#include
#include
#include
#include
class Node
{
private:
Node* _left;
Node* _right;
int _data;
void _AddNode(Node*& _nodeRef, int i)
{
if(_nodeRef)
{
delete _nodeRef;
}
_nodeRef = new Node(i);
}
void _DeleteNode(Node*& _nodeRef)
{
if(_nodeRef)
delete _nodeRef;
}
public:
Node(int i=0, Node* _left=0, Node* _right =0):_left(left),_right(right),_data(i) {}
~Node()
{
}
void AddLeftNode(int i=0)
{
_AddNode(_left,i);
}
void AddRightNode(int i=0)
{
_AddNode(_right,i);
}
void AddNode(int i=0)
{
Node** temp = &this;
while(*temp!=NULL)
{
if(*temp->_data <= i)
temp = &(*temp)->_left;
else
temp = &(*temp)->_right;
}
*temp = new Node(i);
}
Node* Left()
{
return _left;
}
Node* Right()
{
return _right;
}
void DeleteLeft()
{
_DeleteNode(_left);
}
void DeleteRight()
{
_DeleteRight(_right);
}
void SetData(int i=0)
{
_data = i;
}
int Data()
{
return _data;
}
};
void PreOrderTraversalRecuresive(Node* node)
{
//Visit Root
//Visit Left
//Visit Right
if(!node)
return;
cout << node->Data() << " ";
PreOrderTraversalRecuresive(node->Left());
PreOrderTraversalRecuresive(node->Right());
}
void InOrderTraversalRecuresive(Node* node)
{
//Visit Left
//Visit Root
//Visit Right
//returns elems in ascending order
if(!node)
return;
InOrderTraversalRecuresive(node->Left());
cout << node->Data() << " ";
InOrderTraversalRecuresive(node->Right());
}
void PostOrderTraversalRecuresive(Node* node)
{
//Visit Left
//Visit Right
//Visit Root
if(!node)
return;
PostOrderTraversalRecuresive(node->Left());
PostOrderTraversalRecuresive(node->Right());
cout << node->Data() << " ";
}
void PreOrderTraversalIterative(Node* node)
{
if(!node)
return;
std::stack
Node* temp;
nodeStack.push(node);
while(!nodeStack.empty())
{
temp = nodeStack.top();
cout << temp->Data() < " ";
nodeStack.pop();
temp->Right()?nodeStack.push(temp->Right()):0;
temp->Left()?nodeStack.push(temp->Left()):0;
}
}
void InOrderTraversalIterative(Node* node)
{
if(!node)
return;
std::stack
Node* temp=node;
nodeStack.push(temp);
while(!nodeStack.empty())
{
while(!nodeStack.top()->Left())
{
nodeStack.push(temp->Left());
}
cout << nodeStack.top()->Data() < " ";
nodeStack.pop();
temp = nodeStack.top();
cout << temp->Data() << " ";
nodeStack.pop();
temp->Right()?nodeStack.push(temp->Right()):0;
}
}
void PostOrderTraversalIterative(Node* node)
{
if(!node)
return;
std::stack
Node* temp=node;
nodeStack.push(temp);
while(!nodeStack.empty())
{
while(!nodeStack.top()->Left())
{
nodeStack.push(temp->Left());
}
cout << nodeStack.top()->Data() < " ";
nodeStack.pop();
temp = nodeStack.top();
temp->Right()?nodeStack.push(temp->Right()):0;
}
}
void BreadthFirstTraversalIterative(Node *node)
{
if (!node)
return;
std::queue
Node* temp = node;
nodeQueue.push(node);
while(!nodeQueue.empty())
{
temp = nodeQueue.top();
nodeQueue.pop();
cout << temp->Data() << " " ;
temp->Left()?nodeStack.push(temp->Left()):0;
temp->Right()?nodeStack.push(temp->Right()):0;
}
}
void DepthFirstTraversalRecursive(Node* node)
{
if (!node)
return;
cout << node->Data() << " " ;
Node* temp;
if(node->Left())
temp = node->left();
else if(node->Right())
temp = node->Right();
else
temp = NULL;
DepthFirstTraversalRecursive(temp);
}
void DepthFirstTraversalIterative(Node* node)
{
if(!node)
return;
std::stack
Node* temp=node;
nodeStack.push(temp);
while(!nodeStack.empty())
{
while(!nodeStack.top()->Left())
{
nodeStack.push(temp->Left());
}
cout << nodeStack.top()->Data() < " ";
nodeStack.pop();
temp = nodeStack.top();
temp->Right()?nodeStack.push(temp->Right()):0;
}
}
int DepthOfTree(Node *node)
{
if(!node)
return 0;
int h1 = DepthOfTree(node->Left());
int h2 = DepthOfTree(node->Right());
return (h1 > h2)?h1+1:h2+1;
}
Node* FillTree(char* fileName)
{
if(!fileName)
return NULL;
ifstream ifp;
if(!ifp.open(fileName))
return NULL;
int data;
ifp >> data;
Node* node = new Node(data);
while(!ifp.eof())
{
ifp >> data;
node->AddNode(i);
}
ifp.close();
}
int main(int argc, char** argv)
{
PreOrderTraversalRecuresive();
InOrderTraversalRecuresive();
PostOrderTraversalRecuresive();
PreOrderTraversalIterative();
InOrderTraversalIterative();
PostOrderTraversalIterative();
BreadthFirstTraversal();
DepthFirstTraversalRecursive();
DepthFirstTraversalIterative();
DepthOfTree();
}
