A brief summary Binary Tree, C++ implementation

This is a NON Generic implementation(Templates are not Used )

Below are the two header files which defines the class for a Binary tree which holds integer data.

BinaryTreeIntNode.h file defines how the the nodes of the tree are implemented, BinaryTreeIntNode.cpp

has the corresponding member functions implementation. 

LintkedIntTree.h file defines the structure of a Binary tree and the operation on the Binary tree,

LintkedIntTree.cpp has the corresponding implementations of member functions.

For more information on Trees visit:

http://abriefsummaryofeverything.blogspot.com/2011/08/trees-and-binary-treesdraft-version.html
/*################################################################################################################################ FILE:BinaryTreeIntNode.h Author:Thejas ################################################################################################################################*/ #ifndef BINARYTREEINTNODE_H #define BINARYTREEINTNODE_H using namespace std; class BinaryTreeIntNode { public: int data; BinaryTreeIntNode* left; BinaryTreeIntNode* right; BinaryTreeIntNode(); BinaryTreeIntNode(int element,BinaryTreeIntNode* leftNode,BinaryTreeIntNode* rightNode); BinaryTreeIntNode(int element); virtual ~BinaryTreeIntNode(); protected: private: }; #endif // BINARYTREEINTNODE_H /*################################################################################################################################# FILE:LintkedIntTree Author:Thejas #################################################################################################################################*/ #ifndef LINTKEDINTTREE_H #define LINTKEDINTTREE_H #include "BinaryTreeIntNode.h" #include "../stackint.h" class LintkedIntTree { public: LintkedIntTree(); LintkedIntTree(BinaryTreeIntNode* node,int size); void preOrder(bool isRecursive); void preOrderRec(BinaryTreeIntNode* node); void preOrderNonRec(StackInt* stack); void postOrder(bool isRecursive); void postOrderRec(BinaryTreeIntNode* node); void postOrderNonRecDeck(StackInt* stack); void postOrderNonRecColour(StackInt* stack); void inOrder(bool isRecursive); void InOrderRec(BinaryTreeIntNode* node); void InOrderNonRecColour(StackInt* stack); int height(bool isRecursive); int heightRec(BinaryTreeIntNode* node); int heightNonRec(StackInt* stack); virtual ~LintkedIntTree(); protected: private: BinaryTreeIntNode* root; int treeSize; }; #endif // LINTKEDINTTREE_H

/*################################################################################################################################ FILE:BinaryTreeIntNode.cpp Author:Thejas ################################################################################################################################*/ #include "../include/BinaryTreeIntNode.h" #include<iostream> BinaryTreeIntNode::BinaryTreeIntNode() { data=0; left=NULL; right=NULL; } BinaryTreeIntNode::BinaryTreeIntNode(int element,BinaryTreeIntNode* leftNode,BinaryTreeIntNode* rightNode) { data=element; left=leftNode; right=rightNode; } BinaryTreeIntNode::BinaryTreeIntNode(int element) { data=element; left=NULL; right=NULL; } BinaryTreeIntNode::~BinaryTreeIntNode() { //dtor } /*################################################################################################################################ FILE:LintkedIntTree.cpp Author:Thejas ################################################################################################################################*/ #include "../include/LintkedIntTree.h" #include<iostream> #include <deque> LintkedIntTree::LintkedIntTree() { root=NULL; } LintkedIntTree::~LintkedIntTree() { //dtor } LintkedIntTree::LintkedIntTree(BinaryTreeIntNode* node,int size) { treeSize= size; root = node; } void LintkedIntTree::preOrderRec(BinaryTreeIntNode* node) { if(node == NULL){return;} cout<<" "<<node->data; preOrderRec(node->left); preOrderRec(node->right); return; } void LintkedIntTree::preOrder(bool isRecursive) { if(isRecursive==true) { this->preOrderRec(root); } else{ StacktNode* temp = new StacktNode(root,NULL); StackInt* stack = new StackInt(temp,1); this->preOrderNonRec(stack); } return; } void LintkedIntTree::preOrderNonRec(StackInt* stack) { while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp == NULL) { continue; } else { cout<<" "<<temp->node->data; if(temp->node->right!= NULL) { StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); } if(temp->node->left!= NULL) { StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); } } temp->~StacktNode(); } return; } void LintkedIntTree::postOrder(bool isRecursive) { if(isRecursive == true) { postOrderRec(root); }else { StacktNode* temp = new StacktNode(root,NULL); StackInt* stack=new StackInt(temp,1); postOrderNonRecDeck(stack); stack=new StackInt(temp,1); cout<<"\n POST Order COLOURING\n"; postOrderNonRecColour(stack); } return; } void LintkedIntTree::postOrderRec(BinaryTreeIntNode* node) { if(node == NULL) { return; }else { postOrderRec(node->left); postOrderRec(node->right); cout<<" "<<node->data; return; } } void LintkedIntTree::postOrderNonRecDeck(StackInt* stack) { std::deque<int>* deck= new deque<int>(); if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp==NULL) { continue; } BinaryTreeIntNode* t = temp->node; temp->~StacktNode(); deck->push_front(t->data); if(t->left!= NULL) { StacktNode* l= new StacktNode(t->left,NULL); stack->push(l); } if(t->right != NULL) { StacktNode* r = new StacktNode(t->right,NULL); stack->push(r); } } deque<int>::iterator it; it = deck->begin(); int x =deck->size(); cout<<"DECK SIZE = "<<x <<endl; while(it!=deck->end()) { cout<<" "<<*it++; } } void LintkedIntTree::postOrderNonRecColour(StackInt* stack) { if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp == NULL) { continue; } BinaryTreeIntNode* n = temp->node; if(n==NULL) { continue; } if(temp->colour == 0) { StacktNode* t = new StacktNode(n->right,NULL); temp->colour = 1; stack->push(temp); stack->push(t); t=new StacktNode(n->left,NULL); stack->push(t); } else { cout<<" "<<n->data; } } } void LintkedIntTree::inOrder(bool isRecursive) { if(isRecursive == true) { InOrderRec(root); }else { StacktNode* temp = new StacktNode(root,NULL); StackInt* stack=new StackInt(temp,1); InOrderNonRecColour(stack); } } void LintkedIntTree::InOrderRec(BinaryTreeIntNode* node) { if(node == NULL) { return; } InOrderRec(node->left); cout<<" "<<node->data; InOrderRec(node->right); return; } void LintkedIntTree::InOrderNonRecColour(StackInt* stack) { if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode *temp = stack->pop(); if(temp== NULL || temp->node == NULL) { continue; } if(temp->colour == 0) { StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); temp->colour=1; stack->push(temp); StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); }else if(temp->colour==1) { cout<<" "<<temp->node->data; } } return; } int LintkedIntTree::heightRec(BinaryTreeIntNode* node) { if(node == NULL) { return 0; } int h1 = heightRec(node->left); int h2 = heightRec(node->right); h1++; h2++; return h1>h2?h1:h2; } int LintkedIntTree::height(bool isRecursive) { if(isRecursive) { return heightRec(root); } else { StacktNode* node = new StacktNode(root,NULL); StackInt* stack = new StackInt(node,1); return heightNonRec(stack); } } int LintkedIntTree::heightNonRec(StackInt* stack) { int maxh = 1; int h = 1; if(stack == NULL) { return -1; } while(!stack->isEmpty()) { maxh = maxh>h?maxh:h; StacktNode* temp=stack->pop(); h--; if(temp->node==NULL) { continue; } if(temp->colour == 0)//no child has been visited. { temp->colour=1; h++; stack->push(temp); if(temp->node->left!= NULL) { h++; StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); } }else if(temp->colour==1) { temp->colour=2; h++; stack->push(temp); if(temp->node->left!= NULL) { h++; StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); } }else { continue; } cout<<" h ="<<h<<endl; } return maxh; }