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:
}
}
}
网友评论