遍历二叉树

迈不过友情╰ 2022-08-22 14:26 438阅读 0赞

**1. 二叉树的遍历**

遍历定义 ——顺着某一条搜索路径巡访二叉树中的结点，使得 每个结点均被访问一次，而且仅被访问一次。

“访问”的含义可以很广，如：输出结点的信息等。

遍历用途——查找具有某种特征的结点；对树中全部结点逐一进行某种处理。遍历是二叉树一切运算的基础和核心。

**遍历规则**

二叉树由根、左子树、右子树构成，定义为D、 L、R

D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD

若限定先左后右，则有三种实现方案： DLR LDR LRD

先 (根)序遍历 中 (根)序遍历 后(根)序遍历

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。

![20160531113028419][]

![20160531113049639][]

![20160531113110952][]

讨论：若已知先序/后序遍历结果和中序遍历结果， 能否“恢复”出二叉树？

例如： 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。

分析：

①由后序遍历特征，根结点必在后序序列尾部（即A）；

②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即 FHG）；

③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。

![20160531113138609][]

例如：

已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?

解题步骤：

![20160531113156530][]

![20160531113217203][]

**二叉树遍历算法的递归实现：**

![20160531113240391][]

![20160531113257781][]

**对遍历的分析：**

1. 从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

![20160531113318234][]

从虚线的出发点到终点的路径 上，每个结点经过3次。

第1次经过时访问＝先序遍历

第2次经过时访问＝中序遍历

第3次经过时访问＝后序遍历

2. 二叉树遍历的时间效率和空间效率

时间效率:O(n) //每个结点只访问一次

空间效率:O(n) //栈占用的最大辅助空间

（精确值：树深为k的递归遍历需要k+1个辅助单元！最坏情况深度为n，所以空间复杂度为O(n)）

**二叉树遍历算法的非递归实现**

算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。

![20160531113348939][]  
![20160531113402562][]

**二叉树遍历算法的应用举例**

例1 统计二叉树中叶子结点的个数

思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。  
![20160531113430612][]

**二叉树遍历算法的应用举例**

例1 统计二叉树中叶子结点的个数

思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。  
![20160531113456675][]

例3 求二叉树的深度

算法思路：

只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。

当T= NULL时,深度为0;

否则, T的深度= MAX\{左子树深度,右子树深度\}+1;

例4 按层次输出二叉树中的所有结点

算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。

技巧：当根结点入队后，根据其左右孩子指针域令其左、右孩子结点入队，然后根节点出队; 而之后根结点以外的结点出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。

例5 判断二叉树是否为完全二叉树

算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。

技巧: 按层序遍历方式，先把所有结点（不管当前结 点是否有左右孩子）都入队列.若为完全二叉树, 则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。

用二叉链表法（l\_child, r\_child）存储包含n个结点的 二叉树，结点的指针区域中会有n+1个空指针。

[20160531113028419]: /images/20220722/194d906c4f62450fb1ecf8b80ef530a0.png
[20160531113049639]: /images/20220722/b6d89b3ba1354aca9d366dff92e3d8d7.png
[20160531113110952]: /images/20220722/fb2500a8a5644aceaa2a3354dc5be0ce.png
[20160531113138609]: /images/20220722/27797cc704064d8399c614cb17d3ff28.png
[20160531113156530]: /images/20220722/354b0ce87ad74350b7a9b4388e64ad70.png
[20160531113217203]: /images/20220722/35852e2d2cdf49b28293763b634ceffd.png
[20160531113240391]: /images/20220722/6eb5012c2d6343bba43d4d88059a95ce.png
[20160531113257781]: /images/20220722/69ace76c53254463a1189ae246fdea3c.png
[20160531113318234]: /images/20220722/b3f663e904e64417a2cf387b6810d0ab.png
[20160531113348939]: /images/20220722/9d15228d27d54114ba48728ed26576c0.png
[20160531113402562]: /images/20220722/c5c6ce5a3a6349459e73e590406c090a.png
[20160531113430612]: /images/20220722/5397844c4c5b49fe9f7599153053fece.png
[20160531113456675]: /images/20220722/da8378e746414bea996d3a1b66c28f16.png