树，二叉树，哈夫曼树...

今天药忘吃喽~ 2023-10-03 11:03 35阅读 0赞

### 写在前面 ###

之前讲的链表，栈，队列等都是线性存储结构，都是**一对一**的关系。而树是具有**一对多**关系的数据结构。比如我们经常说的湖北省武汉市，湖南长沙的一个类图，就类似于一颗倒转的树。

![fbb3a88a6f05126f86f7f40c26a9241c.png][]

### 什么是树 ###

**树是一种数据结构，由n个节点构成的具有层次关系的有限集合。**

![image-20210713224114989][]

#### 树的基本术语 ####

**节点**：树中的每一个数据元素都是节点（A，B…）

**节点的度**：节点的子树个数（A的子树为B和C）

**树的度**：树中所有节点最大的度（树A和树C的度都是2）

**叶子节点**：度为0的节点（D，E，F）

**节点的层次**：树的根开始，树根所在的层为第一层，根的子节点所在的层为第二层（A第一层，BC第二层）

**有序树和无序树**：子树有左右顺序之分 （如左边的小于右边），反之则为无序树

#### 树的特点 ####

1.  子树是不相交的
2.  除了根节点之外，每个节点有且只有一个父节点
3.  一个又N个节点构成的树只有N-1条边

### 什么是二叉树 ###

树中的节点的度不超过2的有序树。

![image-20210713230407488][]

**二叉树的特点：**

1.  二叉树中，第i层的节点数最多为2i-1
2.  深度为k的二叉树最多有2k\-1个节点
3.  对于任意二叉树，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2\+1，
    
    即度为0的节点n0，永远比度为2的节点 n2多一个。
    
    ![若排版问题可看图][45f1ebb3a28fc78d2afada1ec2f570fa.png]
    
    证明：设度为0的节点有n0个，度为1的节点为n1，度为2的节点为n2，共计n个节点,
    
    因为二叉树的所有节点的度数均不大于2，所以：
    
    n = n0 \+ n1 \+ n2 ①
    
    又因为0度的节点没有孩子，1度的节点有一个孩子，2度的节点有2个孩子，所以孩子总数为：
    
    0 \* n0 \+ 1 \* n1 \+ 2 \* n2，此外，根节点（第一层的节点）不是任何节点的孩子，所以
    
    总节点数 = 孩子总数 + 根节点，即
    
    n = n1 \+ 2n2 \+ 1 ②
    
    ② - ①化简得
    
    n0 = n2 \+ 1

### 满二叉树 ###

**二叉树中除了叶子节点，每个节点的度都为2，则此二叉树为满二叉树。**

具有 n 个节点的满二叉树的深度为: log2(n+1)

![image-20210714002538228][]

### 完全二叉树 ###

**一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树**。叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

![image-20210714003735456][]

### 哈夫曼树(最优二叉树) ###

若给定一个二叉树如下：

![image-20210714135953216][]

**路径**：在一棵树中，一个节点到另一个节点之间的通路，称为路径。如上图中的根节点到a之间的通路。

**路径长度**：在一条路径中，每经过一个节点，路径长度就加1。如上图根节点到节点c的路径长度为3。

**节点的权**：每个节点赋予一个新的数值。如a的权为7，b的权为5。

**节点的带权路劲长度**：从根结点到该结点之间的**路径长度**与该**结点的权**的**乘积**。如b的带权路径长度为2\*5=10。

**树的带权路径长度**：树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。如图中所示的这颗树的带权路径长度为：WPL = 7 \* 1 + 5 \* 2 + 2 \* 3 + 4 \* 3

#### 什么是哈夫曼树 ####

**构造一棵二叉树（每个节点都是叶子结点且都有各自的权值），该树的带权路径长度达到最小，称为最优二叉树，也称为哈夫曼树(Huffman Tree)**

#### 编码问题 ####

场景：给定一段字符串，包含58个字符，且由以下7个字符构成:a,b,c,d,e,f,g，这7个字符出现的频次不同，如何对这7个字符进行编码如何对字符串进行编码，可以使得该字符串的编码存储空间最少？

![image-20210714141834626][]

如果用标准的等长ASCII编码：58 × 8 = 464位

#### 用二叉树进行编码 ####

若用0和1表示左右分支，取出上面4个频次最高的字符，可以得到如下一棵树：

![image-20210714143322940][]

![image-20210714150513498][]

由上图可知，编码为0100可表示的字符就有3种可能的情况，因此，上面节点的分布具有**二义性**。如何避免二义性？只需要让每个节点都是叶子节点即可。

![image-20210714152035199][]

#### 哈夫曼树图示构造 ####

通过上面的方式，我们把上面的字符按频次依次两两组合，且都为叶子节点。最后构造图示如下：

![image-20210714230327864][]

因此，我们发现每个节点都是叶子节点，字符最后的编码为：

![image-20210714230617039][]

所以，编码长度为：

10x3 + 15x2 + 12x2 + 3x5 + 4x4 + 13x2 + 1x5 = 146位

#### 代码构造 ####

public class HuffmanTree {
    
        //节点
        public static class Node<E> {
            //数据，如a,b,c,d。。。
            E data;
            //权重
            int weight;
            //左子节点
            Node leftChild;
            //you子节点
            Node rightChild;
    
            public Node(E data, int weight) {
                this.data = data;
                this.weight = weight;
            }
    		
            public String toString() {
                return "Node[" + weight + ",data=" + data + "]";
            }
        }
    
        public static Node createHuffmanTree(List<Node> nodeList) {
            //当节点大于1时
            while (nodeList.size() > 1) {
                //先对list中根据权重排序
                sort(nodeList);
                //排序之后第一个节点就是权重最小的节点，第二个节点就是权重第二小的节点
                Node left = nodeList.get(0);
                Node right = nodeList.get(1);
                //生成一个新的父节点，类似于步骤1,但父节点没有数据只有权值
                Node<Node> parent = new Node<>(null, left.weight + right.weight);
                //子节点和父节点链接
                parent.leftChild = left;
                parent.rightChild = right;
                //删除最小的节点
                nodeList.remove(0);
                //删除第二小的
                nodeList.remove(0);
                //添加到list中
                nodeList.add(parent);
            }
            //最后返回根节点一棵树
            return nodeList.get(0);
        }
    
        /**
         * 冒牌排序
         *
         * @param nodeList
         */
        public static void sort(List<Node> nodeList) {
            if (nodeList.size() <= 1) {
                return;
            }
            for (int i = 0; i < nodeList.size(); i++) {
                for (int j = 0; j < nodeList.size() - 1; j++) {
                    //前面的数大于后面的数就交换
                    if (nodeList.get(j + 1).weight < nodeList.get(j).weight) {
                        Node temp = nodeList.get(j + 1);
                        nodeList.set(j + 1, nodeList.get(j));
                        nodeList.set(j, temp);
                    }
                }
            }
        }
    
        /**
         * 打印哈夫曼树，先左后右
         * 即从根节点开始先打印出子节点的左节点，在打印右节点
         * @param root 根节点的树
         */
        public static void printTree(Node root) {
            if (root.leftChild != null) {
                System.out.println("左子节点：" + root.leftChild);
                printTree(root.leftChild);
            }
            if (root.rightChild != null) {
                System.out.println("右子节点：" + root.rightChild);
                printTree(root.rightChild);
            }
        }
    
    
        //测试
        public static void main(String[] args) {
            List<Node> nodes = new ArrayList<Node>();
            //把节点加入至list中
            nodes.add(new Node("a", 10));
            nodes.add(new Node("b", 15));
            nodes.add(new Node("c", 12));
            nodes.add(new Node("d", 3));
            nodes.add(new Node("e", 4));
            nodes.add(new Node("f", 13));
            nodes.add(new Node("g", 1));
            Node root = createHuffmanTree(nodes);
            printTree(root);
        }
    }

测试结果

左子节点：Node[25,data=null]
    左子节点：Node[12,data=c]
    右子节点：Node[13,data=f]
    右子节点：Node[33,data=null]
    左子节点：Node[15,data=b]
    右子节点：Node[18,data=null]
    左子节点：Node[8,data=null]
    左子节点：Node[4,data=e]
    右子节点：Node[4,data=null]
    左子节点：Node[1,data=g]
    右子节点：Node[3,data=d]
    右子节点：Node[10,data=a]

### 总结 ###

本章主要是对树有基础的概念，了解常见的树的特点，后面会继续讲到二叉排序树，二叉平衡树等,数据结构相对来说是比较枯燥的，但是坚持下去会有收获的，不管是对算法还是看源码都有很大提升。

### 参考 ###

*  [数据结构树，树存储结构详解][Link 1]

[fbb3a88a6f05126f86f7f40c26a9241c.png]: https://img-blog.csdnimg.cn/img_convert/fbb3a88a6f05126f86f7f40c26a9241c.png
[image-20210713224114989]: https://img-blog.csdnimg.cn/img_convert/7a47a81e7084a0357b651be3aac09cf3.png
[image-20210713230407488]: https://img-blog.csdnimg.cn/img_convert/8cfdb5403e06b905982f50763b8a0f6f.png
[45f1ebb3a28fc78d2afada1ec2f570fa.png]: https://img-blog.csdnimg.cn/img_convert/45f1ebb3a28fc78d2afada1ec2f570fa.png
[image-20210714002538228]: https://img-blog.csdnimg.cn/img_convert/6067f70cdc8f6f132f2baa76f56ef5ec.png
[image-20210714003735456]: https://img-blog.csdnimg.cn/img_convert/9fd523fca9ec465d7cd35aac74b10846.png
[image-20210714135953216]: https://img-blog.csdnimg.cn/img_convert/a0babf18210dee13a1f9ddb8cbc809d5.png
[image-20210714141834626]: https://img-blog.csdnimg.cn/img_convert/8f60aa32f7eec3fca4abd3578fa93d37.png
[image-20210714143322940]: https://img-blog.csdnimg.cn/img_convert/9d04de08382b2adb49e6b6d9ef444a61.png
[image-20210714150513498]: https://img-blog.csdnimg.cn/img_convert/8e4389b0abac159cc67c362a8c6b2e17.png
[image-20210714152035199]: https://img-blog.csdnimg.cn/img_convert/bb52a0f2595feab1e49b73b8f535b3ca.png
[image-20210714230327864]: https://img-blog.csdnimg.cn/img_convert/3b7caf3c0169d761eeca1b0f160c0e8a.png
[image-20210714230617039]: https://img-blog.csdnimg.cn/img_convert/26d4ac322d4f074289b7e7b57610d97a.png
[Link 1]: http://c.biancheng.net/data_structure/tree/