写在前面
之前讲的链表，栈，队列等都是线性存储结构，都是一对一的关系。而树是具有一对多关系的数据结构。比如我们经常说的湖北省武汉市，湖南长沙的一个类图，就类似于一颗倒转的树。
什么是树
树是一种数据结构，由 n 个节点构成的具有层次关系的有限集合。
树的基本术语
节点：树中的每一个数据元素都是节点（A，B...）
节点的度：节点的子树个数（A 的子树为 B 和 C）
树的度：树中所有节点最大的度（树 A 和树 C 的度都是 2）
叶子节点：度为 0 的节点（D，E，F）
节点的层次：树的根开始，树根所在的层为第一层，根的子节点所在的层为第二层（A 第一层，BC 第二层）
有序树和无序树：子树有左右顺序之分 （如左边的小于右边），反之则为无序树
树的特点
子树是不相交的
除了根节点之外，每个节点有且只有一个父节点
一个又 N 个节点构成的树只有 N-1 条边
什么是二叉树
树中的节点的度不超过 2 的有序树。
二叉树的特点：
二叉树中，第 i 层的节点数最多为 2i-1
深度为 k 的二叉树最多有 2k-1 个节点
对于任意二叉树，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1，
即度为 0 的节点 n0，永远比度为 2 的节点 n2 多一个。
满二叉树
二叉树中除了叶子节点，每个节点的度都为 2，则此二叉树为满二叉树。
具有 n 个节点的满二叉树的深度为: log2(n+1)
完全二叉树
一棵二叉树中，只有最下面两层结点的度可以小于 2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
哈夫曼树(最优二叉树)
若给定一个二叉树如下：
路径：在一棵树中，一个节点到另一个节点之间的通路，称为路径。如上图中的根节点到 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 个字符进行编码如何对字符串进行编码，可以使得该字符串的编码存储空间最少？
如果用标准的等长 ASCII 编码：58 × 8 = 464 位
用二叉树进行编码
若用 0 和 1 表示左右分支，取出上面 4 个频次最高的字符，可以得到如下一棵树：
由上图可知，编码为 0100 可表示的字符就有 3 种可能的情况，因此，上面节点的分布具有二义性。如何避免二义性？只需要让每个节点都是叶子节点即可。
哈夫曼树图示构造
通过上面的方式，我们把上面的字符按频次依次两两组合，且都为叶子节点。最后构造图示如下：
因此，我们发现每个节点都是叶子节点，字符最后的编码为：
所以，编码长度为：
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]
复制代码
总结
本章主要是对树有基础的概念，了解常见的树的特点，后面会继续讲到二叉排序树，二叉平衡树等,数据结构相对来说是比较枯燥的，但是坚持下去会有收获的，不管是对算法还是看源码都有很大提升。
参考
评论