typedef struct BiTree* Node;

typedef struct BiTree* Tree;

struct BiTree

{

 int Element;

 Node Left;

 Node Right;

 bool isFirst; //从下向上出栈过程中,第一次出现在栈顶

};

 

 

//先序遍历, 递归

void TraverseTreePreOrder(Tree T)

{

 if(T != NULL)

 {

 cout<<T->Element<<" ";

 TraverseTreePreOrder(T->Left);

 TraverseTreePreOrder(T->Right);

 }

}

 

//中序遍历, 递归

void TraverseTreeInOrder(Tree T)

{

 if(T != NULL)

 {

 TraverseTreeInOrder(T->Left);

 cout<<T->Element<<" ";

 TraverseTreeInOrder(T->Right);

 }

}

 

//后序遍历,递归

void TraverseTreePostOrder(Tree T)

{

 if(T != NULL)

 {

 TraverseTreePostOrder(T->Left);

 TraverseTreePostOrder(T->Right);

 cout<<T->Element<<" ";

 }

}

 

//先序遍历. 非递归

void TraverseTreePreOrder2(Tree T)

{

 stack<Node> Stack;

 while(T!= NULL && !Stack.empty()) //每进行一次while,都是从左儿子到右儿子

 {

 while(T != NULL) //一直遍历最左边的节点

 {

 cout<<T->Element<<" ";

 Stack.push(T);

 T = T->Left;

 }

 //如果遍历到底了,就向上一层, 遍历右儿子

 T =Stack.top(); 

 T = T->Right; 

 Stack.pop(); 

 

 }

}

 

//中序遍历, 非递归

void TraverseTreeInOrder2(Tree T)

{

 stack<Node> Stack;

 while(T!= NULL && !Stack.empty())

 {

 while(T != NULL)

 {

 Stack.push(T); 

 T = T->Left;

 }

 T = Stack.top;

 Stack.pop();

 cout<<T->Element<<" ";

 T = T->Right;

 }

}

 

//后序遍历, 非递归

void TraverseTreePostOrder(Tree T)

{

 stack<Node> Stack;

 while(T != NULL && !Stack.empty())

 {

 while(T != NULL)

 {

 Stack.push(T);

 T->isFirst = true; //所有节点在初始入栈时都会在此被设为true.

 T = T->Left;

 }

 T = Stack.top();

 //Stack.pop();

 if(T->isFirst) //左节点被遍历完,准备向右节点遍历时

 {

 T->isFirst = false;

 //Stack.push(T);

 T = T->Right;

 }

 else //右节点被遍历完,又回到这个节点,准备走向父节点

 {

 Stack.pop();

 cout<<T->Element<<" ";

 T = NULL:

 }

 

 }

}