1.3 二叉树的遍历
1.3.1 概述
二叉树的遍历：沿着某条搜索路径对二叉树中的结点进行访问，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义较为广泛，例如：输出结点信息。
二叉树有3条搜索路径：
· 先上后下
· 先左后右
· 先右后左
对应3条搜索路径，二叉树有7种遍历方式：
· 先上后下
- 层次遍历
· 先左后右 （D data根、 L left左、R right 右）
- DLR （先根遍历、先序遍历、先根序遍历）
- LDR （中根遍历、中序遍历、中根序遍历）
- LRD （后根遍历、后序遍历、后根序遍历）
· 先右后左
- DRL
- RDL
- RLD
需要遍历的二叉树：
1.3.2 遍历方式【重点】
1） 层次遍历
若二叉树为空，则为空操作；否则，按自上而下先访问第0层的根节点，然后再从左到右依次访问各层次中的每一个结点。
层次遍历序列：
ABECFDGHK
2）先根（序）遍历 DLR
若二叉树为空，则为空操作，否则：
1. 访问根节点
2. 先根遍历左子树
3. 先根遍历右子树
先根遍历序列：
ABCDEFGHK
3）中根（序）遍历 LDR
若二叉树为空，则为空操作；否则：
1. 中根遍历左子树
2. 访问根节点
3. 中根遍历右子树
中根遍历序列：
BDCAEHGKF
4）后根（序）遍历LRD
若二叉树为空，则为空操作；否则：
1. 后根遍历左子树
2. 后根遍历右子树
3. 访问根节点
后根遍历序列：
DCBHKGFEA
5）练习
练习1：
先根序遍历：ABDEGCFH
中根序遍历：DBGEAFHC
后根序遍历：DGEBHFCA
练习2：
先根序遍历：ABDEGJHCFIKL
中根序遍历：DBJGEHACKILF
后根序遍历：DJGHEBKLIFCA
练习3：
先根序遍历：ABCDEFGHK
中根序遍历：BDCAEHGKF
后根序遍历：DCBHKGFEA
1.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）动画演示：后根遍历
1.3.4 遍历方式：非递归实现
1）分析：先根（序）遍历 DLR
借助一个栈来记录当前被访问结点的右孩子结点，以便遍历完一个结点的左子树后，可以继续遍历该结点的右子树。
实现思想：
1. 将根节点压栈
2. 从栈顶获得需要遍历的结点A，并访问结点A。
3. 此时结点A有左孩子直接访问，结点A有右孩子压入栈顶
4. 同时沿着左子树继续搜索，重复步骤3
5. 当左子树访问完成后，重复步骤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
借助一个栈来记录遍历过程中所经历的而未被访问的所有结点，以便遍历完左子树后能顺利的返回到它的父节点。
实现思想：
1. 从非空二叉树的根节点出发
2. 沿着该结点的左子树向下搜索，在搜索过程中将遇到的每一个结点依次压栈，直到二叉树中最左下结点压栈为止，
3. 然后从栈中弹出栈顶结点并对其进行访问，访问完成后再进入该结点的右子树，
4. 并用上述相同的方法去遍历该结点的右子树，直到二叉树中所有的结点都被访问。
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
· 借助一个栈用记载遍历过程中所经历而未被访问的所有结点。
1. 确定顶点结点是否能访问，需要知道该结点的右子树是否被遍历完成。
2. 引入两个变量，一个访问标记变量flag和一个结点指针p
- flag永不标记当前栈顶结点是否被访问
- p指向当前遍历过程中最后一个被访问的结点。
· 实现思想
1. 从非空二叉树的根节点出发
2. 将所有的左孩子相继压栈，
3. 然后获得栈中每个结点A，如果该结点A没有右孩子或右孩子已经访问过，将访问结点A
4. 如果结点A有右孩子或右孩子未被访问过，继续压栈
5. 通过标记，使程序开始出了新添加进入的结点。
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; //如果有右子树，需要重新开始
}
}
}
}
}
1.4 建立二叉树
1.4.1 方式
四种方式可以建立二叉树：
1. 由先根和中根遍历序列建二叉树
2. 由后根和中根遍历序列建二叉树
3. 由标明空子树的先根遍历建立二叉树
4. 由完全二叉树的顺序存储结构建立二叉链式存储结构
1.4.2 由先根和中根遍历序列建二叉树【重点】
1）先根和中根原理
总结：
· 通过先序遍历获得根结点（第一个结点）。
· 通过根结点在中序遍历确定左子树和右子树。
2）实例分析
3）练习
练习1：
已知二叉树，先序序列为abcdefg，中序序列为cbdaegf，重建二叉树？
练习2：
已经二叉树，前序遍历序列为{1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}，后序遍历序列是？
练习3：
已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列？
4）算法
/** 例如：new BiTree("ABDEGCFH","DBGEAFHC",0,0,8);
* @param preOrder 先序遍历序列
* @param inOrder 中序遍历序列
* @param preIndex 在preOrder中开始位置
* @param inIndex 在inOrder中开始位置
* @param count 结点数
*/
public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count) {
if(count > 0) {
//1 通过先序获得根结点
char r = preOrder.charAt(preIndex);
//2 中序中，根结点的位置
int i = 0 ;
for(; i < count ; i ++) {
if(r == inOrder.charAt(i + inIndex)) {
break;
}
}
//3 通过中序，截取左子树和右子树
root = new BiTreeNode(r);
root.lchild = new BiTree(preOrder,inOrder,preIndex+1, inIndex, i).root;
root.rchild = new BiTree(preOrder,inOrder,preIndex+1+i,inIndex + i + 1, count-i-1).root;
}
}
1.4.3 由后根和中根遍历序列建二叉树【重点】
1）后根和中根原理
总结：
· 通过后序遍历获得根结点（最后一个结点）。
· 通过根结点在中序遍历确定左子树和右子树。
2）练习
练习1：
已知二叉树，中根遍历序列为：9,3,15,20,7、后根遍历序列为：9,15,7,20,3，重建二叉树？
练习2：
已知二叉树，中根遍历序列为：6,3,4,1,5,8,2,7、后根遍历序列为：3,6,1,8,5,7,2,4，前根遍历序列？
练习3：
已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E和A B C D E F G H I，请画出该二叉树，并写出它的先根遍历的序列
1.4.4 由标明空子树的先根遍历建立二叉树
1）概述
仅使用先根遍历序列无法唯一确定一颗二叉树，例如：“AB”，B可以是左孩子，也可以是右孩子。
在先根遍历序列中加入空树信息，从而确定结点与双亲、孩子与兄弟间的关系，从而唯一确定一颗二叉树。
表名空子树的先序遍历序列：二叉树中每一个结点都必须有孩子或#
· 空树：以字符“#”表示
· 根节点A：以字符串“A##”表示
· 下图树，以字符串“AB#C##D##”表示
下图树，以字符串“ABDH#K###E##CFI###G#J##”表示：
2）算法
建立二叉链表算法分析：
若读取的字符是“#”，则建立空树；否则：
· 建立根节点
· 递归建立左子树的二叉链表
· 递归建立右子树的二叉
算法
采用先序，每一个结点都根左右
private static int index = 0; //用于记录preStr的索引值
public BiTree(String preStr) {
char c = preStr.charAt(index++);
if(c != '#') {
root = new BiTreeNode(c); //根
root.lchild = new BiTree(preStr).root; //左
root.rchild = new BiTree(preStr).root; //右
} else {
root = null;
}
}
1.4.5 由完全二叉树的顺序存储结构建立二叉链式存储结构
由二叉树的特性5可知，结点编号规则：
· 根节点的编号为0
· 编号我i的结点
- 左孩子的编号为2i+1
- 右孩子的编号为2i+2
完全二叉树及其顺序存储（层次遍历序列）
算法
public BiTreeNode createBiTree(String sqBiTree, int index) {
BiTreeNode root = null;
if(index < sqBiTree.length()) {
root = new BiTreeNode(sqBiTree.charAt(index));
root.lchild = createBiTree(sqBiTree, 2*index+1);
root.rchild = createBiTree(sqBiTree, 2*index+2);
}
return root;
}
