前言

2021年上半年 软件设计师 上午试卷中有这样一道题

58.当二叉树的结点数目确定时，________的高度一定是最小的。
A.二叉排序树 B.完全二叉树 C.线索二叉树 D.最优二叉树

我已此为契机，来了解一下查找二叉树、完全二叉树、线索二叉树、最优二叉树的一些相关定义（此题结尾会给出答案详解）

一、查找二叉树（二叉排序树）

二叉排序树的定义：
1、若根结点的左子树非空时，左子树上的所有结点均要小于根节点；
2、若根结点的右子树非空时，右子树上的所有结点均要大于根节点；
3、根结点的左、右子树本身又各是一颗二叉排序树

二叉排序树示例如图所示：

删除与插入
（一）插入结点
1、若查找二叉树为空树，则已要插入的新结点作为它的根节点
2、如果要插入的结点已存在，则不再插入。如上图若想要插入关键字为32的结点，已经存在了，就不进行插入操作。
3、将要插入的结点键值与插入后的父结点键值比较，如果小于则插入左子树，反之插入右子树中

（二）删除结点
1、若待删除结点是叶子结点（即没有左右孩子），则直接删除。例如上图中的88,，直接删除88元素。
2、若待删除结点只有左子树而无右子树，直接将其左孩子与待删除结点的父结点直接连接，例如：41

3、若待删除结点只有右子树而无左子树，直接将其右孩子与待删除结点的父结点直接连接，例如：66

4、若待删除结点p同时存在左、右子树，可以从其左子树选择键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，例如删除：54

二、完全二叉树

定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h
层若干结点靠左对齐，就说它是完全二叉树。

如下图所示：

上图两种都是完全二叉树，接下来我再给出不是完全二叉树的图，好做个对比

a和b都不满足完全二叉树的定义，a是因为第h层结点不满足左靠齐；b是因为除了第h层外，其它层结点个数结点未达到最大。

需要补充一点，满二叉树也是一颗完全二叉树，但是完全二叉树不一定是满二叉树

满二叉树定义
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1，则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)

三、线索二叉树

定义:在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

单看定义还是有点抽象，我们先来了解一下为什么要有线索二叉树呢？
看下图中，我们发现在这颗树上存在着很懂指向null的指针（红色线），线索二叉树就是要让这些指针能够很好的运用上。

在二叉树存储结构中，因为每个结点中只有指向其左、右孩子的指针，所以从任一结点触发只能找到该节点的左、右孩子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。但是若想在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率，所以引入线索二叉树。

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域（证明略），利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

总结：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

接下来介绍其中之一 ----- 前序线索二叉树

前序二叉树，顾名思义，就是按照前序遍历的方式。。。其中，左子树结点的指针指向当前遍历当中的前序结点。右子树结点的指针指向当前遍历的后序结点。比方说，在前序遍历模式中，遍历的顺序是按照“根–左--右”的方式进行的，好比在上图的BDE中
以前序遍历的方式，依次访问的是B、D、E。所以结点D的左孩子指针指向前序B结点，右孩子指针指向后序E结点，如上图所示。

记住前/中/后序遍历的口诀：“前”代表根先遍历，“中”代表根中间时刻遍历，“后”代表根最后遍历。

这样表示可能还不够直观，我们把上面前序线索二叉树的示例转换为前序遍历结果为：ABDEHCFGI

从图中可以就可以验证之前的结论，线索链表很好的解决了在某种遍历方式下查找二叉树结点的前驱和后继结点困难的问题，中序、后序线索二叉树就不展开讲了，原理都是一样的。

四、最优二叉树（哈夫曼树）

定义：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

基本概念：
哈夫曼树又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

依旧结合图例来分别演示树的路径长度，权，带权路径长度，树的带权路径长度（树的代价）如何计算

• 树的路径长度就是图中每一根线（每根线长为1）累加起来的长度。
• 权就不必多说了，就是每个结点中所标记的值，就是该结点权值。
• 带权路径长度，就是路径的长度先求出来，再乘以权值。即：带权路径长度=该结点路径长度×该结点权值。比如，结点2的带权路径长度等于=（1+1）×2=4
• 树的带权路径长度，就是所有所有叶子结点的带权路径长度之和。例如上图，WPL=2×2+3×4+3×8+1×1=41。

哈夫曼树的构造
定义
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

先来一个简单一点的例子，将给定权值W=（1，3，5，7）来构造一颗哈夫曼树，按照上述的算
首先要找到两个权值最小的节点，来构造一颗新的二叉树，如下

现在还剩下的权值是：4，5，7
继续上面的操作

最终这颗树就构造完了

这棵树的带权路径长度为WPL=3×1+3×3+2×5+1×7=29

哈夫曼编码
定义：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

使用场景：在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的二进制字符串，称这个过程为编码。显然，我们希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。

！！！做题时，只需要记住的一点：哈夫曼树中的左分支为0、右分支为1。则从根结点到每个叶子结点所经过的分值对应的0和1组成的序列便是该结点对应的字符的编码。这样的编码成为哈夫曼编码

直接上题!!

【2021年下半年 软件设计师 上午试卷】已知一个文件中出现的各字符及其对应的频率如下表所示。采用Huffman编码，则该文件中字符a和c的码长分别为__(64)A__。若采用Huffman编码，则编码序列110001001101对应的字符应为__(65)A__。

（64）A. 1和3 B. 1和4 C. 3和3 D. 3和4
（65）A. face B. bace C. acde D. fade

解题过程：
1、先构造一颗哈夫曼树
根据题干所给出的权值（频率）={45，13，12，16，9，5}进行构造
每次选取权值最小的两个结点构造一颗二叉树，并将根结点放入权值序列中，一直重复这个步骤即可。
下面是最终构造出来的树↓

然后以“哈夫曼树中的左分支为0、右分支为1”规则，进行编码。

这样就可以求得每个字符的编码：a(0)，b(101)，c(100)，d(111)，e(1101)，f(1100)，从而可知编码序列“110001001101”代表的是字符“face”

在这颗树的构造上有一个容易出错的地方，一定要记得在每次构造树的时候选出两个权值最小的来构造一颗二叉树。比方说在5、9和14这颗树构造完后，还剩下的权值则为{12，13，14，16，45}，那么有些人会只选取12继续和14一起组成一颗二叉树，接下来的树就会变为大致这样。

一定要记得每轮选取的是最小两个，所以我们在这轮选取的应该是12和13，构造一颗12、13、25的树，在进行下一轮最小两权值的构造，以此类推，最终就能构造一颗真正的哈夫曼树！

文章大致内容就这么多，回到开头题目，就变得很清晰了。（虽然内容已经偏题~）

当二叉树的结点数目确定时，__完全二叉树___的高度一定是最小的。
因为，完全二叉树每层都尽量排满，因此树的高度相对其他来说一定是最小的。查找二叉树跟要插入的值大小相关，和树的高度不直接相关。线索二叉树是通过增设指针去保存结点的前驱后继关系，无法保证树的高度最小。最优二叉树是带权路径长度最短的一种二叉树，和树的高度没有必然的联系。

参考资料：《数据结构教程（第版）》

什么是哈夫曼树：
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树被用来进行哈夫曼编码，下面来介绍哈夫曼编码：
假设需要传送的电文为“ABACCDA”，它只有四种字符，只需要用两个字符的串就可以分辨，假设A,B,C,D的编码分别是00，01,10,11，则该电文的编码便是：“00010010101100”，总长为14位，对方接收时，只需要二位一分就可以进行译码。在现实中尽可能希望编码总长尽可能短，如果采用对每个字符设计长度不同的编码，那么让电文中出现次数较多的字符尽可能采用短的编码，那么电文总长就可以减少。比如设计A,B,C,D的编码为0,00,1，01，则上述电文可转换为：“000011010”，总长为9。但是这样的电文无法翻译，例如“0000”就有多种译法。或是“AAAA”，或者是“ABA”，又或者是“BB”等，因此，若要设计长度不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码

那么如何得到电文长度最短的二进制前缀编码呢？设计电文总长度最短的二进制前缀编码即为以n种字符出现的频率做权值，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码称为哈夫曼码。

下面就来说说如何创建一棵赫夫曼树。

对于如何构造哈夫曼树，哈夫曼最早就给出了一个带有一般规律的算法，俗称哈夫曼算法：

（1）根据给定的n个权值{$w_1$,$w_2$……,$w_n$}构成n棵二叉树的集合F = {$T_1$,$T_2$……，$T_n$},其中每棵二叉树中的$T_i$中只有一个带权为$w_i$的根节点，其左右子树均为空。

（2）在F中选取两棵根节点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和；

（3）在F中删除这两棵树，同时将新得到的二叉树加入F中；

（4）重复（2），和（3）步骤，直到F只含有一棵树为止。则这棵树就是哈夫曼树。

下面来看一个简单的案例：字母{a,b,c,d}，出现的次数为{7,5,2,4},构建出哈夫曼树：

我们按照哈夫曼算法来构建哈夫曼树。
第一步选取其中最小的两个构建成二叉树：

第二步将6添加至权值序列中，删除之前的2和4：
权值列表变成{7，5，6}
重复第一二步，直到构建完成：

权值列表：{7,11}

至此，哈夫曼树构建完成：

带权路径长度为：WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35
当然，哈夫曼树不是唯一的，比如上面的哈夫曼树也可以为：

带权路径长度为：WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35

但是不管哈夫曼树怎样构造，最短带权路径长度只有一个。

由于哈夫曼树中没有度为1的结点（又叫做正则二叉树），则一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在哎一个大小为2n-1的一维数组中。

下面来看一个复杂的例题：
已知某系统的通信联络中只可能出现8中字符，次数别为w= {5，29，7，8，14，23，3，11}
按照哈夫曼算法来构建哈夫曼树：
权值列表：{3，5，7，8，11，14，23，29}

权值列表：{7，8，8，11，14，23，29}

权值列表：{8，11，14，15，23，29}

权值列表：{14，15，19，23，29}

权值列表：{19，23，29，29}

权值列表：{29，29，42}

权值列表：{42，58}

至此，哈夫曼树已经构建完成。我们来算算其带权路径：
WPL = 23x2 + 11x3 + 5x4 + 3x4 + 29x2 + 14x3 + 7x4 + 8x4 = 271
我们规定向左为0，向右为1，则，该哈夫曼树为：

则这八种字符的编码分别为：{0110，10，1110，1111，110，00，011，010}

当然构造出的哈夫曼树不止一种，也可能为：
该图的带权路径为:
WPL = 29x2 + 14x3 + 7x4 + 3x5 + 5x5 + 23x2 + 8x3 + 11x3 = 271
由此看出，哈夫曼树可能不同，但是带权路径一定是同一个最小值。

已经了解了思想了，现在该如何实现了。

class Node:
    def __init__(self, name, weight):
        self.name = name #节点名
        self.weight = weight #节点权重
        self.left = None #节点左孩子
        self.right = None #节点右孩子
        self.father = None # 节点父节点
    #判断是否是左孩子
    def is_left_child(self):
        return self.father.left == self

#创建最初的叶子节点
def create_prim_nodes(data_set, labels):
    if(len(data_set) != len(labels)):
        raise Exception('数据和标签不匹配!')
    nodes = []
    for i in range(len(labels)):
        nodes.append( Node(labels[i],data_set[i]) )
    return nodes


# 创建huffman树
def create_HF_tree(nodes):
    #此处注意，copy()属于浅拷贝，只拷贝最外层元素，内层嵌套元素则通过引用，而不是独立分配内存
    tree_nodes = nodes.copy()
    while len(tree_nodes) > 1: #只剩根节点时，退出循环
        tree_nodes.sort(key=lambda node: node.weight)#升序排列
        new_left = tree_nodes.pop(0)
        new_right = tree_nodes.pop(0)
        new_node = Node(None, (new_left.weight + new_right.weight))
        new_node.left = new_left
        new_node.right = new_right
        new_left.father = new_right.father = new_node
        tree_nodes.append(new_node)
    tree_nodes[0].father = None #根节点父亲为None
    return tree_nodes[0] #返回根节点

#获取huffman编码
def get_huffman_code(nodes):
    codes = {}
    for node in nodes:
        code=''
        name = node.name
        while node.father != None:
            if node.is_left_child():
                code = '0' + code
            else:
                code = '1' + code
            node = node.father
        codes[name] = code
    return codes


if __name__ == '__main__':
    labels = ['A','B','C','D','E','F','G','H']
    data_set = [5,29,7,8,14,23,3,11]
    nodes = create_prim_nodes(data_set,labels)#创建初始叶子节点
    root = create_HF_tree(nodes)#创建huffman树
    codes = get_huffman_code(nodes)#获取huffman编码
    #打印huffman码
    for key in codes.keys():
        print(key,': ',codes[key])

运行结果：

A :  0001
B :  10
C :  1110
D :  1111
E :  110
F :  01
G :  0000
H :  001

代码参考自：哈夫曼树代码