前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

6.7遍历二叉树

6.7.1 二叉树遍历原理

二叉树的遍历( traversing binary tree )是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

访问和次序是关键！

6.7.2二叉树的遍历方法

1.前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树,再前序遍历右子树。如下图所示，遍历的顺序为: ABDGHCEIF。

2.中序遍历

规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。 如图所示、谝历的顺序为: GDHBAEICF。

3.后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。 如图所示，遍历的顺序为: GHDBIEFCA.

4.层序遍历

规则是若树为空，则空操作返回，否则从树的第一层， 也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图所示，遍历的顺序为: ABCDEFGHI。

6.7.3前序遍历算法

二叉树的定义是递归的方式，所以实现算法也可以递归

/*二叉树的前序遍历递归算法*/
 void PreOrderTraverse ( BiTree T )
 {
     if( T==NULL)
         return;
     printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/
     PreOrderTraverse (T->lchild) ; /*先序遍历左子树*/
     PreOrderTraverse (T->rchild) ; /*最后先序遍历右子树*/
 }

可以简单的看个例子

一颗这样的二叉树T，如果要遍历它的话

1.调用PreOrderTraverse (T), T根结点不为null, 所以执行printf, 打印字母A

2.调用PreOrderTraverse (T->lchild) ;访问了A结点的左孩子，不为null,执行 printf显示字母B

3.不断的递归调用PreOrderTraverse (T->lchild)到H，此时为H结点无左孩子，所以T==null, 返回此函数，此时递归调用PreOrderTraverse (T->rchild) ;访问了H结点的右孩子，printf 显示字母K,

后面的话会不断的向前向左向右遍历

6.7.4中序遍历算法

/*二叉树的前序遍历递归算法*/
 void PreOrderTraverse ( BiTree T )
 {
     if( T==NULL)
         return;
     InOrderTraverse (T->lchild) ; /*中遍历左子树*/
     printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/
     InOrderTraverse (T->rchild) ; /*最后中序遍历右子树*/
 }

流传和上类似，都是不断的递归

6.7.5后序遍历算法

/*二叉树的前序遍历递归算法*/
 void PreOrderTraverse ( BiTree T )
 {
     if( T==NULL)
         return;
     InOrderTraverse (T->lchild) ; /*中遍历左子树*/
     InOrderTraverse (T->rchild) ; /*最后中序遍历右子树*/
     printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/
 }

6.7.6推导遍历结果

已知一棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少? （已知前中求后）

前序遍历是先打印在递归左跟右，所以前序遍历序列为ABCDEF，A就位根结点的数据。再由中序遍历序列CBAEDF可以CB是A的左子树，EDF是A的右子树

然后我们看前序中的C和B,它的顺序是ABCDEF,是先打印B后打印C,所以B应该是A的左孩子，而C就只能是B的孩子,此时是左还是右孩子还不确定。再看中序序列是CBAEDF, C是在B的前面打印，这就说明C是B的左孩子，否则就是右孩子了

再看前序中的E、D、F,它的顺序是ABCDEF,那就意味着D是A结点的右孩子，E和F是D的子孙，注意，它们中有一个不一定是孩子，还有可能是孙子的。再来看中序序列是CBAEDF，由于E在D的左侧，而F在右侧，所以可以确定E是D的左孩子，F是D的右孩子。因此最终得到的二叉树

得到了二叉树，结果就是CBDEFDA

为刚才判断了A结点是根结点，那么它在后序序列中，一定是最后一个。刚才推导出C是B的左孩子，而B是A的左孩子，那就意味着后序序列的前两位一定是CB。同样的办法也可以得到EFD这样的后序顺序，最终就自然的得到CBEFDA这样的序列，不用在草稿上画树状图了。

反过来 ，二叉树的中序序列是ABCDEFG,后序序列是BDCAFGE,求前序序列。（已知中后求前）

由后序的BDCAFGE,得到E是根结点，因此前序首字母是E

于是根据中序序列分为两棵树ABCD和FG,由后序序列的BDCAFGE,知道A是E的左孩子，前序序列目前分析为EA

再由中序序列的ABCDEFG, 知道BCD是A结点的右子孙，再由后序序列的BDCAFGE知道C结点是A结点的右孩子，前序序列目前分析得到EAC。

中序序列ABCDEFG,得到B是C的左孩子，D是C的右孩子,所以前序序列目前分析结果为EACBD。

由后序序列BDCAFGE,得到G是E的右孩子，于是F就是G的孩子，细细分析，根据中序序列ABCDEFG,是可以得出F是G的左孩子。

从这里我们也得到两个二叉树遍历的性质。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

要注意的是，如果已知前序和后序遍历，是不能确定一颗二叉树的