/admin

Template Class Binary Tree In C

BinarySearchTree.cpp

Simple implementation of binary search tree in C. binary-search-tree-cpp.cpp. Parentnode is the node to which you want to add the child. The Node class defines three CTORs; a no argument one, one with an argument of type T (by value), and a third with a parent node and a T type value. The function readtreefromfile is just to make a complete test. It is not part of the Tree class code.

/*
* main.cpp
*
* Created on: 8 Nov 2015
* Author: Alex
*/
#include<iostream>
template <classT>
classBinaryTree
{
structnode{
T value;
structnode* right;
structnode* left;
};
public:
BinaryTree();
~BinaryTree();
voidadd(T val);
voidprintPreOrder();
voidprintInOrder();
voidprintPostOrder();
intsize();
boollookup(T val);
private:
structnode* root;
int treeSize;
voidadd(structnode** node, T val);
boollookup(structnode* node, T val);
voidprintPreOrder(structnode* node);
voidprintInOrder(structnode* node);
voidprintPostOrder(structnode* node);
voiddeleteTree(structnode* node);
};
template <classT>
BinaryTree<T>::BinaryTree(){
this->root = NULL;
this->treeSize = 0;
}
template <classT>
BinaryTree<T>::~BinaryTree(){
deleteTree(this->root);
}
template <classT>
int BinaryTree<T>::size(){
returnthis->treeSize;
}
template <classT>
void BinaryTree<T>::add(T val){
add(&(this->root), val);
}
template <classT>
void BinaryTree<T>::add(structnode** node, T val){
if(*node NULL) {
structnode* tmp = newstructnode;
tmp->value = val;
tmp->left=NULL;
tmp->right = NULL;
*node = tmp;
this->treeSize++;
}else{
if(val > (*node)->value){
add(&(*node)->right, val);
}else{
add(&(*node)->left, val);
}
}
}
template <classT>
void BinaryTree<T>::printInOrder(){
printInOrder(this->root);
std::cout << std::endl;
}
template <classT>
void BinaryTree<T>::printInOrder(structnode* node){
if(node != NULL){
printInOrder(node->left);
std::cout << node->value << ', ';
printInOrder(node->right);
}
}
template <classT>
void BinaryTree<T>::printPreOrder(){
printPreOrder(this->root);
std::cout << std::endl;
}
template <classT>
void BinaryTree<T>::printPreOrder(structnode* node){
if(node != NULL) {
std::cout << node->value << ', ';
printInOrder(node->left);
printInOrder(node->right);
}
}
template <classT>
void BinaryTree<T>::printPostOrder(){
printPostOrder(this->root);
std::cout << std::endl;
}
template <classT>
void BinaryTree<T>::printPostOrder(structnode* node){
if(node != NULL){
printInOrder(node->left);
printInOrder(node->right);
std::cout << node->value << ', ';
}
}
template <classT>
void BinaryTree<T>::deleteTree(structnode* node){
if(node != NULL){
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
template <classT>
bool BinaryTree<T>::lookup(T val){
returnlookup(this->root, val);
}
template <classT>
bool BinaryTree<T>::lookup(structnode* node, T val){
if(node NULL){
returnfalse;
}else{
if(val node->value){
returntrue;
}
if(val > node->value){
returnlookup(node->right, val);
}else{
returnlookup(node->left, val);
}
}
}
intmain(){
BinaryTree<int> tree;
tree.add(5);
tree.add(4);
tree.add(7);
tree.add(10);
tree.add(1);
tree.add(2);
tree.printPostOrder();
tree.printInOrder();
tree.printPreOrder();
std::cout << 'Tree size: ' << tree.size() << std::endl;
BinaryTree<char> tee;
tee.add('z');
tee.add('0');
tee.add('9');
tee.add('a');
tee.add('A');
tee.add('Z');
std::cout << 'Contains 9? : '<< ((tee.lookup('9'))? 'true' : 'false' ) << std::endl;
tee.printPostOrder();
tee.printInOrder();
tee.printPreOrder();
std::cout << 'Tree size: ' << tee.size() << std::endl;
}
Sign up for freeto join this conversation on GitHub. Already have an account? Sign in to comment

Trees: Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures.Tree Vocabulary: The topmost node is called root of the tree. The elements that are directly under an element are called its children. Best free video converter for mac.

The element directly above something is called its parent. For example, ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. Finally, elements with no children are called leaves.tree-j. File system-/.