目 录
1. 树与二叉树
1.1 树的基本概念
1.1.1 树的定义
1.1.2 树的常用术语
1.2 二叉树的概述
1.2.1 基本概念
1.2.2 满二叉树定义
1.2.3 完全二叉树定义
1.2.4 单分支树的定义
1.2.5 二叉树的特性
1）特性1：i层最多结点数 2^i
2）特性2：最多结点个数 2^h-1
3）特性3：叶子结点关系 n_0 = n_2 + 1
4）特性4：深度 ?log2n? + 1
5）特性5：判断是否
1.2.6 存储结构
1）顺序存储结构
2）链式存储结构
1.3 二叉树的遍历
1.3.1 概述
1.3.2 遍历方式【重点】
1） 层次遍历
2）先根（序）遍历 DLR
3）中根（序）遍历 LDR
4）后根（序）遍历LRD
5）练习
1.3.3 遍历方式：递归实现【重点】
1）算法：先根（序）遍历 DLR
2）算法：中根（序）遍历 LDR
3）算法：后根（序）遍历LRD
4）动画演示：后根遍历
1.3.4 遍历方式：非递归实现
1）分析：先根（序）遍历 DLR
2）算法：先根（序）遍历 DLR【重点】
3）分析：中根（序）遍历 LDR
4）算法：中根（序）遍历 LDR（了解）
5）分析：后根（序）遍历LRD
6）算法：后根（序）遍历LRD（了解）
1.4 建立二叉树
1.4.1 方式
1.4.2 由先根和中根遍历序列建二叉树【重点】
1）先根和中根原理
2）实例分析
3）练习
4）算法
1.4.3 由后根和中根遍历序列建二叉树【重点】
1）后根和中根原理
2）练习
1.4.4 由标明空子树的先根遍历建立二叉树
1）概述
2）算法
1.4.5 由完全二叉树的顺序存储结构建立二叉链式存储结构
1.5 哈夫曼树及哈夫曼编码
1.5.1 基本概念
1.5.2 最优二叉树（哈夫曼树）【重点】
1.5.3 构建哈夫曼树【重点】
1.5.4 哈夫曼编码【重点】
1.5.5 哈夫曼编码类
1.6 树与森林
1.6.1 转换概述
1.6.2 树转换成二叉树
1.6.3 二叉树转换成树
1.6.4 森林与二叉树互转
1.6.5 树的存储结构
1）双亲链表存储结构
2）孩子链表存储结构
3）双亲孩子链表存储结构
4）孩子兄弟链表存储结构（重点掌握）
1.6.6 树的遍历
1）先根遍历
2）后根遍历
3）层次遍历
1.6.7 森林的遍历
1）先根遍历
2）后根遍历
3）层次遍历
后记
1. 树与二叉树
树形结构是一种非常重要的非线性结构，树形结构中数据元素之间具有一对多的逻辑关系。
1.1 树的基本概念
1.1.1 树的定义
· 树是由n(n>=0)个结点所构成的有限集合
- 当n=0时，称为空树
- 当n>0时，n个结点满足以下条件
· 有且仅有一个称为根的结点
· 其余结点可分为m个互不相交的有限集合，且每一个集合又构成一棵树，该树称为根节点的子树。
· 对于一颗非空树，其中有且仅有一个没有前驱的结点，这个结点就是根节点，其余结点有且仅有一个前驱，但可以有多个后继。
· 树的表示法：树形表示法、文氏图表示法、凹入图表示法和广义表(括号)表示法
- 树形表示法
- 文氏图表示法
- 凹入图表示法
- 广义表(括号)表示法
1.1.2 树的常用术语
1.2 二叉树的概述
1.2.1 基本概念
二叉树是一个特殊的树，每个结点最多只有两棵子树，且两棵子树也是二叉树。
精确定义：二叉树是由n（n>=0)个结点所构成的有限集合。当n=0时，这个集合为空，此时二叉树为空树，当n>0时，这个集合是由一个根结点和两个互不相交的分别称为左子树和右子树的二叉树构成。
二叉树的两棵子树有左右之分，所以二叉树是有序树。
二叉树的5种基本形态：空树、只有根结点、只有左子树、只有右子树、既有左子树又有右子树。
1.2.2 满二叉树定义
满二叉树是二叉树的一种特殊情况。
如果在一棵二叉树中，它的所有结点或者叶结点，或者是左、右子树都非空，并且所有叶结点都在同一层上，则称这棵二叉树为满二叉树。
1.2.3 完全二叉树定义
如果在一棵具有n个结点的二叉树中，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同，则称这样的二叉树为完全二叉树。
1.2.4 单分支树的定义
左支树：所有结点都没有右孩子的二叉树。
右支树：所有结点都没有左孩子的二叉树。
1.2.5 二叉树的特性
1）特性1：i层最多结点数 2^i
二叉树中第i(i>=0)层上的结点数最多为2^i
2）特性2：最多结点个数 2^h-1
深度为h(h>=1)的二叉树中最多有2^h-1个结点
3）特性3：叶子结点关系 n_0 = n_2 + 1
对于任意一颗二叉树，若其叶结点的个数为n_0，度为2的结点个数为n_2，则有n_0=n_2+1
验证1：
验证2：
证明：
4）特性4：深度 [log2n] + 1
具有n个结点的完全二叉树的深度为[log2n] + 1 或 [log2(n+1)]
数学常识
向下取整的运算称为Floor，用数学符号? ?表示；向上取整的运算称为Ceiling，用数学符号⌈ ⌉表示
例如：
⌊59/60⌋=0
⌈59/60⌉=1
⌊-59/60⌋=-1
⌈-59/60⌉=0
5）特性5：判断是否
若对含n个结点的完全二叉树从上到下且从左至右进行0至n-1的编号，则对完全二叉树中任意一个编号为1的结点有：
1. 若i=0，则该结点是二叉树的根，无双亲，否则编号为(i-1)/2的结点为其双亲结点。
2. 若2i+1>=n，则该结点无左孩子，否则，编号为2i+1的结点为其左孩子结点
3. 如果2i+2>=n，则该结点无右孩子结点，否则，编号为2i+2的结点为其右孩子结点。
1.2.6 存储结构
1）顺序存储结构
完全二叉树存储：
用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各节点元素，即将完全二叉树编号为i的结点元素存储在下标为i数组元素中。
非完全二叉树：
先在树中增加一些并不存在的虚结点并使其成为一棵完全二叉树，然后用与完全二叉树相同的方法对结点进行编号，再将编号为i的结点的值存放到数组下标为i的数组单元中，虚结点不存放任何值。
顺序存储适用于满二叉树和完全二叉树。
对于非完全二叉树来说，一个深度为h的树，需要的存储单元为2h-1，会造成空间的浪费，如：对于右支树来说，只需要h个存储单元，但是存储的时候却要使用2h-1个空间。
2）链式存储结构
二叉树的链式存储：将二叉树的各个结点随机的存放在位置任意的内存空间中，各个结点之间的逻辑关系通过指针来反映。
链式存储有2种方式：二叉链表存储结构、三叉链表存储结构。
· 二叉链表存储结构有3个域：数据域data、左孩子域lchild、右孩子域rchild
· 三叉链表存储结构有4个域：数据域data、左孩子域lchild、右孩子域rchild、父节点域parent
· 二叉链表存储结构示意图：
· 三叉链表存储结构示意图：
二叉链式存储结构是二叉树最常用的存储结构。
结点类
public class BiTreeNode {
public Object data;//数据域
public BiTreeNode lchild, rchild;//左、右孩子域
}
二叉树类
public class BiTree {
private BiTreeNode root;
//树的根节点
public BiTree() {//构建一颗空树
this.root = null;
}
public BiTree(BiTreeNode root) {//构建一棵树
this.root = root;
}
}
root.lchild = new BiTreeNode(“B”);
root.rchild = new BiTreeNode(“C”);
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;
}
