二叉树的深度优先和广度优先遍历

蔚落 2021-06-24 13:59 389阅读 0赞

图的深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

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

深度优先遍历分为三种：前序,中序,后序。

首先我们知道，前序遍历的规则是：

根结点→左子结点→右子结点   
中序遍历是：左子结点→根结点→右子结点   
后序遍历是：左子结点→右子结点→根结点

已知某二叉树的前序是abdgcefh，中序dgbaechf，则后序是？  
那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结点，即根结点是a。   
在中序遍历的顺序dgbaechf中，以a分成左、右两边，左边是dgb，右边是echf。   
  
所以，这棵树现在可以确定如下：   
a   
/ \\   
dgb echf   
  
接下来再分别对左子树和右子树进行类似的操作。   
对于左子树dgb来说，在前序遍历abdgcefh中找到bdg，证明这子树的根是b，那么现在可以确定的树结构如下：   
a   
/ \\   
b echf   
/   
dg   
  
再看dg，前序遍历中的顺序为dg，所以d是dg这部分子树的根，那么又因为中序遍历的dg顺序也是dg，所以g是右子结点。   
即：   
a   
/ \\   
b echf   
/   
d   
\\   
g   
  
现在看echf这部分子树，前序中顺序是cefh，所以子树根结点是c，那么左子结点是e，右子树是hf：   
得到：   
a   
/ \\   
b c   
/ / \\   
d e hf   
\\   
g   
  
最后只剩下hf部分了，前序遍历中是fh，所以根是f，那么h就是左子结点。   
现在得到了整棵树：   
a   
/ \\   
b c   
/ / \\   
d e f   
\\ /   
g h   
  
对这棵树再进行后序遍历就行了，结果就是：DGEBHFCA

A   
    
      B         C   
  
D        E         F  
  
      G          H