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