Tips: 采用java语言,关注博主,底部附有完整代码

工具:IDEA

本系列介绍的是数据结构: 树

这是第六篇目前计划一共有12篇:

1. 二叉树入门
2. 顺序二叉树
3. 线索化二叉树
4. 堆排序
5. 赫夫曼树(一)
6. 赫夫曼树(二) 本篇
7. 赫夫曼树(三)
8. 二叉排序树
9. 平衡二叉树
10. 2-3树,2-3-4树,B树 B+树 B*树 了解
11. 红黑树(一)
12. 红黑树(二)

敬请期待吧~~

高光时刻

随机字符串生成赫夫曼树完整流程:

回顾

先来回顾一下上一篇,上一篇的重点就是创建一颗赫夫曼树,

赫夫曼树是WPL 最小的树

上一篇是将数组转变成赫夫曼树

流程为:

1. 将数组转变成赫夫曼结点集合

2. 依次取出集合中前两个数据生成一个新的结点,然后删除掉这两个旧的结点

3. 重新排序

4. 重复2,3操作,直到集合中只剩下一个结点

最终赫夫曼集合中最后的这个结点就是他的根节点

完整流程图:

随机字符串生成赫夫曼树

解释一下什么叫随机字符串生成赫夫曼树

假设当前有一串字符串为 :

String str = "统计字符串个数122333";	
1

可以看出,字符串中有重复的数据

例如

• 22
• 333

那么就将权值设置为字符串中每个字符的个数,

在新添加一个变量来记录当前字母

修改赫夫曼结点

public class HuffmanNode implements Comparable<HuffmanNode> {
    // 权值 【字母个数】
    public int value;

    // 字母
    public Byte by;

    // 左子结点
    public HuffmanNode leftNode;

    // 右子结点
    public HuffmanNode rightNode;


    public HuffmanNode(int value, Byte by) {
        this.value = value;
        this.by = by;
    }

    // 前序遍历
    public void show() {...}

    @Override
    public int compareTo(HuffmanNode o) {
        return value - o.value;
    }
}
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

这里用包装类Byte来记录字母完全是因为Byte能够设置null

统计字符串个数

// 统计字符串个数
public static void count() {
    String str = "统计字符串个数122333";
    HashMap<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        int temp = 0;
      	
      	// 判断是否包含key
        if (map.containsKey(ch)) {
            // 包含key取出对应的value进行累加
            temp = map.get(ch);
        }
        map.put(ch, temp + 1);
    }
    System.out.println("字符个数为:" + map);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结果

字符个数为:{数=1, 计=1, 1=1, 串=1, 2=2, 3=3, 符=1, 字=1, 个=1, 统=1}

这段代码很好理解,也是一道很常见的面试题!

因为这段代码重复的字母不多,体现不出赫夫的优点,现在讲原本字符串替换成

String str = "i like like like java do you like a java";
1

这段字符串,分别为:

• d : 1
• v : 1
• u : 1
• j : 2
• v : 2
• o : 2
• l : 4
• k : 4
• e : 4
• i : 5
• a : 5
• 空格 : 9

左边是字母,右边是字母个数

然后通过昨天的代码来稍微改改就可以:

完整流程:

完整代码

# 赫夫曼树
/**
 * @author: android 超级兵
 * @create: 2022-06-13 09:59
 **/
public class CreateHuffmanTreeClient {
    public static void main(String[] args) {
        System.out.println("创建赫夫曼树");
        String str = "i like like like java do you like a java";
        // [d:1,v:1,u:1,j:2,v:2,o:2,l:4,k:4,e:4,i:6,a:5,' ':9]
//         d:1
//         v:1
//         u:1
//         j:2
//         v:2
//         o:2
//         l:4
//         k:4
//         e:4
//         i:5
//         a:5
//         空格:9
        /// 分别计算个个字母的个数

        HuffmanNode root = createHuffman(str.getBytes());

        System.out.println("前序遍历:");

        root.show();
    }
		/// 创建赫夫曼树
    public static HuffmanNode createHuffman(byte[] bytes) {
        // 计算小写字母个数，生成对应赫夫曼结点
        ArrayList<HuffmanNode> list = countLetters(bytes);

        // 创建HuffmanTree
        return createHuffmanTree(list);
    }
  
    /*
     * @author: android 超级兵
     * @create: 2022/6/13 10:04
     * TODO 计算字母个数 返回赫夫曼结点集合
     * return 赫夫曼结点集合
     * map: key = 字母 value = 字母个数
     * tips: HashMap 特点: key不会重复
     */
    public static ArrayList<HuffmanNode> countLetters(byte[] bytes) {
        ArrayList<HuffmanNode> list = new ArrayList<>();

        // 用于统计字符串个数
        HashMap<Byte, Integer> map = new HashMap<>();

        // 循环所有bytes
        for (byte b : bytes) {
            int temp = 0;
            // map中是否包含当前循环的b
            if (map.containsKey(b)) {
                // 如果包含，重新赋值temp
                temp = map.get(b);
            }
            // 记录byte的个数
            // 这里hashmap不会重复，所以一直累加value
            map.put(b, temp + 1);
        }

//        System.out.println("当前记录下标为:" + Arrays.toString(indexInts));

        // 创建赫夫曼结点
        map.forEach((aByte, integer) -> list.add(new HuffmanNode(integer, aByte)));

        return list;
    }

    /*
     * @author: android 超级兵
     * @create: 2022/6/13 10:46
     * TODO 创建赫夫曼树
     * return :返回最终rootNode
     */
    public static HuffmanNode createHuffmanTree(ArrayList<HuffmanNode> list) {
        while (list.size() > 1) {
            // 排序
            Collections.sort(list);

//            System.out.println("第" + index + "次变化过程前:" + list);
            // 左子结点
            HuffmanNode left = list.get(0);
            // 右子结点
            HuffmanNode right = list.get(1);

            HuffmanNode parent = new HuffmanNode(left.value + right.value, null);
            parent.leftNode = left;
            parent.rightNode = right;

            // 删除左子结点
            list.remove(0);
            // 删除右子结点
            list.remove(0);

            list.add(parent);
        }

        // 返回root结点
        return list.get(0);
    }
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

最终随机生成的赫夫曼树为:

完整代码

原创不易,您的点赞就是对我最大的支持!

下一篇:赫夫曼树(三) [开发中]