二叉树层次和中序遍历算法

先序非递归算法

思路

假设：T是要遍历树的根指针，若T != NULL

对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。

问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？

方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。

算法1

void PreOrder(BiTree T, Status ( Visit ) (ElemType e))

{ // 基于方法一

InitStack(S);

while ( T!=NULL || !StackEmpty(S)){

while ( T != NULL ){

Visit(T->data) ;

Push(S,T);

T = T->lchild;

}

if( !StackEmpty(S) ){

Pop(S,T);

T = T->rchild;

}

}

}

算法2

void PreOrder(BiTree T, Status ( Visit ) (ElemType e))

{ // 基于方法二

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Visit(T->data);

Push(S, T->rchild);

T = T->lchild;

}

if ( !StackEmpty(S) ){

Pop(S,T);

}

}

}

进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

中序非递归算法

思路

T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。

问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？

方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

算法

void InOrder(BiTree T, Status ( Visit ) (ElemType e))

{

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Push(S,T);

T = T->lchild;

}

if( !StackEmpty(S) ){

Pop(S, T);

Visit(T->data);

T = T->rchild;

}

}

}

进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

后序非递归算法

思路

T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。

首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [Page]

typedef struct stackElement{

Bitree data;

char tag;

}stackElemType;

算法

void PostOrder(BiTree T, Status ( Visit ) (ElemType e))

{

InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){

while ( T != NULL ){

Push(S,T,0);

T = T->lchild;

}

while ( !StackEmpty(S) && GetTopTag(S)==1){

Pop(S, T);

Visit(T->data);

}

if ( !StackEmpty(S) ){

SetTopTag(S, 1); // 设置栈顶标记

T = GetTopPointer(S); // 取栈顶保存的指针

T = T->rchild;

}else break;

}

}

先序：是二叉树遍历中的一种，即先访问根结点，然后遍历左子树，后遍历右子树。遍历左、右子树时，先访问根结点，后遍历左子树，后遍历右子树，如果二叉树为空则返回。

中序：是二叉树遍历中的一种，即先遍历左子树，后访问根结点，然后遍历右子树。若二叉树为空则结束返回。

后序：是二叉树遍历中的一种，即先遍历左子树，后遍历右子树，然后访问根结点，遍历左、右子树时，仍先遍历左子树，后遍历右子树，最后遍历根结点。

扩展资料：

当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。

如果已知前序遍历和中序遍历，就能确定后序遍历，同样如果已知中序遍历和后序遍历，就能确定前序遍历，如果已知前序遍历和后序遍历，就能直到中序遍历。

参考资料：

百度百科-前序遍历

参考资料：

百度百科-中序遍历

参考资料：

百度百科-后序遍历

以你的图为准，不管是先序遍历，中序遍历，还是后序遍历，都以根为主，也就是你看根就可以了。就那中序遍历来说，按规则来，顺序是左根右，根就是F，对于根的左就是F左边的一大堆，右就是F右边的那一堆，就可以写成 （）F（），对左来说，根就是C，C的左右和上边的确定方法一样，对右来说，根就是E，E的有是有的，但E的左是空，写成（（）C（））F（E（）），这样依次写下来就是ACBDFEG。当然写的时候不需要写括号，只是为了说明方便，先序遍历和后序遍历一样。

从前序的第一个结点开始确定根，中序决定左子树和右子树，如第一个结点A，根据中序可知，A的左子树是DBE，右子树是FC，再从前序中确定第二个根B，根据中序可知B的左子树是D，右子树为E，依次重复执行，直到遍历完所有结点。所以后序遍历DEBFCA

首先从前序的第一个确定二叉树的根A，回到中序切割，将二叉树分为三部分：

左子树的中序DBGE，根A，右子树的中序CHF

再由左子树的前序可知左子树的根为B，于是左子树的中序被再次切分为三部分：

左子树的左子树中序D，左子树的根B，左子树的右子树的中序GE

类似地，由右子树的前序可知右子树的根为C，于是右子树的中序也被切分为三部分：

右子树的左子树为空，右子树的根C，右子树的左子树的中序HF

继续切分下去：GE的根为E、HF的根为F，直到每棵子树只有一个结点为止，最终得到的完整二叉树如下：

于是后序遍历序列为：DGEBHFCA

一、

先序遍历

：

1、访问根节点

2、

前序遍历

左

子树

3、前序遍历

右子

树

二、

中序遍历

：

1、中序遍历左子树

2、访问根节点

3、中序遍历右子树

三、

后序

遍历：

1、

后序遍历

左子树

2、后序遍历右子树

3、访问根节点

下面介绍一下例子与方法：

1、画树求法：

第一步，根据前序遍历的特点，我们知道

根结点

为G

第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。

第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1

确定根,确定左子树，确定右子树。

2

在左子树中递归。

3

在右子树中递归。

4

打印当前根。

那么，我们可以画出这个

二叉树

的形状：

那么，根据后序的遍历规则，我们可以知道，后序遍历顺序为：AEFDHZMG

二叉树的一些介绍：

在计算机科学中，二叉树是每个节点最多有两个子树的

树结构

。通常子树被称作“左子树”（left

subtree）和“右子树”（right

subtree）。二叉树常被用于实现

二叉查找树

和

二叉堆

。

二叉树的每个结点至多只有二

棵子

树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为

满二叉树

；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为

完全二叉树

。

以上就是关于二叉树层次和中序遍历算法全部的内容，包括:二叉树层次和中序遍历算法、什么叫先序、中序、后序遍历、关于c语言中二叉树前，中，后序遍历，没看懂，请问该如何理解比如中序遍历:左，根，右。那么拿到一个等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！