二叉树非递归遍历实现——C语言实现
二叉树非递归遍历：前、中、后序三种遍历需要用到栈，层序遍历需要用到队列。首先用c语言实现栈和队列，然后再实现二叉树的非递归遍历
详细解释参考：维基百科树的遍历/wiki/Tree_traversal
编程环境：Visual Studio
static void Visit(Position P)
{
printf("%d ", P->Data);
}
void PreOrder(Tree T)//前序遍历
{
Stack S;
Position P;
S = InitStack();//创建栈
P = T;
while(P || !StackEmpty(S))//StackEmpty栈是否为空
{
if(P)
{
Visit(P);
if(P->Right)
Push(P->Right, S);
P = P->Left;
}
else
P = Pop(S);
}
DestoryStack(S);//销毁栈
}
void InOrder(Tree T)//中序遍历
{
Stack S;
Position P;
S = InitStack();//创建栈
P = T;
while(P || !StackEmpty(S))
{
if(P)
{
Push(P, S);
P = P->Left;
}
else
{
P = Pop(S);
Visit(P);
P = P->Right;
}
}
DestoryStack(S);//销毁栈
}
void PostOrder(Tree T)//后序遍历，根节点会被访问到两次，只有最后一次被访问到才出栈，即右子树遍历完成之后，根节点才可以出栈
{
Position preNode, currNode;
Stack S;
S = InitStack();
preNode = NULL;
Push(T, S);
while(!StackEmpty(S))//判断栈是否为空
{
currNode = Peek(S);//获取栈顶元素
if(preNode == NULL || preNode->Left == currNode || preNode->Right == currNode)//如果当前节点是根节点或当前节点有左子树或右子树
{
if(currNode->Left)//如果有左子树则左子树入栈
Push(currNode->Left, S);
else if(currNode->Right)//如果当前节点只有右子树则右子树入栈
Push(currNode->Right, S);
}
else if(currNode->Left == preNode)//访问完左子树，返回到父亲点，然后判断是否还有右子树，然后右子树进栈
{
if(currNode->Right)
Push(currNode->Right, S);
}
else//如果没有左子树也没有右子树，或者左子树和右子树都遍历完成，则访问该节点，并将该节点出栈
{
Visit(currNode);
Pop(S);
}
preNode = currNode;
}
DestoryStack(S);//销毁栈
}
void LevelOrder(Tree T)//层序遍历
{
Queue Q;
Position P;
if(T == NULL)
return;
Q = InitQueue();
Enqueue(T, Q);
while(!QueueEmpty(Q))//判断队列是否为空
{
P = Dequeue(Q);
Visit(P);
if(P->Left)
Enqueue(P->Left, Q);
if(P->Right)
Enqueue(P->Right, Q);
}
DestoryQueue(Q);//销毁队列
} 完整代码 /detail/zitong00/6286797
