数据结构与算法——树与二叉树篇详解_树和二叉树

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

i 层 0 1 2 3 4 5 ⋯ i 最多结点数 2 0 2 1 2 2 2 3 2 4 2 5 ⋯ 2 i 最多结点数 1 2 4 8 16 32 ⋯ 2 i (i层最多结点数)

$$\begin{array}{c|cc} \hline i层&0&1&2&3&4&5&\cdots&i\\ \hline 最多结点数&2^0&2^1&2^2&2^3&2^4&2^5&\cdots&2^i\\ \hline 最多结点数&1&2&4&8&16&32&\cdots&2^i\\ \hline \end{array}$$ \tag{i层最多结点数} i层最多结点数最多结点数​0201​1212​2224​3238​42416​52532​⋯⋯⋯​i2i2i​​(i层最多结点数)

2）特性2：最多结点个数 2^h-1

• 深度为h(h>=1)的二叉树中最多有2^h-1个结点

$$\begin{gathered} S_n=a_1+a_2+a_3+\cdots +a_{n-1}+a_n \\ {S}_n=a_1+a_{1}q+a_1{q}^2+\cdots +a_1{q}^{n-2}+a_1{q}^{n-1} \\ q{S}_n=a_{1}q+a_1{q}^2+a_1{q}^3+\cdots +a_1{q}^{n-1}+a_1{q}^n \\ {S}_n-q{S}_n=a_1-a_1{q}^n \\ {S}_n=\frac{a_1-a_1{q}^n}{1-q} \\ {S}_n=\frac{a_1(1-q^n)}{1-q}\text{\hspace{1em}(等比数列求和)} \end{gathered}$$

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)⌋
  $$h=\lfloor lo{g}_{2}n\rfloor +1\text{\hspace{1em}()}$$

数的深度 取值 公式 l o g 2 n 的值 ⌊ l o g 2 n ⌋ 的值 3 4 ≤ n < 8 2 2 ≤ n < 2 3 2 ≤ l o g 2 n < 3 2 4 8 ≤ n < 16 2 3 ≤ n < 2 4 3 ≤ l o g 2 n < 4 3 5 16 ≤ n < 32 2 4 ≤ n < 2 5 4 ≤ l o g 2 n < 5 4 6 32 ≤ n < 64 2 5 ≤ n < 2 6 5 ≤ l o g 2 n < 6 5 h 2 h − 1 ≤ n < 2 h h − 1 ≤ l o g 2 n < h h − 1 ( )

$$\begin{array}{c|c|c} \hline 数的深度 &取值&公式&log_2n的值 & ⌊log2n⌋的值\\ \hline 3& 4 \le n \lt 8& 2^2 \le n \lt 2^3 & 2 \le log_2n \lt 3 & 2 \\ \hline 4& 8 \le n \lt 16& 2^3 \le n \lt 2^4 & 3 \le log_2n \lt 4 & 3 \\ \hline 5& 16 \le n \lt 32& 2^4 \le n \lt 2^5 & 4 \le log_2n \lt 5 & 4 \\ \hline 6& 32 \le n \lt 64& 2^5 \le n \lt 2^6 & 5 \le log_2n \lt 6 & 5 \\ \hline h& & 2^{h-1} \le n \lt 2^h & h-1 \le log_2n \lt h & h-1 \\ \hline \end{array}$$ \tag{} 数的深度3456h​取值4≤n<88≤n<1616≤n<3232≤n<64​公式22≤n<2323≤n<2424≤n<2525≤n<262h−1≤n<2h​log2​n的值2≤log2​n<33≤log2​n<44≤log2​n<55≤log2​n<6h−1≤log2​n<h​⌊log2n⌋的值2345h−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的结点为其右孩子结点。

序号 i 结论 5.1 双亲节点 i − 1 2 个数 n 2 i + 1 结论 5.2 左孩子 2 i + 2 结论 5.3 ：右孩子 5 5 − 1 2 = 2 7 11 无 12 无 3 3 − 1 2 = 1 8 7 2 × 3 + 1 = 7 8 无 4 4 − 1 2 = 1 11 9 2 × 4 + 1 = 9 10 2 × 4 + 2 = 10 ( )

$$\begin{array}{c|c|c} \hline 序号i& 结论5.1双亲节点 \frac{i-1}{2} & 个数n & 2i+1 & 结论5.2左孩子 & 2i+2 & 结论5.3：右孩子 \\ \hline 5 & \frac{5-1}{2}=2 & 7 & 11 & 无 & 12 & 无\\ \hline 3 & \frac{3-1}{2}=1 & 8 & 7 & 2×3+1 =7 & 8 & 无\\ \hline 4 & \frac{4-1}{2}=1 & 11 & 9 & 2×4+1=9 & 10 & 2×4+2=10\\ \hline \end{array}$$ \tag{} 序号i534​结论5.1双亲节点2i−1​25−1​=223−1​=124−1​=1​个数n7811​2i+11179​结论5.2左孩子无2×3+1=72×4+1=9​2i+212810​结论5.3：右孩子无无2×4+2=10​​()

1.2.6 存储结构

1）顺序存储结构

• 完全二叉树存储：

  用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各节点元素，即将完全二叉树编号为i的结点元素存储在下标为i数组元素中。

  

• 非完全二叉树：

  先在树中增加一些并不存在的虚结点并使其成为一棵完全二叉树，然后用与完全二叉树相同的方法对结点进行编号，再将编号为i的结点的值存放到数组下标为i的数组单元中，虚结点不存放任何值。

  

• 顺序存储适用于满二叉树和完全二叉树。

• 对于非完全二叉树来说，一个深度为h的树，需要的存储单元为2^{h-1，会造成空间的浪费，如：对于右支树来说，只需要h个存储单元，但是存储的时候却要使用2}h-1个空间。

2）链式存储结构

• 二叉树的链式存储：将二叉树的各个结点随机的存放在位置任意的内存空间中，各个结点之间的逻辑关系通过指针来反映。

• 链式存储有2种方式：二叉链表存储结构、三叉链表存储结构

  • 二叉链表存储结构有3个域：数据域data、左孩子域lchild、右孩子域rchild

    

  • 三叉链表存储结构有4个域：数据域data、左孩子域lchild、右孩子域rchild、父节点域parent

    

• 二叉链表存储结构示意图

  

• 三叉链表存储结构示意图

  

• 二叉链式存储结构是二叉树最常用的存储结构。

  • 结点类

    public class BiTreeNode {
        public Object data;					//数据域
        public BiTreeNode lchild, rchild;	//左、右孩子域
    }
    1
    2
    3
    4

  • 二叉树类

    public class BiTree {
        private BiTreeNode root;	
        //树的根节点
        public BiTree() {					//构建一颗空树
            this.root = null;
        }
        public BiTree(BiTreeNode root) {	//构建一棵树
            this.root = root;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

    root.lchild = new BiTreeNode(“B”);

    root.rchild = new BiTreeNode(“C”);

1.3 二叉树的遍历

1.3.1 概述

• 二叉树的遍历：沿着某条搜索路径对二叉树中的结点进行访问，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义较为广泛，例如：输出结点信息。

• 二叉树有3条搜索路径：

  1. 先上后下
  2. 先左后右
  3. 先右后左

• 对应3条搜索路径，二叉树有7种遍历方式：

  • 先上后下
    1. 层次遍历
  • 先左后右 （D data根、 L left左、R right 右）
    2. DLR （先根遍历、先序遍历、先根序遍历）
    2. LDR （中根遍历、中序遍历、中根序遍历）
    2. LRD （后根遍历、后序遍历、后根序遍历）
  • 先右后左
    5. DRL
    5. RDL
    5. 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);		//先根遍历右子树
    }
}
1
2
3
4
5
6
7

2）算法：中根（序）遍历 LDR

public void inRootTraverse(BiTreeNode T) {
    if(T != null) {
        inRootTraverse(T.lchild);		//中根遍历处理左子树
        System.out.print(T.data);		//访问根节点
        inRootTraverse(T.rchild);		//中根遍历处理右子树
    }
}
1
2
3
4
5
6
7

3）算法：后根（序）遍历LRD

public void postRootTraverse(BiTreeNode T) {
    if(T != null) {
        postRootTraverse(T.lchild);		//后根遍历左子树
        postRootTraverse(T.rchild);		//后根遍历右子树
        System.out.print(T.data);		//访问根结点
    }
}
1
2
3
4
5
6
7

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;				// 访问下一个左孩子
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5）分析：后根（序）遍历LRD

• 借助一个栈用记载遍历过程中所经历而未被访问的所有结点。
  • 确定顶点结点是否能访问，需要知道该结点的右子树是否被遍历完成。
  • 引入两个变量，一个访问标记变量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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

1.4 建立二叉树

1.4.1 方式

• 四种方式可以建立二叉树
  1. 由先根和中根遍历序列建二叉树
  2. 由后根和中根遍历序列建二叉树
  3. 由标明空子树的先根遍历建立二叉树
  4. 由完全二叉树的顺序存储结构建立二叉链式存储结构

1.4.2 由先根和中根遍历序列建二叉树【重点】

1）先根和中根原理

图一 图二 图三 图四 图五 先序遍历 A B C A B C A B C A B C A B C 中序遍历 B A C C B A B C A A C B A B C 特点 B C 不同左分支 B C 相同右分支 ( )

$$\begin{array}{c|c|c} \hline &图一&图二&图三&图四&图五\\ \hline 先序遍历&ABC&ABC&ABC&ABC&ABC\\ \hline 中序遍历&BAC&CBA&BCA&ACB&ABC\\ \hline 特点&&BC不同左分支&BC相同右分支\\ \hline \end{array}$$ \tag{} 先序遍历中序遍历特点​图一ABCBAC​图二ABCCBABC不同左分支​图三ABCBCABC相同右分支​图四ABCACB​图五ABCABC​​()

• 总结：
  • 通过先序遍历获得根结点（第一个结点）。
  • 通过根结点在中序遍历确定左子树和右子树。

2）实例分析

3）练习

• 练习1：

  已知二叉树，先序序列为abcdefg，中序序列为cbdaegf，重建二叉树？
  1

  

• 练习2：

  已经二叉树，前序遍历序列为{1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}，后序遍历序列是？
  1

  

• 练习3：

  已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列？
  1

  

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.4.3 由后根和中根遍历序列建二叉树【重点】

1）后根和中根原理

图一 图二 图三 图四 图五 中序遍历 B A C C B A B C A A C B A B C 后序遍历 B C A C B A C B A C B A C B A 特点 C B 相同左分支 B C 不同右分支 ( )

$$\begin{array}{c|c|c} \hline &图一&图二&图三&图四&图五\\ \hline 中序遍历&BAC&CBA&BCA&ACB&ABC\\ \hline 后序遍历&BCA&CBA&CBA&CBA&CBA\\ \hline 特点&&CB相同左分支&BC不同右分支\\ \hline \end{array}$$ \tag{} 中序遍历后序遍历特点​图一BACBCA​图二CBACBACB相同左分支​图三BCACBABC不同右分支​图四ACBCBA​图五ABCCBA​​()

总结：

• 通过后序遍历获得根结点（最后一个结点）。
• 通过根结点在中序遍历确定左子树和右子树。

2）练习

• 练习1：

  已知二叉树，中根遍历序列为：9,3,15,20,7、后根遍历序列为：9,15,7,20,3，重建二叉树？
  
  1
  2

• 练习2：

  已知二叉树，中根遍历序列为：6,3,4,1,5,8,2,7、后根遍历序列为：3,6,1,8,5,7,2,4，前根遍历序列？
  
  
  1
  2
  3

• 练习3：

  已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E和A B C D E F G H I，请画出该二叉树，并写出它的先根遍历的序列
  
  1
  2

  

1.4.4 由标明空子树的先根遍历建立二叉树

1）概述

• 仅使用先根遍历序列无法唯一确定一颗二叉树，例如：“AB”，B可以是左孩子，也可以是右孩子。

• 在先根遍历序列中加入空树信息，从而确定结点与双亲、孩子与兄弟间的关系，从而唯一确定一颗二叉树。

• 表名空子树的先序遍历序列：二叉树中每一个结点都必须有孩子或#

  • 空树：以字符“#”表示

  • 根节点A：以字符串“A##”表示

  • 下图树，以字符串“AB#C##D##”表示

    

  • 下图树，以字符串“ABDH#K###E##CFI###G#J##”表示

    

2）算法

• 建立二叉链表算法分析：

  • 若读取的字符是“#”，则建立空树；否则
  1. 建立根节点
  2. 递归建立左子树的二叉链表
  3. 递归建立右子树的二叉

• 算法

  • 采用先序，每一个结点都根左右

  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
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

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;
}
1
2
3
4
5
6
7
8
9

1.5 哈夫曼树及哈夫曼编码

1.5.1 基本概念

• 结点间路径：从一个结点到另一个结点所经历的结点和分支序列。
• 结点的路径长度：从根节点到该结点的路径上分支的数目。
• 结点的权：在实际应用中，人们往往会给树中的每一个结点赋予一个具有某种实际意义的数值，这个数值被称为该结点的权值。
• 结点的带权路径长度：该结点的路径长度与该结点的权值的乘积。
• 树的带权路径长度：树中所有叶结点的带权路径长度之和。

1.5.2 最优二叉树（哈夫曼树）【重点】

• 给定n个权值并作为n个叶结点，按一定规则构造一颗二叉树，使其带权路径长度达到最小值，则这棵二叉树被称为最优二叉树，也称为哈夫曼树。

$$\begin{gathered} (a)WPL=5\times 3+4\times 3+3\times 2+2\times 2+1\times 2=39 \\ (b)WPL=5\times 2+4\times 2+3\times 3+2\times 3+1\times 2=35 \\ (c)WPL=5\times 2+4\times 2+3\times 2+2\times 3+1\times 3=33 \\ \text{\hspace{1em}(带权路径长度)} \end{gathered}$$

• 同一组数据的最优二叉树不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。 构建哈夫曼树的时候即可以推导出。

1.5.3 构建哈夫曼树【重点】

( 1 ) 由已知给定的 n 个权值 { w 1 , w 2 , w 3 , . . . , w n } ，构建一个有 n 棵二叉树所构建的森林 F = { T 1 , T 2 , T 3 , . . . T n } ，其中每一棵二叉树中只含一个带权值为 w i 根节点，其左、右子树为空 ( 2 ) 在二叉树森林 F 中选取根节点的权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树 去构建一颗新二叉树，新二叉树的根节点权值为其左右子树根节点的权值之和。 ( 3 ) 作为新二叉树的左右子树的这两棵二叉树从森林 F 中删除，同时加入刚生成的新二叉树 ( 4 ) 重复步骤 ( 2 ) 和 ( 3 ) ，直到森林 F 中只剩一颗二叉树为止，该二叉树就是哈夫曼树。 (1)由已知给定的n个权值\{w_1,w_2,w_3,...,w_n\}，构建一个有n棵二叉树所构建的森林 \\ F=\{T_1,T_2,T_3,...T_n\}，其中每一棵二叉树中只含一个带权值为w_i根节点，其左、右子树为空\\ \\ (2)在二叉树森林F中选取根节点的权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树\\ 去构建一颗新二叉树，新二叉树的根节点权值为其左右子树根节点的权值之和。 \\ \\ (3)作为新二叉树的左右子树的这两棵二叉树从森林F中删除，同时加入刚生成的新二叉树 \\ \\ (4)重复步骤(2)和(3)，直到森林F中只剩一颗二叉树为止，该二叉树就是哈夫曼树。 \\ (1)由已知给定的n个权值{w1​,w2​,w3​,...,wn​}，构建一个有n棵二叉树所构建的森林F={T1​,T2​,T3​,...Tn​}，其中每一棵二叉树中只含一个带权值为wi​根节点，其左、右子树为空(2)在二叉树森林F中选取根节点的权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树去构建一颗新二叉树，新二叉树的根节点权值为其左右子树根节点的权值之和。(3)作为新二叉树的左右子树的这两棵二叉树从森林F中删除，同时加入刚生成的新二叉树(4)重复步骤(2)和(3)，直到森林F中只剩一颗二叉树为止，该二叉树就是哈夫曼树。

• 练习：

  有5个带权结点 {A,B,C,D,E}，其权值分别为W={10,30,40,15,6}，权值作为结点数据，绘制一颗哈夫曼

1.5.4 哈夫曼编码【重点】

• 编码诉求：对字符集进行二进制编码，使得信息的传输量最小。如果能对每一个字符用不同的长度的二进制编码，并且尽可能减少出现次数最多的字符的编码位数，则信息传送的总长度便可以达到最小。

• 哈夫曼编码：用电文中各个字符使用的频度作为叶结点的权，构造一颗具有最小带权路径长度的哈夫曼树，若对树中的每个左分支赋予标记0，右分支赋予标记1，则从根节点到每个叶结点的路径上的标记连接起来就构成一个二进制串，该二进制串被称为哈夫曼编码。

• 练习：p176

  已知在一个信息通信联络中使用了8个字符：a、b、c、d、e、f、g和h，每个字符的使用频度分别为：6、30、8、9、15、24、4、12，试设计各个字符的哈夫曼编码。
  1

• 哈夫曼树进行译码

  • 哈夫曼编码是一种前缀码，任何一个字符的编码都不是同一个字符集中另一个字符的编码的前缀。
  • 译码过程时编码过程的逆过程。从哈夫曼树的根开始，从左到右把二进制编码的每一位进行判别，若遇到0，则选择左分支走向下一个结点；若遇到1，则选择右分支走向下一个结点，直至到达一个树叶结点，便求得响应字符。

• 练习

  有5个带权结点 {A,B,C,D,E}，其权值分别为W={10,30,40,15,6}，权值作为结点数据，绘制一颗哈夫曼，并编写哈夫曼编码
  1

  

  A：1111

  B：10

  C：0

  D：110

  E：1110

  编码：编码字符串 AABBEDCC–>111111111010111011000

1.5.5 哈夫曼编码类

• n个权值，组成哈夫曼树节点个数：2n-1

• 哈夫曼结点类

  public class HuffmanNode {
  
      public int weight;// 权值
      public int flag; // 节点是否加入哈夫曼树的标志
      public HuffmanNode parent,lchild,rchild; // 父节点及左右孩子节点
  
      // 构造一个空节点
      public HuffmanNode(){
          this(0);
      }
  
      // 构造一个具有权值的节点
      public HuffmanNode(int weight){
          this.weight = weight;
          flag=0;
          parent=lchild=rchild=null;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

• 哈夫曼编码类

  public class HuffmanTree {
      // 求哈夫曼编码的算法，w存放n个字符的权值(均>0)
      public int[][] huffmanCoding(int[] W){
          int n = W.length;  // 字符个数
          int m = 2*n -1;   //哈夫曼树的节点数
          // 构造n个具有权值的节点
          HuffmanNode[] HN = new HuffmanNode[m];
          int i = 0;
          for (; i<n ; i++) {
              HN[i] = new HuffmanNode(W[i]);
          }
          // 创建哈夫曼树
          for (i = n;  i<m ; i++) {
              // 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2
              HuffmanNode min1 = selectMin(HN,i-1);
              min1.flag = 1;
              HuffmanNode min2 = selectMin(HN,i-1);
              min2.flag = 1;
              // 构造 min1和min2的父节点，并修改父节点的权值
              HN[i] = new HuffmanNode();
              min1.parent=HN[i];
              min2.parent=HN[i];
              HN[i].lchild = min1;
              HN[i].rchild = min2;
              HN[i].weight = min1.weight+min2.weight;
          }
          //  从叶子到根 逆向求每个字符的哈夫曼编码
          int[][] HuffCode = new int[n][n]; // 分配n个字符编码存储空间
          for (int j =0;j<n;j++){
              // 编码的开始位置，初始化为数组的结尾
              int start = n-1;
              // 从叶子节点到根，逆向求编码
              for(HuffmanNode c = HN[j],p=c.parent;p!=null;c=p,p=p.parent){
                  if(p.lchild.equals(c)){
                      HuffCode[j][start--]=0;
                  }else{
                      HuffCode[j][start--]=1;
                  }
              }
              // 编码的开始标志为-1，编码是-1之后的01序列
              HuffCode[j][start] = -1;
  
          }
  
          return HuffCode;
  
      }
  
      // 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2
      private HuffmanNode selectMin(HuffmanNode[] HN, int end) {
          // 求 不在哈夫曼树中， weight最小值的那个节点
          HuffmanNode min = HN[end];
          for (int i = 0; i < end; i++) {
              HuffmanNode h = HN[i];
              // 不在哈夫曼树中， weight最小值
              if(h.flag == 0 && h.weight<min.weight){
                  min = h;
              }
          }
          return min;
      }
  
  
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64

• 哈夫曼编码会用类似如下格式进行存储

  

• 测试类

  public class Demo02 {
  
      public static void main(String[] args) {
          // 一组权值
          int[] W = {6,30,8,9,15,24,4,12};
          // 创建哈夫曼树
          HuffmanTree tree = new HuffmanTree();
          // 求哈夫曼编码
          int[][] HN = tree.huffmanCoding(W);
          //打印编码
          System.out.println("哈夫曼编码是： ");
          for (int i = 0; i < HN.length; i++) {
              System.out.print(W[i]+" ");
              for (int j = 0; j < HN[i].length; j++) {
                  if(HN[i][j] == -1){
                      for (int k = j+1; k <HN[i].length ; k++) {
                          System.out.print(HN[i][k]);
                      }
                      break;
                  }
              }
              System.out.println();
          }
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

1.6 树与森林

1.6.1 转换概述

• 树与二叉树之间、森林与二叉树之间可以相互转换，而且这种转换是一一对应的。

1.6.2 树转换成二叉树

• 树转换成二叉树可归纳3步骤：加线、删线、旋转

  1. 加线：将树中所有相邻的兄弟之间加一条连线。
  2. 删线：对树中的每一个结点，只保留它与第1个孩子结点之间的连线，删去它与其他孩子结点之间的连线。
  3. 旋转：以树的根结点为轴心，将树平面顺时针旋转一定角度并做适当的调整，使得转化后所得二叉树看起来比较规整。

• 由树转换成的二叉树永远是一棵根结点的右子树为空的二叉树。

1.6.3 二叉树转换成树

• 二叉树转换成树是树转换二叉树的逆过程。

• 树转换成二叉树可归纳3步骤：加线、删线、旋转

  1. 加线：若某结点是双亲结点的左孩子，则将该结点沿着右分支向下的所有结点与该结点的双亲结点用线连接。
  2. 删除：将树中所有双亲结点与右孩子结点的连线删除。
  3. 旋转：对经过（1）、（2）粮补后所得的树以根结点为轴心，按逆时针方向旋转一定的角度，并做适当调整，使得转化后所得的树看起来比较规整。

1.6.4 森林与二叉树互转

• 森林是由若干树组成，任何一棵树和树对应的二叉树其右子树一定是空的。

• 根据这个规律可以得到森林转化成二叉树的方法：

  1. 将森林中每棵树转化成二叉树。
  2. 按照森林的先后顺序，将一颗二叉树视为前一棵二叉树的右子树依次链接起来，从而构成一颗二叉树

• 将二叉树转化成森林正好是这个过程相反。

1.6.5 树的存储结构

• 树的4种链式存放方式：
  1. 双亲链表存储结构
  2. 孩子链表存储结构
  3. 双亲孩子链表存储结构
  4. 孩子兄弟链表存储结构（重点掌握）

1）双亲链表存储结构

• 以一组地址连续的存储单元存放树中的各个结点，每个结点有两个域：
  • 数据域：用于存放树中该结点的值。
  • 指针域：用于存放该结点的双亲结点在存储结构中的位置。

• 优点：查找一个指定结点的双亲结点非常容易。
• 缺点：查找指定结点的孩子结点，需要扫描整个链表。

2）孩子链表存储结构

• 以一组地址连续的存储单元来存放树中的各个结点，每一个结点有两个域
  • 数据域：存放该结点的值
  • 指针域：用于存放该结点的孩子链表的头指针。

• 优点：便于实现查找树中指定结点的孩子结点
• 缺点：不便于查找指定结点的双亲结点

3）双亲孩子链表存储结构

• 与孩子链表存储结构类似，以一组地址连续的存储单元来存放树中的各个结点，每一个结点有三个域
  • 数据域：存放该结点的值
  • 父指针域：用于存放双亲结点在数组中的位置
  • 子指针域：用于存放该结点的孩子链表的头指针。

4）孩子兄弟链表存储结构（重点掌握）

• 孩子兄弟链表存放，又称为“左子/右兄”二叉链式存储结构。
  • 左指针：指向该结点的第一个孩子
  • 右指针：指向该结点的右邻兄弟

• 结点类

  public class CSTreeNode {
      public Object data;							//结点的数据域
      publicCSTreeNode firstChild, nextsibling;	//左孩子、右兄弟
  }
  1
  2
  3
  4

1.6.6 树的遍历

• 树的遍历主要有：先根遍历、后根遍历、层次遍历。

1）先根遍历

• 若树为非空，则
  1. 访问根节点
  2. 从左到右依次先根遍历根节点的每一颗子树。

先根遍历序列：

ABEFCDGHIJK

public void preRootTraverse(CSTreeNode T) {
    if(T != null) {
        System.out.print(T.data);
        preRootTraverse(T.firstChild);	//先根遍历树中根节点的第一个子树
        preRootTraverse(T.nextsibling);	//先根遍历树中根节点的其他子树
    }
}
1
2
3
4
5
6
7

2）后根遍历

• 若树为非空，则
  1. 从左到右依次后根遍历根节点的每一棵子树
  2. 访问根节点

后根遍历序列：

EFBCIJKHGDA

• 使用孩子兄弟链表存储的树，与遍历二叉树的中序序列相同

public void postRootTraverse(CSTreeNode t) {
    if(T != null) {
        postRootTraverse(T.firstChild);		//后根遍历树中根节点的第一个子树
        System.out.print(T.data);			//访问数的根节点
        postRootTraverse(T.nextsibling);	//后根遍历树中根节点的其他子树
    }
}
1
2
3
4
5
6
7

3）层次遍历

• 若树为非空，则从根节点开始，从上到下依次访问每一层的各个结点，在同一层中的结点，则按从左到右的顺序依次进行访问。

ABCDEFGHIJK

public void levelTraverse(CSTreeNode T) {
    if(T != null) {
        LinkQueue L = new LinkQueue();		//构建队列
        L.offer(T);							//根节点入队列
        while(!L.isEmpty()) {			//队列不为空，处理根结点和左孩子
            for(T = L.poll() ; T != null ; T = T.nextsibling) {//依次处理兄弟(右子树)
                System.out.print(T.data + " ");
                if(T.firstChild != null) {	//第一个孩子结点非空入队列
                    L.offer(T.firstchild);
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.6.7 森林的遍历

• 森林由3部分组成：
  1. 森林中第一棵树的根节点
  2. 森林中第一棵树的子树森林
  3. 森林中其他树构成的森林。
• 森林的3中遍历：
  1. 先根遍历
  2. 后根遍历
  3. 层次遍历

1）先根遍历

• 若森林不空，则可依下列次序进行遍历
  1. 访问森林中第一棵树的根节点
  2. 先序遍历第一课树中的子树森林
  3. 先序遍历除去第一棵树之后剩余的树构成的森林。
• 也就是说：依次从左到右对森林中的每一颗树进行先根遍历。

先跟遍历顺序是：

ABCEDFGHIJKL

2）后根遍历

• 若森林不空，则可依下列次序进行遍历
  1. 后根遍历第一棵树中的子树森林
  2. 访问森林中第一棵树的根节点
  3. 后根遍历除去第一棵树之后剩余的树构成的森林。
• 也就是说：依次从左至右对森林中的每一棵树进行后根遍历。

后根遍历序列是：

BECDAGFIKLJH

4）层次遍历

• 若森林为非空，则按从左到右的顺序对森林中每一颗树进行层次遍历。
• 也就是说：依次从左至右对森林中的每一棵树进行层次遍历。

层次遍历序列：

ABCDEFGHIJKL

=========================================================

后记

好啦，以上就是本期全部内容，能看到这里的人呀，都是能人。

十年修得同船渡，大家一起点关注。

我是♚焕蓝·未来，感谢各位【能人】的：点赞、收藏和评论，我们下期见！

各位能人们的支持就是♚焕蓝·未来前进的巨大动力~

注：如果本篇Blog有任何错误和建议，欢迎能人们留言！