文章目录
5.3 二叉树的遍历
5.3.1 概述
二叉树的遍历：沿着某条搜索路径对二叉树中的结点进行访问，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义较为广泛，例如：输出结点信息。
二叉树有3条搜索路径：
先上后下
先左后右
先右后左
对应3条搜索路径，二叉树有7种遍历方式：
先上后下
层次遍历
先左后右 （D data根、 L left左、R right 右）
DLR （先根遍历、先序遍历、先根序遍历）
LDR （中根遍历、中序遍历、中根序遍历）
LRD （后根遍历、后序遍历、后根序遍历）
先右后左
DRL
RDL
RLD
需要遍历的二叉树
A
B
C
D
E
F
G
H
K
5.3.2 遍历方式【重点】
1） 层次遍历
若二叉树为空，则为空操作；否则，按自上而下先访问第0层的根节点，然后再从左到右依次访问各层次中的每一个结点。
层次遍历序列
ABECFDGHK
2）先根（序）遍历 DLR
若二叉树为空，则为空操作，否则
访问根节点
先根遍历左子树
先根遍历右子树
先根遍历序列
ABCDEFGHK
3）中根（序）遍历 LDR
若二叉树为空，则为空操作；否则
中根遍历左子树
访问根节点
中根遍历右子树
中根遍历序列
BDCAEHGKF
4）后根（序）遍历LRD
若二叉树为空，则为空操作；否则
后根遍历左子树
后根遍历右子树
访问根节点
后根遍历序列
DCBHKGFEA
5）练习
练习1：
先根序遍历：ABDEGCFH
中根序遍历：DBGEAFHC
后根序遍历：DGEBHFCA
练习2：
先根序遍历：ABDEGJHCFIKL
中根序遍历：DBJGEHACKILF
后根序遍历：DJGHEBKLIFCA
练习3：
先根序遍历：ABCDEFGHK
中根序遍历：BDCAEHGKF
后根序遍历：DCBHKGFEA
5.3.3 遍历方式：递归实现【重点】
1）算法：先根（序）遍历 DLR
public void preRootTraverse(BiTreeNode T) {
if(T != null) {
System.out.print(T.data); //输出根元素
preRootTraverse(T.lchild); //先根遍历左子树
preRootTraverse(T.rchild); //先根遍历右子树
}
}2）算法：中根（序）遍历 LDR
public void inRootTraverse(BiTreeNode T) {
if(T != null) {
inRootTraverse(T.lchild); //中根遍历处理左子树
System.out.print(T.data); //访问根节点
inRootTraverse(T.rchild); //中根遍历处理右子树
}
}3）算法：后根（序）遍历LRD
public void postRootTraverse(BiTreeNode T) {
if(T != null) {
postRootTraverse(T.lchild); //后根遍历左子树
postRootTraverse(T.rchild); //后根遍历右子树
System.out.print(T.data); //访问根结点
}
}4）动画演示：后根遍历
5.3.4 遍历方式：非递归实现
1）分析：先根（序）遍历 DLR
借助一个==栈==来记录当前被访问结点的右孩子结点，以便遍历完一个结点的左子树后，可以继续遍历该结点的右子树。
实现思想：
将根节点压栈
从栈顶获得需要遍历的结点A，并访问结点A。
此时结点A有左孩子直接访问，结点A有右孩子压入栈顶
同时沿着左子树继续搜索，重复步骤3
当左子树访问完成后，重复步骤2依次访问对应的右子树
2）算法：先根（序）遍历 DLR【重点】
public void preRootTraverse() {
BiTreeNode T = root;
if( T != null ) {
LinkStack S = new LinkStack(); // 创建栈记录没有访问过的右子树
S.push(T); // 将根节点压入栈顶
while(!S.isEmpty()) { // 栈中只要有数据，表示继续遍历
T = S.pop(); // 弹出栈顶数据
System.out.print(T.data); // 结点被访问
while(T != null) { // T指针，访问每一个左孩子
if(T.lchild != null) { // 输出左孩子
System.out.print(T.lchild.data);
}
if(T.rchild != null) { // 将右孩子压栈
T.push(T.rchild);
}
T = T.lchild; // 访问下一个左孩子
}
}
}
}3）分析：中根（序）遍历 LDR
借助一个==栈==来记录遍历过程中所经历的而未被访问的所有结点，以便遍历完左子树后能顺利的返回到它的父节点。
实现思想
从非空二叉树的根节点出发
沿着该结点的左子树向下搜索，在搜索过程中将遇到的每一个结点依次压栈，直到二叉树中最左下结点压栈为止，
然后从栈中弹出栈顶结点并对其进行访问，访问完成后再进入该结点的右子树，
并用上述相同的方法去遍历该结点的右子树，直到二叉树中所有的结点都被访问。
4）算法：中根（序）遍历 LDR
public void inRootTraverse() {
BiTreeNode T = root;
if(T != null) {
LinkStack S = new LinkStack();
S.push(T); //将根节点压入到栈顶
while( !S.isEmpty() ) { //栈中有数据，表示遍历未完成
//1 将所有的左孩子压栈
while(S.peek() != null) { //栈顶的元素不为空，注意：不是弹栈
// 获得栈顶，
BiTreeNode temp = (BiTreeNode)S.peek();
// 并将左孩子压入栈顶
S.push(temp.lchild);
}
S.pop(); //将栈顶的空元素弹出
//2 依次弹出栈，访问当前节点，如果有右孩子继续压栈
if(! S.isEmpty()) {
T = (BiTreeNode)S.pop();
System.out.print(T.data); //访问栈顶
S.push(T.rchild);
}
}
}
}5）分析：后根（序）遍历LRD
借助一个栈用记载遍历过程中所经历而未被访问的所有结点。
确定顶点结点是否能访问，需要知道该结点的右子树是否被遍历完成。
引入两个变量，一个访问标记变量flag和一个结点指针p
flag永不标记当前栈顶结点是否被访问
p指向当前遍历过程中最后一个被访问的结点。
实现思想
从非空二叉树的根节点出发
将所有的左孩子相继压栈，
然后获得栈中每个结点A，如果该结点A没有右孩子或右孩子已经访问过，将访问结点A
如果结点A有右孩子或右孩子未被访问过，继续压栈
通过标记，使程序开始出了新添加进入的结点。
6）算法：后根（序）遍历LRD
public void postRootTraverse() {
BiTreeNode T = root;
if( T != null) {
LinkStack S = new LinkStack();
S.push(T);
// 声明两个变量
Boolean flag; //用于记录是否被访问
BiTreeNode p; //用于记录上一次处理的结点
while(! S.isEmpty() ) {
//1 将所有的左孩子压栈
while(S.peek() != null) { //栈顶的元素不为空，注意：不是弹栈
// 获得栈顶，
BiTreeNode temp = (BiTreeNode)S.peek();
// 并将左孩子压入栈顶
S.push(temp.lchild);
}
S.pop(); //将栈顶的空元素弹出
while( !S.isEmpty() ) {
T = (BiTreeNode) S.peek();
if(T.rchild == null || T.rchild == p) { // 没有右孩子 或 已经访问过
System.out.print(T.data);
S.pop(); //弹出
p = T; //记录刚才访问过的
flag = true; //没有新元素，继续访问
} else {
S.push(T.rchlid);
flag = false; //新右子树添加
}
if(!flag) {
break; //如果有右子树，需要重新开始
}
}
}
}
}