二叉树的深度优先遍历、广度优先遍历和非递归遍历(转）

二叉树的深度优先遍历、广度优先遍历和非递归遍历

二叉树的遍历：

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

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

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

深度优先遍历二叉树。

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

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

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

    访问根结点；

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

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

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

    访问根结点；

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

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

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

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

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

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

    访问根结点。



广度优先遍历二叉树。

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

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

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

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

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

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

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

    6结束。



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

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

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

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

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

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

----------------------------------------------------------------------

    图的深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。
    图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。