#include <iostream>
using namespace std;
#include <stdio.h>
#include <stack>
using std::stack;
template<typename T>
struct Node
{
Node(T value):mValue(value),mLeftChild(0),mRightChild(0)
{
}
T mValue;
Node *mLeftChild;
Node *mRightChild;
};
/* build a tree which is
1
/ \
2 3
/ \ / \
4 5 6 7
*/
Node<int>*
buildTree()
{
Node<int> *n1 = new Node<int>(1);
Node<int> *n2 = new Node<int>(2);
Node<int> *n3 = new Node<int>(3);
Node<int> *n4 = new Node<int>(4);
Node<int> *n5 = new Node<int>(5);
Node<int> *n6 = new Node<int>(6);
Node<int> *n7 = new Node<int>(7);
n1->mLeftChild = n2;
n1->mRightChild = n3;
n2->mLeftChild = n4;
n2->mRightChild = n5;
n3->mLeftChild = n6;
n3->mRightChild = n7;
return n1;
}
template<typename T>
void
bfsTravesal(Node<T> *root)
{
deque<Node<T> *> result;
result.push_back(root);
while( result.size() )
{
Node<T> *head = result.front();
result.pop_front();
cout << head->mValue<<" ";
if ( head->mLeftChild )
{
result.push_back(head->mLeftChild);
}
if ( head->mRightChild )
{
result.push_back(head->mRightChild);
}
}
}
template<typename T>
void
preOrderTraversal(Node<T> *node)
{
if ( 0 == node )
return ;
cout << node->mValue << " ";
preOrderTraversal(node->mLeftChild);
preOrderTraversal(node->mRightChild);
}
template<typename T>
void
inOrderTraversal(Node<T> *node)
{
if (0 == node)
{
return ;
}
inOrderTraversal(node->mLeftChild);
cout << node->mValue << " ";
inOrderTraversal(node->mRightChild);
}
template<typename T>
void
postOrderTraversal(Node<T> *node)
{
if (0 == node)
{
return ;
}
postOrderTraversal(node->mLeftChild);
postOrderTraversal(node->mRightChild);
cout << node->mValue << " ";
}
template<typename T>
void
preOrderNoneRecursiveTravesal (Node<T> *node)
{
stack<Node<T> *> s;
while (node!=NULL||!s.empty())
{
if ( 0 != node )
{
cout << node->mValue << " ";
s.push(node);
node = node->mLeftChild;
}
else
{
node = s.top();
node = node->mRightChild;
s.pop();
}
}
}
template<typename T>
void
inOrderNoneRecursiveTravesal (Node<T> *node)
{
stack<Node<T> *> s;
Node<T> *currentNode = node;
while (currentNode!=NULL || !s.empty())
{
while (node)
{
s.push(node);
node = node->mLeftChild;
}
if( ! s.empty() )
{
node = s.top();
s.pop();
cout << node->mValue<<" ";
node = node ->mRightChild;
}
}
}
template<typename T>
void
postOrderTraversal (Node<T> *node)
{
}
int main(int argc,char *argv[])
{
Node<int> *root = buildTree();
inOrderNoneRecursiveTravesal(root);
cout << "inOrderNoneRecursiveTravesal finish "<<endl;
preOrderNoneRecursiveTravesal(root);
cout << "preOrderNoneRecursiveTravesal finish "<<endl;
bfsTravesal(root);
cout << "bfs end"<<endl<<endl;
preOrderTraversal(root);
cout << "preOrderTraversal"<<endl<<endl;
inOrderTraversal(root);
cout << "inOrderTraversal"<<endl<<endl;
postOrderTraversal(root);
cout << "postOrderTraversal"<<endl<<endl;
return 0;
}