Algorithms: Binary tree

Simple implementation of binary tree in C++

#include<iostream.h>
/**************************************
 Tree Node structure - contains data, left and right children
**************************************/
template <class T>
  struct TreeNode {
  T data;
  TreeNode *left;
  TreeNode *right;

  TreeNode() {
    left = NULL;
    right = NULL;
    this->data = T();
  }

  TreeNode(T data) {
    left = NULL;
    right = NULL;
    this->data = data;
  }
};
/**************************************
Binary Tree class implementation
**************************************/
template <class T> class BinTree {
  TreeNode<T> *root;
private:
  void Add(TreeNode<T> *node, T data){
    if (data > node->data) {
      if(node->right == NULL) {
        TreeNode<T> *n = new TreeNode<T>(data);
        node->right = n;
      } else {
      // go to right branch
        Add(node->right, data);
      }
    } else if (data < node->data) {
      if(node->left == NULL) {
        TreeNode<T> *n = new TreeNode<T>(data);
        node->left = n;
      } else {
      // go to left branch
        Add(node->left, data);
      }
    } else {
    // do nothing - we already have this node in tree
    }
  }

  bool Find(TreeNode<T> *node, T data){
    T nodeData = node->data;
    cout << " " << nodeData;

    if(nodeData == data) {
      return true;
    } else if(data > nodeData) {
      if(node->right == NULL) {
        return false;
      } else {
        return Find(node->right, data);
      }
    } else {
      if(node->left == NULL) {
        return false;
      } else {
        return Find(node->left, data);
      }
    }
  }
public:
  BinTree(){
    root = NULL;
  }

  void Add(T data) {
    if(root == NULL) {
      TreeNode<int> *n = new TreeNode<int>(data);
      root = n;
    } else {
      Add(root, data);
    }
  }

  bool Find(T data) {
    if(root->data == data){
      cout << " " << data;
      return true;
    } else {
      return Find(root, data);
    }
  }
};

int main (int argc, char *argv[]) {
  BinTree<int> *tree = new BinTree<int>();

  tree->Add(12);
  tree->Add(15);
  tree->Add(18);
  tree->Add(14);
  tree->Add(5);
  tree->Add(8);
  tree->Add(7);
  tree->Add(2);
  tree->Add(4);
  tree->Add(1);

  cout << "Searching for 7:";
  cout << " - " << (tree->Find(7) ? "FOUND" : "NOT FOUND") << endl;
}

Output (using the scenario on the picture above):

Searching for 7: 12 5 8 7 - FOUND

Leave a Reply