BintreeNode.h

Go to the documentation of this file.

//
//  Created by Matthias Thöny on 1/11/12.
//  Copyright (c) 2012 University of Zuerich. All rights reserved.
//
#ifndef VMML_BintreeNode_h
#define VMML_BintreeNode_h

#include <iostream>

namespace geData {
    template <class T>
    class BintreeNode
    {
    protected:
        T data;
        BintreeNode<T> *left, *right, *parent;
    public:
        //constructors and destructor
        BintreeNode(T _data): data(_data), left(0L), right(0L), parent(0L){}
        ~BintreeNode(){
            if(this->left != NULL)
            {
                delete this->left;
            }
            if(this->right != NULL)
            {
                delete this->right;
            }
            this->left = 0L;
            this->right = 0L;
            this->parent = 0L;
        }
        
        //set and get data member
        const T getData() const { return data; }
        void setData(T data) {  this->data = data; }
        
        //set and get parent
        BintreeNode<T>* getParent() { return this->parent; }
        void setParent(BintreeNode<T> * node) { this->parent = node; }
        
        //set and get left and right branches
        BintreeNode<T>* getLeft() { return left; }
        BintreeNode<T>* getRight() { return right; }
        
        void setLeft(BintreeNode<T>* node){
            if(node != 0L){
                node->setParent(this);
                left = node;
            }else{
                left = 0L;
            }
        }
        
        void setRight(BintreeNode<T> * node){
            if(node != 0L){
                node->setParent(this);
                right = node;
            }else{
                right = 0L;
            }
        }
        
        BintreeNode<T>* search(T data)
        {
            // Daten nicht vorhanden
            if(this->data == 0L)
            {
                return 0L;
            }else if(this->data == data)
            {
                return this;
            }else if(data < this->data)
            {
                return this->left->search(data);
            }else{
                return this->right->search(data);
            }
        }
        
        BintreeNode<T>* searchLeftElement() {
            if(this->left == 0L)
            {
                return this;
            }else{
                return this->getLeft()->searchLeftElement();
            }
        }
        
        BintreeNode<T>* searchRightElement() {
            if(this->right == 0L)
            {
                return this;
            }else{
                return this->getRight()->searchRightElement();
            }
        }
        
        BintreeNode<T>* findInorderSuccessor() {
            if(this->right != 0L) {
                return this->right->searchLeftElement();
            }else{
                return 0L;
            }
        }
        
        BintreeNode<T>* findInorderPredeccessor() {
            if(this->left != 0L) {
                return this->left->searchRightElement();
            }else{
                return 0L;
            }
        }
        
        virtual void printValue(){
            //std::cout << &this->data << std::endl;
            std::cout << this->data << " ";
        }
        
        virtual void printInorder() {
            this->printValue();
            if(this->left != 0L) {
                this->left->printInorder();
            }
            if(this->right != 0L) {
                this->right->printInorder();
            }
        }
        
        virtual void printPostorder() {
            if(left != 0L) {
                left->printPostorder();
            }
            if(right != 0L) {
                right->printPostorder();
            }
            this->printValue();
        }
        
        virtual void printEuler() {
            this->printValue();
            if(left != 0L) {
                left->printEuler();
            }
            this->printValue();
            if(right != 0L) {
                right->printEuler();
            }
            this->printValue();
        }
        
        virtual bool insert(T data)
        {
            if(left == 0L)
            {
                left = new BintreeNode<T>(data);
                left->setData(data);
                return true;
            }
            if(right == 0L)
            {
                right = new BintreeNode<T>(data);
                right->setData(data);
                return true;
            }
            if(left->insert(data))
            {
                return true;
            }else{
                if(right->insert(data))
                {
                    return true;
                }else{
                    std::cout << "Binary tree reaches max capacity" << std::endl;
                    return false;
                }
            }
        }
        
        virtual bool remove(T data){
            std::cout << "TODO";
            return 0;
        }
        
        //comparison operators
        virtual bool operator<(const BintreeNode<T>& node) const {
            return this->data < node.data;
        }
        
        bool virtual operator>(const BintreeNode<T>& node) const {
            return this->data > node.data;
        }
        
        bool virtual operator==(const BintreeNode<T>& node) const {
            return this->data == node.data;
        }
    };
}
#endif