数据结构 - 二叉树的遍历

二叉树的遍历

N：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。

给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树。

二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

深度优先遍历二叉树

1. 中序遍历（LNR）的递归算法：

若二叉树为空，则算法结束；否则：

中序遍历根结点的左子树；

访问根结点；

中序遍历根结点的右子树。

2. 前序遍历（NLR）的递归算法：

若二叉树为空，则算法结束，否则：

访问根结点；

前序遍历根结点的左子树；

前序遍历根结点的右子树。

3. 后序遍历（LRN）的递归算法：

若二叉树为空，则算法结束，否则：

后序遍历根结点的左子树；

后序遍历根结点的右子树；

访问根结点。

非递归深度优先遍历二叉树

栈是实现递归最常用的结构，利用一个栈来记下尚待遍历的结点或子树，以备以后访问，可以将递归的深度优先遍历改为非递归的算法。

1. 非递归前序遍历：遇到一个结点，就访问该结点，并把此结点推入栈中，然后下降去遍历它的左子树。遍历完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。

2. 非递归中序遍历：遇到一个结点，就把它推入栈中，并去遍历它的左子树。遍历完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去遍历该结点的右子树。

3. 非递归后序遍历：遇到一个结点，把它推入栈中，遍历它的左子树。遍历结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去遍历该结点的右子树。遍历完右子树后才能从栈顶托出该结点并访问之。另外，还需要给栈中的每个元素加上一个特征位，以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的（则要继续遍历右子树），还是从右边回来的（则该结点的左、右子树均已遍历）。特征为Left表示已进入该结点的左子树，将从左边回来；特征为Right表示已进入该结点的右子树，将从右边回来。

非递归广度优先遍历二叉树

非递归广度优先遍历二叉树（层序遍历）是用队列来实现的。从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。算法如下：

1. 初始化一个队列，并把根结点入队列；

2. 当队列为非空时，循环执行步骤3到步骤5，否则执行6；

3. 出队列取得一个结点，访问该结点；

4. 若该结点的左子树为非空，则将该结点的左子树入队列；

5. 若该结点的右子树为非空，则将该结点的右子树入队列；

6. 结束。