树和二叉树

树为非线性结构，对比线性结构来说，每一结点有多个后继结点。

1、树的定义

树(Tree) 是 n (n>0) 个结点的有限集。

• 若 n = 0，称为空树
• 若 n > 0，则它满足如下两个条件:

(1) 有且仅有一个特定的称为根(Root) 的结点

(2) 其余结点可分为 m (m > 0) 个互不相交的有限集 T1, T2, T3,…Tm，其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。

2、树的基本术语

根节点： 树中最顶层的节点，图中A为根结点，树中只有一个根节点。

结点的度：结点拥有的子树数。A 有 T1，T2，T3三个子树，A结点的度为3，B结点有E、F俩个子树，B结点的度为2。

叶子结点/终端结点：度=0的结点，也就是说该结点下没有子树。

非叶子结点/非终端结点：度！=0的结点

孩子结点、双亲结点： 一个结点下的子结点被称为孩子结点，该结点为孩子结点的双亲结点。

树的深度：树中结点的最大层次

结点的祖先： 从根到该结点所经历分支上的所有结点

结点的子孙： 以某节点为根的子树中任一结点

森林：是m（m>=0）课互不相交的树的集合

一棵树也是森林，可以看做特殊的森林。

将森林中的每棵树根结点连接起来就变成了一棵树

3、二叉树的定义

为何要重点研究每结点最多只有两个“叉” 的树?

• 二叉树的结构最简单，规律性最强
• 可以证明，所有树都能转为唯一对应的二叉树: 不失一般性

普通树(多叉树) 若不转化为二叉树，则运算很难实现，二又树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性.

二叉树是 n(n>0) 个结点的有限集，它或者是空集(n = 0)或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

二叉树的特点

1、每个结点最多有俩孩子(二叉树中不存在度大于 2 的结点）

2、子树有左右之分，其次序不能颠倒。

3、二叉树可以是空集合,根可以有空的左子树或空的右子树

注意：二叉树不是树的特殊情况，他们是俩个概念。但是树和二叉树的基本术语是通用的。

二叉树的结点的子树要区分左子树和右子树，即使只有一个子树也要进行区分，说明他是左子树还是右子树。

树当结点只有一个孩子时，无需区分他是左还是右的次序，因此俩者是不同的。

【思考】

具有3个结点的二叉树可能有几种不同形态?普通树呢?

二叉树的5种基本形态

4、二叉树的性质和存储结构

（1）性质1：在二叉树的第 i 层上至多有 2^i-1 个结点（i>=1）, 至少有1个结点

（2）性质2： 深度为 k 的二叉树至多有 2^k -1个结点，至少有 k 个结点

（3）性质3： 对于一棵二叉树，如果其叶子结点数为 n₀ , 度 为2的结点数为 n₂ , 则有： n₀ = n₂ + 1

5、满二叉树、完全二叉树

（1）满二叉树

一棵树深度为k且有 2^k -1 个结点的二叉树称为满二叉树

特点

1、每一层上结点数都是最大结点数

2、所有的叶子结点都在最后一层

（2）完全二叉树

深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满

二又树中编号为 1~n 的结点一一对应时，称之为完全二叉树。

非完全二叉树中的F结点的位置对应满二叉树的G，因此不是完全二叉树

注: 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树. 一定是连续的去掉!!!

特点

1、叶子结点只可能分布在层次最大的俩层上。

2、对于任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为 i 或者 i + 1

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

完全二叉树的性质

如下图共有 12 个结点，log₂12 ≈ 3，因此层数为 4

下图中就可以直观的看出，各节点之间的关系：

6、二叉树的存储

顺序存储结构

实现: 按满二叉树的结点层次编号，依次存放二叉树中的数据元素

【举例说明】

1、将下面的二叉树按顺序结构存储

没有元素的位置在数组中也要空出来。

2、若某二叉树采用顺序结构存储，如下图所示，还原出二叉树

顺序存储结构的缺点：

当二叉树中有非常多的空结点时，这些空结点需要在数组中存储空或者0，因此空间的利用率不高，浪费空间。因此顺序存储比较适合满二叉树和完全二叉树

链式存储结构

使用俩个指针分别指向该结点的左孩子结点和右孩子结点。如果没有左孩子或者右孩子则置为空。

【案例演示】

^ 表示空指针域

【思考】

在 n 个结点的二叉链表中，有多少个空指针域？

乍一看好像也没有什么规律，我们可以试着反推以下，有n个结点，必然有 2n 个链域，其中除了头结点外, 每个结点必然有一个双亲，必然有一个指针存放双亲结点，因此非空的链域有 n-1 ， 2n - （n-1）= n + 1 ，因此在n个结点的二叉链表中有 n + 1个空指针域

【三叉链表】

相较于二叉链表，多了一个指针域，用于存储双亲结点

7、遍历二叉树演示

遍历的定义

遍历定义一 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次 (又称周游)

“访问”的含义很广，可以是对结点作各种处理，如: 输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

遍历的目的

得到树中所有结点的一个线性排列

遍历方法

无论二叉树多么复杂，都可以将它看成三部分。

因此根据访问顺序的不同，就有了不同的遍历方式，如下：

假设：L遍历左子树、D：访问根节点、R：遍历右子树

整个二叉树的遍历方案：

DLR、LDR、LRD、DRL、RDL、RLD【重点研究前三种】

【先序遍历演示】

若差二叉树为空，则无需操作，否则：

（1）访问根节点

（2）先序遍历左子树

（3）先序遍历右子树

（1）先遍历根结点A

（2）子树不为空，左子树的根节点为B，遍历B结点，B的左右子树为空，左子树遍历完毕

（3）找到A的右子树，A的右子树的根节点为C，遍历C，C的左右子树为空，终止遍历。

最终结果：ABC

以下先序遍历结果：ABELDHMIJ

【中序遍历演示】

若差二叉树为空，则无需操作，否则：

（1）中序遍历左子树

（2）访问根节点

（3）中序遍历右子树

（1）找到A的左子树B，B的左子树为空，遍历左子树根结点B，B的右子树为空，左子树B遍历完毕

（2）遍历根节点A

（3）找到A的右子树C，C的左子树为空，遍历右子树的根节点C，C的右子树为空，右子树C遍历完毕

最终结果：BAC

以下按照中序遍历结果：ELBAMHIDJ

【后序遍历演示】

若差二叉树为空，则无需操作，否则：

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根节点

（1）找到A的左子树B，B的左右子树为空，遍历左子树根结点B，左子树B遍历完毕

（2）找到A的右子树C，C的左右子树为空，遍历右子树根结点C，右子树C遍历完毕

（3）访问根节点A

最终遍历结果：BCA

以下二叉树遍历结果：LEBMIHJDA

【根据遍历序列确定二叉树】

• 若二叉树中各结点的值均不相同，则二叉树结点的先序序列，中序序列和后序序列都是唯一的。
• 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一颗二叉树

【举例说明一】

已知二叉树的先序和中序序列，构造出相应的二叉树

先序: A B C DEFG HIJ

中序: C D B FE A IHGJ

由先序序列确定根；由中序序列确定左右子树

1、由先序知根为A，则由中序知左子树为CDBFE， 右子树为IHGJ

2、再分别在左、右子树的序列中找出根、左子树序列、右子树序列

在先序得知左子树的根为B，在中序遍历中得知 CD为左子树，FE为右子树

同样，G为右子树的根，中序得知IH为左子树，J为右子树

3、由先序得知C是根，D在C的右边，D是C的右子树。同样，E为根，F为左子树。H为根，I为左子树

【举例说明二】

中序序列: BDCEAFHG

后序序列: DECBHGFA，请画出这棵二叉树

分析

1、由后序遍历得知，A为整棵树的根。由中序遍历得知，根结点A左边的为左子树，右边的为右子树。

2、看 BDCE 左子树，同样的方法，由后序遍历得知B为左子树根结点，在由中序遍历得知 DCE为B的右子树。DCE同样用此方法，C为根结点，D为子树，E为右子树

3、A的右子树用相同方法求出

8、二叉树相关算法

（1）遍历二叉树递归算法实现

【先序遍历】

先序遍历的顺序：（1）遍历根结点 （2）遍历左子树 （3）遍历右子树

二叉树的每个结点都可以有左子树和右子树，这种类似的结构可以采用递归的方式。可以先把整棵树分解开来，即对左子树和右子树先序遍历：

（1）若根结点不为空，遍历根结点

（2）若左子树不为空，遍历左子树

（3）若右子树不为空，遍历右子树

代码实现

public class PreOrderTraverse {
    public static void main(String[] args) {
        // 创建二叉树
        TreeNode root = new TreeNode("A");
        TreeNode left = new TreeNode("B");
        TreeNode right = new TreeNode("C");
        root.left = left;
        root.right = right;

        // 先序遍历
        root.preOrder(root);
    }
}
//  定义树的结点信息
class TreeNode{
    Object data;// data域
    TreeNode left; // 左结点
    TreeNode right; // 右结点

    // 初始化
    public TreeNode(Object data) {
        this.data = data;
        left = null;
        right = null;
    }

    /**
     * 先序遍历
     * */
    public void preOrder(TreeNode root){
        // 若根结点为空则停止递归
        if (root == null) return;
        // 先遍历根结点
        System.out.println(root.data);
        // 遍历左子树
        preOrder(root.left);
        // 遍历右子树
        preOrder(root.right);
    }
}

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

【中序遍历】

中序遍历顺序：

（1）若左子树不为空，遍历左子树

（2）若根结点不为空，遍历根结点

（3）若右子树不为空，遍历右子树

    /**
     * 中序遍历
     * */
    public void inOrder(TreeNode root){
        // 若根结点为空则停止递归
        if (root == null) return;
        // 遍历左子树
        preOrder(root.left);
        // 先遍历根结点
        System.out.println(root.data);
        // 遍历右子树
        preOrder(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

【后序遍历】

后序遍历顺序：

（1）若左子树不为空，遍历左子树

（2）若右子树不为空，遍历右子树

（3）若根结点不为空，遍历根结点

    /**
     * 后序遍历
     * */
    public void postOrder(TreeNode root){
        // 若根结点为空则停止递归
        if (root == null) return;
        // 遍历左子树
        preOrder(root.left);
        // 遍历右子树
        preOrder(root.right);
        // 先遍历根结点
        System.out.println(root.data);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

【分析】

如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同

从图中可以看到，每个结点都被经过3次，第一次访问就是先序遍历，第二次访问就是中序遍历，第三次访问就是后序遍历。

时间效率：O(n) 每个结点都被访问一次

空间效率：O(n) 栈占用的最大辅助空间

（2）遍历二叉树非递归算法实现

利用栈实现非递归遍历二叉树，以中序遍历为例。

基本思想：

（1）建立一个栈

（2）将根结点入栈，如果左子树不为空，遍历左子树

（3）如果左子树为空，弹出根结点，遍历右子树

演示

1、根结点不为空，将根结点A入栈

2、访问左子树，同样将左子树的根结点B入栈

3、访问B的左子树，发现为空，则弹栈B输出。接着访问B的右子树，同样将右子树的根结点D入栈

4、访问D的左子树为空，则弹栈D并输出，右子树也为空

5、左子树访问完毕，弹栈A输出。接着访问右子树，同样将右子树根结点C入栈

6、结点 C 左子树为空，弹栈C输出。此时C结点的右子树为空，栈为空。访问完毕。

代码实现

    /**
     * 非递归中序遍历
     * */
    public void traverse(TreeNode node){
        // 初始化栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = node;
        while(p != null || !stack.isEmpty()) {
            if (p == null) {   
                // 左子树为空,弹栈并输出
                TreeNode pop = stack.pop();
                System.out.println(pop.data);
                // 遍历右子树
                p = pop.right;
            }else {
                // 压栈根结点
                stack.push(p);
                // 右子树为空
                p = p.left;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（3）二叉树的建立

【以先序遍历序列为例】

例如：已知先序序列为：ABCDEGF

• 从键盘输入二叉树的结点信息，建立二叉树的存储结构
• 在建立二叉树的过程中按照二叉树的先序方式建立

如果只根据先序序列建立二叉树，所得到的二叉树是不唯一的。

如果想得到一颗唯一的树，需要给树补充一些空结点。

假设空结点用 # 标识，则上图中的先序序列为： ABC##DE#G##F###

此时通过这个序列就能创建出一颗唯一的二叉树！

代码实现

public class BinaryTreeCreate {
    public static void main(String[] args) {
        String preorder = "A,B,C,#,#,D,E,#,G,#,#,F,#,#,#";
        BinaryTreeCreate builder = new BinaryTreeCreate();
        TreeNode root = builder.buildTreeHelper(preorder.split(","));

        root.preOrder(root);
    }

    int index = 0;
    // 通过先序遍历建立二叉树
    public TreeNode buildTreeHelper(String[] nodes){
        if (index >= nodes.length || nodes[index].equals("#")) {
            index++; // 移动索引
            return null;
        }

        String value = nodes[index];
        index++; // 移动索引

        TreeNode node = new TreeNode(value);
        // 建立左子树
        node.left = buildTreeHelper(nodes);
        // 建立右子树
        node.right = buildTreeHelper(nodes);

        return node;
    }
}

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

（4）复制二叉树

【算法步骤】

• 如果是空树，递归结束
• 否则，复制根节点
  • 递归复制左子树
  • 递归复制右子树

public class BinaryTreeCreate {
    public static void main(String[] args) {
        BinaryTreeCreate builder = new BinaryTreeCreate();


        // 先建立一个二叉树
        // 创建原始二叉树
        TreeNode originalRoot = new TreeNode(1);
        originalRoot.left = new TreeNode(2);
        originalRoot.right = new TreeNode(3);
        originalRoot.left.left = new TreeNode(4);
        originalRoot.left.right = new TreeNode(5);

        System.out.println("按照先序遍历序列为：12453" );

        TreeNode newNode = builder.copyTree(originalRoot);
        newNode.preOrder(newNode);
    }

    // 复制二叉树
    public TreeNode copyTree(TreeNode node){
        if (node == null) return  null;
        // 复制根结点
        TreeNode treeNode = new TreeNode(node.data);
        // 复制左子树
        treeNode.left = copyTree(node.left);
        // 复制右子树
        treeNode.right = copyTree(node.right);

        // 返回新的二叉树
        return treeNode;
    }
}

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

（5）计算二叉树的深度

• 如果是空树，则深度为0
• 否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大值+1

    // 计算二叉树的深度
    public int deep(TreeNode node) {
        if (node == null) return 0;
        // 递归计算左子树
        int m = deep(node.left);
        // 递归计算右子树
        int n = deep(node.right);
        // +1 == 》根结点的层数
        return  m > n ? (m+1) : (n+1);
    }
1
2
3
4
5
6
7
8
9
10

（6）计算二叉树结点总数

• 如果是空树，则结点个数为0
• 否则： 左子树结点个数+右子树结点个数+1

    // 计算二叉树结点的个数
    public int treeNodeCount(TreeNode node) {
        if (node == null) return 0;
        int m = treeNodeCount(node.left);
        int n = treeNodeCount(node.right);

        return m + n + 1;
    }
1
2
3
4
5
6
7
8

（7）计算二叉树所有叶子结点

• 如果是空树，则叶子结点个数为0;
• 否则，为左子树的叶子结点个数+右子树的叶子结点个数

判断叶子节点的方法：根结点的左右子树都为空

    // 计算二叉树叶子节点个数
    public int leafCount(TreeNode node) {
        if (node == null) return 0;
        if (node.left ==  null && node.right == null) return 1;
        int m = leafCount(node.left);
        int n = leafCount(node.right);

        return m + n ;
    }
1
2
3
4
5
6
7
8
9

9、线索二叉树

为什么要研究线索二叉树呢？

当用二叉链表作为二叉树的存储结构时可以很方便地找到某个结点的左右孩

子，但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结

点。

解决方法

• 通过遍历寻找——浪费时间
• 在增加俩个指针，前驱节点和后驱节点——浪费空间
• 利用二叉树中的空指针域

具有 n 个结点的二叉树，有 n+1 个空指针域，我们可以利用这些空指针域存储结点的前驱和后驱节点：

• 如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱

• 如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继

这种改变指向的指针称为“线索”

如下图：

A的右指针为空，理应存储A的后继，但是A是最后一个结点，因此不用存储

C的右指针为空，存储后继结点B

E的左指针为空，存储前驱结点 B

G的左右指针都为空，左指针存储E，右指针存储D

在之前链式二叉树有俩个指针，分别指向左孩子和有孩子，线索二叉树中为了区分指针到底是指向前驱和后继，还是指向左右孩子，因此在增加俩个标志域 ltag、rtag：

ltag = 0 ，lchild 指向该结点的左孩子
ltag = 1，lchild 指向该结点的前驱
rtag = 0，rchild 指向该结点的右孩子
rtag = 1，rchild 指向该结点的后继

【案例演示】

根结点A有左右孩子结点，正常存储即可。

B的左孩子结点为空，因此： ltag = 1，lchild = A

C的左右孩子结点为空，因此 ltag = 1，lchild = C，rtag=1，rchild=D

D的右孩子为空，rtag =1，rchild = E

E的左右孩子结点为空，因此 ltag = 1，lchild =D，rtag=1，rchild=null

10、树和森林

（1）树的存储结构

双亲表示法

实现: 定义结构数组存放树的结点每个结点含两个域:

• 数据域: 存放结点本身信息
• 双亲域: 指示本结点的双亲结点在数组中的位置

对应的二叉树：

特点：找双亲结点容易，但是找孩子难

孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储。

则 n 个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的数组）存储。

孩子链表的类型表示：

// 孩子存储结构
class ChildNode{
    // 孩子结点的下标
    int childIndex;
    // 下一个孩子的地址
    ChildNode nextChild;
}
// 双亲存储结构
class ParentNode {
    // data域
    Object data;
    // 第一个孩子
    ChildNode firstChild;
}

// 树的存储结构
class CtTre{
    // 保存双亲结点的数组
    ParentNode[] nodes;
    // 根结点的下标，结点总数
    int r,n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

特点：找到孩子结点容易，找双亲难。

但是我们可以将 双亲表示法和孩子链表结合起来，在双亲存储结构中增加一个指针用于指向该结点的双亲结点的下标位置：

// 孩子存储结构
class ChildNode{
    // 孩子结点的下标
    int childIndex;
    // 下一个孩子的地址
    ChildNode nextChild;
}
// 双亲存储结构
class ParentNode {
    // data域
    Object data;
    // 双亲的索引下标
    int parentIndex;
    // 第一个孩子
    ChildNode firstChild;
}

// 树的存储结构
class CtTre{
    // 保存双亲结点的数组
    ParentNode[] nodes;
    // 根结点的下标，结点总数
    int r,n;
}

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

孩子兄弟表示法

又叫 二叉树表示法，二叉链表表示法

实现:用二又链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

与二叉树的区别：树没有左右孩子之分

（2）树和二叉树的转换

由于树和又树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系

给定一棵树，可以找到唯一的一棵二叉树与之对应。

在图中可以发现，在树中兄弟结点之间并没有连线，而孩子的兄弟结点在二叉树中都变为了 右孩子结点。并没孩子的兄弟结点没有了和根结点的连接。

树和二叉树转换的步骤：

（1）加线: 在兄弟之间加连线

（2） 抹线: 对每个结点，除了其左孩子外，去除其与其余孩子之间的关系

（3）旋转: 以树的根结点为轴心，将整树顺时针转45

兄弟相连留长子

二叉树转换成树的步骤

（1） 加线: 若p结点是双亲结点的左孩子，则将p的右孩子，右孩的右孩子…沿分支找到的所有右孩子，都与p的双亲用线连起来

（2）抹线: 抹掉原二叉树中双亲与右孩子之间的连线调整

（3）将结点按层次排列，形成树结构

左孩右右连双亲，去掉原来右孩线。

（3）森林与二叉树的转换

森林转换二叉树

（1）将各棵树分别转换成二叉树
（2）将每棵树的根结点用线相连
（3）以第一棵树根结点为二叉树的根再以根结点为轴心，顺时针旋转
构成二叉树型结构

树变二叉根相连

二叉树转换成森林

（1）抹线: 将二又树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

（2）还原: 将孤立的二又树还原成树

去掉全部右孩线，孤立二叉在还原

（4）树和森林的遍历

树的遍历方式：

森林的遍历

将森林看作由三部分构成

• 森林中第一棵树的根结点
• 森林中第一棵树的子树森林
• 森林中其它树构成的森林。

先序遍历

中序遍历

【例子】

11、哈夫曼树

哈夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，在实际中有广泛的用途。

哈夫曼树的定义，涉及路径、路径长度、权等概念，下面先给出这些概念的定义，然后再介绍哈夫曼树。

路径: 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

结点的路径长度: 两结点间路径上的分支数

树的路径长度：从树根到每一结点的路径长度之和。

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，路径最短的二叉树不一定是完全二叉树

权(weight): 将树中结点赋给一个有着某种含义的数值则这个数值称为该结点的权

结点的带权路径长度 ：从根结点到该结点之间的路径长度与该结点的权的乘积

树的带权路径长度： 树中所有叶子结点的带权路径长度之和。通常记作：

【举例说明】

例: 有4 个结点 a，b,c, d，权值分别为 7,5,2,4 ,构造以此4个结点为叶子结点的二叉树.

求该二叉树的带权路径长度： WPL = $2\ast 7+2\ast 5+2\ast 4+2\ast 4=36$

第二种构造方法：WPL = $2\ast 4+3\ast 7+3\ast 5+2=46$

构造不同的二叉树它的带权路径是不一样的，哈夫曼树也称最优树，带权路径（WPL）最短的树。

带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

（1）哈夫曼树的构造算法

构造哈夫曼树的方法：

(1) 根据n个给定的权值 {w1，w2… w3} 构成n棵二叉树的森林 F={T1，T2，…Tn}，其中Ti只有一个带权为 wi，的根结点.。【构造森林全是根】

(2) 在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。【选用两小造新树】

(3) 在F中删除这两棵树，同时将新得到的二又树加入森林中【删除两小添新人】

(4) 重复(2)和(3)，直到森林中只有一棵树为止，这棵树即为哈夫曼树

【举例说明】

有四个结点 a、b、c、d，权值分别为7、5、2、4，构造哈夫曼树

1、构造4个以a、b、c、d结点为根的树

2、选取权值最小的俩个结点 2、4构造一颗新树

3、此时有7、5、6三棵树，继续选取权值最小的树构造新树，直到剩下一棵树

总结

包含 n 个叶子结点的哈夫曼树中共有2n- 1 个结点。

哈夫曼树的结点的度数为 0或2，没有度为 1 的结点。

包含n棵树的森林要经过 n-1 次合并才能形成哈夫曼树，共产生 n-1 个新结点

（2）哈夫曼树的实现

使用一维结构数组存储哈夫曼树的结点，定义四个变量，分别表示：权值、双亲结点下标、左右孩子结点下标

初始化

根据权值构造n个为根节点的树，没有双亲结点和左右孩子结点。

初始化时请注意,对于结构型的数组，不赋值默认为null

class HuffmanNode {
    int weight; // 权值
    int lchild; // 左孩子
    int rchild; // 右孩子结点下标
    int parent; // 双亲结点的下标

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "weight=" + weight +
                ", lchild=" + lchild +
                ", rchild=" + rchild +
                ", parent=" + parent +
                '}';
    }
}

class HuffmanTree {
    HuffmanNode[] ht;
    // 初始化 weights==>权重集合
    public HuffmanTree(int[] weights) {
        // 权重的个数
        int n = weights.length;
        ht = new HuffmanNode[2*n - 1];
        // 设置0~n个元素的权重
        for (int i = 0; i < n; i++) {
            HuffmanNode node = new HuffmanNode();
            node.weight = weights[i];
            node.parent = node.lchild = node.rchild = 0;
            ht[i] = node;
        }
        // n~2*n-1初始化对象
        for (int i = n; i < ht.length; i++) {
            ht[i] = new HuffmanNode();
        }

    }
}
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

假设给定权值为：7, 19, 2, 6, 32, 3, 21, 10

初始化后：

初始化完毕，开始将俩个结点进行合并，从下标 i = weights.length 开始，直到 2n-1：

• 从weights数组中选取俩个从未选中的（parent=0）并且权重最小的。假设 s1，s2
• 修改俩个较小结点的双亲结点：ht[s1].parent = i、ht[s2].parent = i
• 修改新产生的结点：ht[i].weight = ht[s1].weight + ht[s2].weight、ht[i].lchild= s1、ht[i].rchild= s2

  public void createHuffmanTree(int[] weights) {
        for (int i = weights.length; i < 2 * weights.length - 1; i++) {
            // 获取俩个最小权重的结点下标
            List<Integer> list = getMinNode();
            System.out.println(list);
            Integer first = list.get(0);
            Integer second = list.get(1);
            // 更新俩个结点的双亲下标
            ht[first].parent = i;
            ht[second].parent = i;
            // 设置新生成的结点
            ht[i].weight = ht[first].weight + ht[second].weight;
            ht[i].lchild = first;
            ht[i].rchild = second;
        }

    }


    public List<Integer> getMinNode() {
        ArrayList<Integer> list = new ArrayList<>();
        // 假设俩个最小值
        int firstMinValue = Integer.MAX_VALUE;
        int secondMinValue = Integer.MAX_VALUE;
        // 最小值的下标
        int firstIndex = -1;
        int secondIndex = -1;
        for (int i = 0; i < ht.length; i++) {
            if (ht[i].parent == 0 && ht[i].weight != 0) {
                if (ht[i].weight < firstMinValue) {
                    secondMinValue = firstMinValue; // 更新第二个最小值
                    secondIndex = firstIndex;
                    firstMinValue = ht[i].weight;  // 更新第一个最小值
                    firstIndex = i;
                } else if (ht[i].weight < secondMinValue) {
                    secondMinValue = ht[i].weight;
                    secondIndex = i;
                }
            }
        }
        list.add(firstIndex);
        list.add(secondIndex);
        return list;
    }
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