写点什么

悟了!树,二叉树,哈夫曼树...

用户头像
阿粤Ayue
关注
发布于: 1 小时前
悟了!树,二叉树,哈夫曼树...

写在前面

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



什么是树

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


树的基本术语

节点:树中的每一个数据元素都是节点(A,B...)

节点的度:节点的子树个数(A 的子树为 B 和 C)

树的度:树中所有节点最大的度(树 A 和树 C 的度都是 2)

叶子节点:度为 0 的节点(D,E,F)

节点的层次:树的根开始,树根所在的层为第一层,根的子节点所在的层为第二层(A 第一层,BC 第二层)

有序树和无序树:子树有左右顺序之分 (如左边的小于右边),反之则为无序树

树的特点

  1. 子树是不相交的

  2. 除了根节点之外,每个节点有且只有一个父节点

  3. 一个又 N 个节点构成的树只有 N-1 条边

什么是二叉树

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


二叉树的特点:

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

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

  3. 对于任意二叉树,终端结点数(叶子结点数)为 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]
复制代码

总结

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

参考


发布于: 1 小时前阅读数: 3
用户头像

阿粤Ayue

关注

微信搜:Javatv 2019.10.16 加入

秘密基地:javatv.net

评论

发布
暂无评论
悟了!树,二叉树,哈夫曼树...