二叉树的遍历
介绍
二叉树的遍历可以说是二叉树最重要的一个内容，如果想对树的算法有一定的认识，那么二叉树的遍历是一定要熟练使用的，本文将主要介绍一下二叉树的遍历。
算法实现
先序遍历
先序、中序、后序遍历中的序就是访问根节点的顺序。先序遍历也就是先访问根节点。
递归先序遍历
void order_traversal(BiTree T)
{
if(T!=NULL)
{
visit(T);
order_traversal(T->lchild);
order_traversal(T->rchild);
}
}非递归先序遍历
void Preorder_traversal(BiTree T)
{
initStack(S);
BiTree p;
p=T;
while(p!=null||(!isEmpty(S)))
{
if(p!=null)
{
push(S,p);
visit(p);
p=p->lchild;
}
else
{
pop(S,p);
p=p->rchild;
}
}
}中序遍历
递归二叉树遍历
void order_traversal(BiTree T)
{
if(T!=NULL)
{
order_traversal(T->lchild);
visit(T);
order_traversal(T->rchild);
}
}非递归中序遍历
算法思路：
- 沿着根节点的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的节点
- 栈顶元素出栈并访问：若其右孩子为空，继续执行 2；若其右孩子不空，将右子树转执行1.
void Medorder_traversal(BiTree T)
{
InitStack(S);
BiTree p=T;
while(!IsEmpty(S)||p)
{
if(p) //一路向左
{
push(S,p);
p=p->lchild;
}
else
{
pop(S,p);
visit(p);
p=p->rchild;
}
}
}后序遍历
递归后序遍历
void order_traversal(BiTree T){
if(T!=NULL)
{
order_traversal(T->lchild);
order_traversal(T->rchild);
visit(T);
}}非递归后序遍历
非递归后序遍历的算法比较难，这里着重介绍一下。
后序遍历二叉树应该先访问左子树，再访问右子树，最后访问根节点。
算法思路：
从根节点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左子树的节点，但是此时不能出栈并访问，因为如果有其右子树，还需按相同的规则对其右子树进行处理。直到上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早就访问完），这样就保证了正确的访问顺序。
- 沿着根节点的左孩子，依次入栈，直到左孩子为空
- 读栈顶元素：若其右孩子非空，且未被访问过，则右子树转来执行 1 ，否则栈顶元素出栈并访问。
上述算法思路中，第2步必须分清是从左子树返回的，还是右子树返回的。因此设定一个辅助指针，指向最近访问过的节点，也可在节点中增加一个标志域，记录是否已被访问。
void PostOrder(BiTree T)
{
initStack(S);
p=T;
r=NULL;
while (p||!IsEmpty(S))
{
if(p)
{
push(S,p);
p=p->lchild;
}
else
{
GetTop(S,p);
if(p->rchild&&p->rchild!=r)
{
p=p->rchild;
}
else
{
pop(S,p);
visit(p);
r=p;
p=NULL;
}
}
}
}注：每次出栈访问完一个节点就相当于遍历完以该节点为根节点的子树，所以要将该节点置NULL;
对于后序非递归遍历，当一个节点的左右子树都被访问后才能出栈。实际上，访问一个节点p时，栈中节点恰好是p节点的所有祖先，从栈底到栈顶节点再加上p节点，刚好构成从根节点到p节点的一条路径，此算法在求根节点到某节点的路径，两个节点的最近公共祖先上都有其作用。
层次遍历
层次遍历一般借助于一个队列。
void LevelOrder(BiTree T)
{
InitQueue(Q);
BiTree p=T;
Enqueue(p);
while(!QueueEmpty(Q))
{
Dequeue(Q,p);
visit(p);
if(p->lchild!=NULL)
Enqueue(p->lchild);
if(p->rchild!=NULL)
Enqueue(p->rchild);
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录