遍历二叉树的递归与非递归实现

在二叉树的操作实现中，常常需要对其所有节点进行某种操作，这种对所有节点逐一进行的操作就是遍历。

遍历二叉树的递归实现

遍历二叉树是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次且仅被访问一次。其中的访问可指计算二叉树中节点的数据信息，打印该节点的信息，也包括对节点进行的任何其他操作。

遍历二叉树是二叉树最基本的操作，也是二叉树其他各种操作的基础。因为在实际应用中，常常需要按一定顺序对二叉树中的每个节点逐个进行访问，或查找节点，然后再进行处理。

二叉树是非线性数据结构，通过遍历可使二叉树中节点由非线性序列得到访问节点的顺序序列。也就是说，遍历操作使非线性结构线性化。

由二叉树的定义可知，二叉树由根节点、根节点的左子树和根节点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。

若以D、L、R分别表示访问根节点、遍历根节点的左子树、遍历根节点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则只有前三种方式。根据对根的访问先后顺序不同，分别称DLR为先序（根）遍历、LDR为中序（根）遍历和LRD为后序（根）遍历。

基于二叉树的递归定义，可得遍历二叉树的递归算法定义。

1.先序遍历

若二叉树为空，则为空操作，否则

（1）访问根节点；

（2）先序遍历根节点的左子树；

（3）先序遍历根节点的右子树。

先序遍历二叉树的递归算法如下。

2.中序遍历

若二叉树为空，则为空操作，否则

（1）中序遍历根节点的左子树；

（2）访问根节点；

（3）中序遍历根节点的右子树。

中序遍历二叉树的递归算法如下。

3.后序遍历

若二叉树为空，则为空操作，否则

（1）后序遍历根节点的左子树；

（2）后序遍历根节点的右子树；

（3）访问根节点。

后序遍历二叉树的递归算法如下。

4.层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对节点逐个访问。

对于如上图所示的二叉树，其先序、中序、后序、层次遍历的序列如下。

先序遍历：A、B、D、F、G、C、E；

中序遍历：B、F、D、G、A、C、E；

后序遍历：F、G、D、B、E、C、A；

层次遍历：A、B、C、D、E、F、G。

从二叉树遍历的定义可知，先序、中序和后序三种遍历算法的区别在于访问根节点和遍历左、右子树的先后关系，但都采用了递归的方法。而递归的实现，一定会采用后进先出的栈。

遍历二叉树的非递归实现

对于上图所示的二叉树，其先序、中序和后序遍历都是从根节点A开始的，且在遍历过程中经过节点的路线也是一样的，只是访问的时机不同而已。图6-14所示的从根节点左外侧开始到根节点右外侧结束的曲线为遍历二叉树的路线。沿着该路线按△标记的节点读得的序列为先序序列，按*标记读得的序列为中序序列，按#标记读得的序列为后序序列。

然而，这一路线正是从根节点开始沿左子树搜索，当搜索到最左端，无法再深入下去时，则返回，再逐一进入刚才搜索时遇到节点的右子树，再进行如此的搜索和返回，直到最后从根节点的右子树返回到根节点为止。先序遍历是在搜索时遇到节点就访问，中序遍历是在从左子树返回时遇到节点访问，后序遍历是在从右子树返回时遇到节点访问。

在这一过程中，返回节点的顺序与搜索节点的顺序相反，正好符合栈结构后进先出的特点，因此，可以利用栈将递归算法改写成非递归算法。

在沿左子树搜索时，深入一个节点入栈一个节点，若为先序遍历，则在入栈之前访问它；当沿左分支深入不下去时，则返回，即从栈中弹出前面压入的节点；若为中序遍历，则此时访问该节点，然后从该节点的右子树继续深入；若为后序遍历，则将此节点再次入栈，然后从该节点的右子树继续深入，深入一个节点入栈一个节点，深入不下去时再返回，直到第二次从栈里弹出该节点，即从右子树返回时，才访问之。

1.先序遍历的非递归实现

在下面算法中，二叉树以二叉链表存放，一维数组stack[MAXSIZE]用以实现栈，变量top用来表示当前栈顶的位置。

2.中序遍历的非递归实现

中序遍历的非递归算法实现，只需将先序遍历的非递归算法中的printf(p->data)移到p=stack[top]和p=p->rchild之间即可。

3.后序遍历的非递归实现

后序遍历非递归算法比较复杂。由于后序遍历要求左、右子树都访问完后，最后访问根节点。说明节点在第一次出栈后，还需再次入栈。也就是说，节点要入两次栈，出两次栈，而访问节点是在第二次出栈时访问。因此，为了区别同一个节点指针的两次出栈，设置一标志flag，当节点指针进、出栈时，其标志flag也同时进、出栈。

后序遍历二叉树的非递归算法如下。

在算法中，一维数组stack[MAXSIZE]用于实现栈的结构，指针变量p指向当前要处理的节点，top为栈顶指针，用来表示当前栈顶的位置。

无论是递归还是非递归遍历二叉树，由于每个节点仅被访问一次，则不论按哪一种次序进行遍历，对含n个节点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，即空间复杂度也为O(n)。

作者：有出路
链接：https://juejin.cn/post/6996949323707580447
来源：掘金