写在前面

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

05.树和二叉树 - 图1

什么是树

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

05.树和二叉树 - 图2

树的基本术语

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

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

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

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

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

树的高度：树中所有节点中最大的层次为树的高度

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

树的特点

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

什么是二叉树

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

05.树和二叉树 - 图3

二叉树的特点：

  1. 二叉树中，第i层的节点数最多为2

  2. 深度为k的二叉树最多有2-1个节点

  3. 对于任意二叉树，终端结点数（叶子结点数）为 n，度为 2 的结点数为 n，则 n=n+1，
    即度为0的节点n，永远比度为2的节点 n多一个。
    05.树和二叉树 - 图4
    证明：设度为0的节点有n个，度为1的节点为n，度为2的节点为n，共计n个节点,
    因为二叉树的所有节点的度数均不大于2，所以：
    n = n + n + n ①
    又因为0度的节点没有孩子，1度的节点有一个孩子，2度的节点有2个孩子，所以孩子总数为：
    0 n + 1 n + 2 * n，此外，根节点（第一层的节点）不是任何节点的孩子，所以
    总节点数 = 孩子总数 + 根节点，即
    n = n + 2n + 1 ②
    ② - ①化简得
    n = n + 1

满二叉树

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

具有 n 个节点的满二叉树的深度为: log

05.树和二叉树 - 图5

完全二叉树

如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左而右。则深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

05.树和二叉树 - 图6

哈夫曼树(最优二叉树)

若给定一个二叉树如下：

05.树和二叉树 - 图7

路径：在一棵树中，一个节点到另一个节点之间的通路，称为路径。如上图中的根节点到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个字符进行编码如何对字符串进行编码，可以使得该字符串的编码存储空间最少？

05.树和二叉树 - 图8

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

用二叉树进行编码

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

05.树和二叉树 - 图9

05.树和二叉树 - 图10

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

05.树和二叉树 - 图11

哈夫曼树图示构造

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

05.树和二叉树 - 图12

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

05.树和二叉树 - 图13

所以，编码长度为：

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

代码构造

  1. public class HuffmanTree {
  3.     //节点
  4.     public static class Node<E> {
  5.         //数据，如a,b,c,d。。。
  6.         E data;
  7.         //权重
  8.         int weight;
  9.         //左子节点
  10.         Node leftChild;
  11.         //you子节点
  12.         Node rightChild;
  14.         public Node(E data, int weight) {
  15.             this.data = data;
  16.             this.weight = weight;
  17.         }
  19.         public String toString() {
  20.             return "Node[" + weight + ",data=" + data + "]";
  21.         }
  22.     }
  24.     public static Node createHuffmanTree(List<Node> nodeList) {
  25.         //当节点大于1时
  26.         while (nodeList.size() > 1) {
  27.             //先对list中根据权重排序
  28.             sort(nodeList);
  29.             //排序之后第一个节点就是权重最小的节点，第二个节点就是权重第二小的节点
  30.             Node left = nodeList.get(0);
  31.             Node right = nodeList.get(1);
  32.             //生成一个新的父节点，类似于步骤1,但父节点没有数据只有权值
  33.             Node<Node> parent = new Node<>(null, left.weight + right.weight);
  34.             //子节点和父节点链接
  35.             parent.leftChild = left;
  36.             parent.rightChild = right;
  37.             //删除最小的节点
  38.             nodeList.remove(0);
  39.             //删除第二小的
  40.             nodeList.remove(0);
  41.             //添加到list中
  42.             nodeList.add(parent);
  43.         }
  44.         //最后返回根节点一棵树
  45.         return nodeList.get(0);
  46.     }
  48.     /**
  49.      * 冒牌排序
  50.      *
  51.      * @param nodeList
  52.      */
  53.     public static void sort(List<Node> nodeList) {
  54.         if (nodeList.size() <= 1) {
  55.             return;
  56.         }
  57.         for (int i = 0; i < nodeList.size(); i++) {
  58.             for (int j = 0; j < nodeList.size() - 1; j++) {
  59.                 //前面的数大于后面的数就交换
  60.                 if (nodeList.get(j + 1).weight < nodeList.get(j).weight) {
  61.                     Node temp = nodeList.get(j + 1);
  62.                     nodeList.set(j + 1, nodeList.get(j));
  63.                     nodeList.set(j, temp);
  64.                 }
  65.             }
  66.         }
  67.     }
  69.     /**
  70.      * 打印哈夫曼树，先左后右
  71.      * 即从根节点开始先打印出子节点的左节点，在打印右节点
  72.      * @param root 根节点的树
  73.      */
  74.     public static void printTree(Node root) {
  75.         if (root.leftChild != null) {
  76.             System.out.println("左子节点：" + root.leftChild);
  77.             printTree(root.leftChild);
  78.         }
  79.         if (root.rightChild != null) {
  80.             System.out.println("右子节点：" + root.rightChild);
  81.             printTree(root.rightChild);
  82.         }
  83.     }
  86.     //测试
  87.     public static void main(String[] args) {
  88.         List<Node> nodes = new ArrayList<Node>();
  89.         //把节点加入至list中
  90.         nodes.add(new Node("a", 10));
  91.         nodes.add(new Node("b", 15));
  92.         nodes.add(new Node("c", 12));
  93.         nodes.add(new Node("d", 3));
  94.         nodes.add(new Node("e", 4));
  95.         nodes.add(new Node("f", 13));
  96.         nodes.add(new Node("g", 1));
  97.         Node root = createHuffmanTree(nodes);
  98.         printTree(root);
  99.     }
  100. }

测试结果

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

总结

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

参考