当前位置：首页 > news >正文

【数据结构和算法】二、python中的常用数据结构(数组、链表、堆栈、递归、二叉树、哈夫曼树等数据结构的基本原理讲解与实战演练)

news 2024/10/25 22:05:06

1、数组和链表

1.1 数组是什么？

1.2 链表是什么？

1.3 数组和链表的算法实战

2、堆栈

2.1 堆栈是什么？

2.2 堆栈的算法实践

3、递归

3.1 递归是什么

4、二叉树

4.1 概念

4.2 二叉树的特点

4.3 二叉树链式结构的遍历

4.4 代码实现

5、Huffman树

5.1 霍夫曼编码

5.2 霍夫曼树相关的几个名词

5.3 什么是霍夫曼树

5.4 构建霍夫曼树的过程

5.5 霍夫曼树结点结构

5.6 构建霍夫曼树的算法实现

5.7 根据霍夫曼树节点实现霍夫曼编码

数据结构算是我们软件开发中最基础的部分了，它体现着我们编程的内功。很多数人是在大学的计算机课上学习的数据结构，虽然很经典，但在实际项目开发中，反而感觉到用得不多。

原本不是用得少，而是我们在使用的时候被很多高级语言和框架组件封装好了，真正需要自己去实现的地方比较少而已。但别人封装好了不代表我们就可以不关注了，数据结构作为程序员的内功心法，针对初学者或者是复习，都是非常值得我们多花一些时间来进行研究的。

1、数组和链表

先从大家最经常使用的数组和链表聊起。不过在聊数组和链表之前，咱们先看一下数据的逻辑结构分类。通俗的讲，数据的逻辑结构主要分为两种：

线性的：就是连成一条线的结构，本文要讲的数组和链表就属于这一类，另外还有队列、栈等
非线性的：顾名思义，数据之间的关系是非线性的，比如堆、树、图等

知道了分类，下面我们来详细看一下「数组」和「链表」的原理。

1.1 数组是什么？

数组是一个有限的、类型相同的数据的集合，在内存中是一段连续的内存区域。

数组的下标是从0开始的，上图数组中有12个元素，对应着下标依次是0、1、2、3、4 …… 11，同时，数组里面存的数据的类型必须是一致的，数组中存储的都是数值类型，那么就不允许存入其它类型的值。数组中的全部元素是“连续”的存储在一块内存空间中的，元素与元素之间是不会有别的存储隔离的。例如上图中数组存储的整数类型(Integer)，每个元素都占用内存中4个字节大小的空间。另外，也是因为数组需要连续的内存空间，所以数组在定义的时候就需要提前指定固定大小，不能改变。

数组的访问：

数组在访问操作方面有着独特的性能优势，因为数组是支持随机访问的，也就是说我们可以通过下标随机访问数组中任何一个元素，其原理是因为数组元素的存储是连续的，所以我们可以通过数组内存空间的首地址加上元素的偏移量计算出某一个元素的内存地址，如下：

array[n]的地址 = array数组内存空间的首地址 + 每个元素大小n*

通过上述公式可知：数组中通过下标去访问数据时并不需要遍历整个数组，因此数组的访问时间复杂度是 O(1)，当然这里需要注意，如果不是通过下标去访问，而是通过内容去查找数组中的元素，则时间复杂度不是O(1)，极端的情况下需要遍历整个数组的元素，时间复杂度可能是O(n)，当然通过不同的查找算法所需的时间复杂度是不一样的。

数组的插入与删除：

同样是因为数组元素的连续性要求，所以导致数组在插入和删除元素的时候效率比较低。

如果要在数组中间插入一个新元素，就必须要将要相邻的后面的元素全部往后移动一个位置，留出空位给这个新元素。还是拿上面那图举例，如果需要在下标为2的地方插入一个新元素15，那就需要将原有下标2、3、4、5……11的所有元素依次往后移动一位，新元素再插入下标为2的位置，最后形成新的数组是：

11,9,15,17,89,1,90,19,5,3,23,43,99

如果新元素是插入在数组的最开头位置，那整个原始数组都需要向后移动一位，此时的时间复杂度为最坏情况即O(n)，如果新元素要插入的位置是最末尾，则无需其它元素移动，则此时时间复杂度为最好情况即O(1)，所以平均而言数组插入的时间复杂度是O(n)

数组的删除与数组的插入是类似的。

所以整体而言，数组的访问效率高，插入与删除效率低。不过想改善数组的插入与删除效率也是有办法的，通过下面的「链表」就是一个好的解决方案。

1.2 链表是什么？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，一般用于插入与删除较为频繁的场景。

上图是“单链表”示例，链表并不需要数组那样的连续空间，它只需要一个个零散的内存空间即可，因此对内存空间的要求也比数组低。

链表的每一个节点通过“指针”链接起来，每一个节点有2部分组成，一部分是数据（上图中的Data），另一部分是后继指针（用来存储后一个节点的地址），在这条链中，最开始的节点称为Head，最末尾节点的指针指向NULL。

「链表」也分为好几种，上图是最简单的一种，它的每一个节点只有一个指针（后继指针）指向后面一个节点，这个链表称为：单向链表，除此之外还有双向链表、循环链表等。

双向链表：

双向链表与单向链表的区别是前者是2个方向都有指针，后者只有1个方向的指针。双向链表的每一个节点都有2个指针，一个指向前节点，一个指向后节点。双向链表在操作的时候比单向链表的效率要高很多，但是由于多一个指针空间，所以占用内存也会多一点。

循环链表：

其实循环链表就是一种特殊的单向链表，只不过在单向链表的基础上，将尾节点的指针指向了Head节点，使之首尾相连。

链表的访问

链表的优势并不在与访问，因为链表无法通过首地址和下标去计算出某一个节点的地址，所以链表中如果要查找某个节点，则需要一个节点一个节点的遍历，因此链表的访问时间复杂度为O(n)

链表的插入与删除

也正式因为链表内存空间是非连续的，所以它对元素的插入和删除时，并不需要像数组那样移动其它元素，只需要修改指针的指向即可。

例如：删除一个元素E：

例如：插入一个元素：

既然插入与删除元素只需要改动指针，无需移动数据，那么链表的时间插入删除的时间复杂度为O(1)不过这里指的是找到节点之后纯粹的插入或删除动作所需的时间复杂度。

如果当前还未定位到指定的节点，只是拿到链表的Head，这个时候要去删除此链表中某个固定内容的节点，则需要先查找到那个节点，这个查找的动作又是一个遍历动作了，这个遍历查找的时间复杂度却是O(n)，两者加起来总的时间复杂度其实是O(n)的。

其实就算是已经定位到了某个要删除的节点了，删除逻辑也不简单。以“删除上图的2节点”为例，假如当前链表指针已经定位到了2节点，删除的时候，需要将这个2节点的前面一个节点1的后继指针改为指向3节点，那么2节点就会自动脱落了，但是当前链表指针是定位在2节点上，如何去改变1节点的后续指针呢，对于“单向链表”而言，这个时候需要从头遍历一遍整个链表，找到1节点去修改其后继指针的内容，所以时间复杂度是O(n)，但如果当前是“双向链表”，则不需要遍历，直接通过前继指针即可找到1节点，时间复杂度是O(1)，这里就是“双向链表”相当于“单向链表”的优势所在。

1.3 数组和链表的算法实战

通过上面的介绍我们可以看到「数组」和「链表」各有优势，并且时间复杂度在不同的操作情况下也不相同，不能简单一句O(1)或O(n)所能概况的。所以下面我们找个常用的算法题来练习练习。

算法题：反转一个单链表输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

"""定义一个单向链表节点class ListNode:def __init__(self, x):self.val = xself.next = None创建链表node1 = ListNode(1)node1.next = None# 能不能通过循环创建Linked List？node2 = ListNode(2)node2.next = node1.nextnode1.next = node2node3 = ListNode(3)node3.next = node2.nextnode2.next = node3head = node1# 遍历节点while True:if head is None:breakprint(head.val)head = head.next"""def reverseList(head):# 定义一个前置节点变量，默认是null，因为对于第一个节点而言没有前置节点pre = None# 定义一个当前节点变量，首先将头节点赋值给它curr = head# 遍历整个链表，直到当前指向的节点为空，也就是最后一个节点了while curr is not None:# 在循环体里会去改变当前节点的指针方向，# 当前节点的指针改为指向前一个节点# 但是如果直接就这么修改了，那链条就断了，再也找不到后面的节点了，# 所以首先需要将下一个节点先临时保存起来，赋值到temp中，以备后续使用temp = curr.next# 处理当前节点，将当前节点的指针指向前面一个节点curr.next = pre# 将当前节点赋值给变量pre，也就是让pre移动一步，pre指向了当前节点pre = curr# 将之前保存的临时节点（后面一个节点）赋值给当前节点变量curr = temp# 循环体执行链表状态变更情况：# NULL<-1 2->3->4->5->NULL# NULL<-1<-2 3->4->5->NULL# NULL<-1<-2<-3 4->5->NULL# NULL<-1<-2<-3<-4 5->NULL# NULL<-1<-2<-3<-4<-5# 循环体遍历完之后，pre指向5的节点# 时间复杂度为O(?)return pre

以上，就是对「数组与链表」的一些解释和实现。

2、堆栈

2.1 堆栈是什么？

堆栈（stack）是一种先进后出的、操作受限的线性表，也可以直接称为栈。

可以把栈想象成一个箱子一样，往这个箱子里面一层一层的放东西，先放进去的在里面，后放进去的东西依次在外面。但取东西的时候就是先取靠近外面的，再依次一层层取里面的。这就是后进先出（ Last In-First Out ）的原则。

因此「栈」虽然是线性的，但是有2个端：顶端和底端，但它只允许从一端进行插入和删除数据，这就是前面说的「栈」是操作受限的了。

栈只有两种操作：Push 和 Pop 。我们用Push（压入）来表示往栈中插入数据，也叫入栈，用Pop（弹出）来表示从栈中删除数据，也叫出栈。我们可以既可以用「数组」来实现一个栈，也可以用「链表」来实现一个栈。

用数组实现的栈，叫做 顺序栈：

顺序栈的实现并不困难，简单写一下思路：
- 初始化一个数组
- 使用一个计数器变量给数组的元素计数
- 元素入栈操作：将新元素写入到数组最后一个元素后面，计数器加一。
- 元素出栈操作：将数组中最后一个元素返回，计数器减一。
  
  在入栈前需要判断数组是否已经满了，如果数组大小等于计数器大小，则表明数组是满的。
  
  出栈的时候也需要判断数组是不是空数组，如果计数器是0，则表明数组是空的。
从上面的实现流程可以看出，通过数组实现的栈，其入栈和出栈都是对单个元素进行操作，因此其入栈和出栈的时间复杂度都是O(1)，并且其入栈和出栈操作并没有额外开销更多空间，因此其空间复杂度也是O(1)的。
用链表实现的栈，叫做 链式栈：

实现思路：
- 定义一个链表节点的类
- 根据类定义一个头节点Head
- 元素入栈操作：将新元素的Next指向头结点Head的Next节点，再将Head的Next指向新节点。
- 元素出栈操作：返回Head所指向的节点，让Head指向Next节点。
在入栈和出栈时都需要判断链表是否为空的情况。

链式栈的入栈和出栈都是在处理头部节点，所以操作很简单，其时间和空间复杂度均为O(1)。

2.2 堆栈的算法实践

堆结构

算法题：有效的符号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

输入："()"、"()[]{}"、"(]"、"([)]" 、"{[]}"

输出：True、True、False、False、True

"""
思路1：
使用堆栈解决，依次遍历字符串，如果遇到是左括号就入栈到堆栈中.
如果遇到的是右括号，则从堆栈中取出栈顶的第一个左括号，比对一下
这个左括号和当前遇到的右括号是否匹配，如果不匹配这认为这整个字符串无效。
如果能匹配，则继续循环，删除这个左括号和右括号，继续遍历字符串中剩下的字符
遇到左括号就入栈，只要遇到右括号就与将栈顶的左括号出栈与之比较。
一直走到字符串结束，再来检查堆栈中是否还有元素，如果还有元素，
则这个字符串同样无效，如果堆栈为空，则字符串有效。思路实现一个代码：
"""
class Solution:def valid(self, s):satck = list()for i in range(len(s)):c = s[i]if c == '(' or c =='{' or c=='[':satck.append(c)else:if len(satck) == 0: return Falsetemp = satck.pop()if (temp == '(' and  c == ')') or (temp == '{' and  c == '}') or (temp == '[' and  c==']'):continueelse:return Falsereturn len(satck) == 0

3、递归

「递归」并不是一种数据结构，它是很多算法都使用的一种编程技巧。由于太普遍了，并且用它来解决问题非常的优雅。

3.1 递归是什么

递归就是指函数直接或间接的调用自己，递归是基于栈来实现的。递归的经典例子就是斐波拉契数列（Fibonacci）。一般如果能用递归来实现的程序，那它也能用循环来实现。用递归来实现的话，代码看起来更清晰一些，但递归的性能并不占优势，时间复杂度甚至也会更大一些。

斐波拉契数列

实现递归满足的2个条件：

（1）可自调用

就是我们要解决的这个问题，可以通过函数调用自己的方式来解决，即可以通过将大问题分解为子问题，然后子问题再可以分解为子子问题，这样不停的分解。并且大问题与子问题/子子问题的解决思路是完全一样的，只不过数据不一样。因此这些问题都是通过某一个函数去解决的，最终我们看到的就是不停得函数调用自己，然后就把问题化解了。

如果这个问题不能分解为子问题，或子问题的解决方法与大问题不一样，那就无法通过递归调用来解决。

（2）可停止自调用

停止调用的条件非常关键，就是大问题不停的一层层分解为子问题后，最终必须有一个条件是来终止这种分解动作的（也就是停止调用自己），做递归运算一定要有这个终止条件，否则就会陷入无限循环。

围绕着斐波拉契数列（Fibonacci）为例，我们来理解一下递归：

斐波拉契数列就是由数字 1，1，2，3，5，8，13…… 组成的这么一组序列，特点是每位数字都是前面相邻两项之和。如果我们希望得出第N位的数字是多少？

（1）可以使用循环的方式求解：

思路:

已知最基本的情况是 f(0)=0，f(1)=1，因此我们可以设置一个一个循环，循环从i=1开始，循环N-1次，在循环体内 f(i)=f(i-1)+f(i-2)，直到i=N-1，这样循环结束的时候就求出了f(N)的值了。

（2）更优雅的方式是使用递归的方式求解：i

已知斐波拉契数列的逻辑就是：

F_0=0F_1=1F_n=F_{n-1}

可以看出，这个逻辑是满足上面2个基本条件，假如求解 f(3)，那 f(3)=f(2)+f(1)，因此我们得继续去求解f(2)，而 f(2)=f(1)+f(0)，因此整个求解过程其实就在不断的分解问题的过程，将大问题f(3)，分解为f(2)和f(1)的问题，以此类推。既然可以分解成子问题，并且子问题的解决方法与大问题一致，因此这个问题是满足“可调用自己”的递归要求。同时，我们也知道应该在何时停止调用自己，即当子问题变成了f(0)和f(1)时，就不再需要往下分解了，因此也满足递归中“可停止调用自己”的这个要求。

def Fb(n):if(n<=1):return 0 if n==0 else 1return Fb(n-1) + Fb(n-2)  # 这里就是函数自己调用自己

从上面的例子可以看出，我们写递归代码最重要的就是写2点：

（1）递推公式

上面代码中，递推公式就是 Fb(n)=Fb(n-1)+Fb(n-2)，正是这个公式，才可以一步步递推下去，这也是函数自己调用自己的关键点。因此我们在写递归代码的时候最首先要做的就是思考整个逻辑中的递推公式。

（2）递归停止条件

上面代码中的停止条件很明显就是：if(n<=1) return 0 if n==0 else 1这就是递归的出口，想出了递推公司之后，就要考虑递归停止条件是啥，没有停止条件就会无限循环了，通常递归的停止条件是程序的边界值。

我们对比实现斐波拉契数列问题的2种方式，可以看出递归的方式比循环的方式在程序结构上更简洁清晰，代码也更易读。但递归调用的过程中会建立函数副本，创建大量的调用栈，如果递归的数据量很大，调用层次很多，就会导致消耗大量的时间和空间，不仅性能较低，甚至会出现堆栈溢出的情况。

我们在写递归的时候，一定要注意递归深度的问题，随时做好判断，防止出现堆栈溢出。

另外，我们在思考递归逻辑的时候，没必要在大脑中将整个递推逻辑一层层的想透彻，一般人都会绕晕的。大脑很辛苦的，我们应该对它好一点。我们只需要关注当前这一层是否成立即可，至于下一层不用去关注，当前这一层逻辑成立了，下一层肯定也会成立的，最后只需要拿张纸和笔，模拟一些简单数据代入到公式中去校验一下递推公式对不对即可。

4、二叉树

4.1 概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

4.2 二叉树的特点

每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
二叉树的子树有左右之分，其子树的次序不能颠倒。

4.3 二叉树链式结构的遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 A-->B-->D-->G-->H-->I-->C-->E-->J-->F

LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。 G-->D-->I-->H-->B-->A-->E-->J-->C-->F

LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 G-->I-->H-->D-->B-->J-->E-->F-->C-->A

4.4 代码实现

# 构建二叉树
def Bintree(data, left=None, right=None):return [data, left, right]#判断二叉树是否为空树，返回的是一个布尔值
def is_empty_Bintree(tree):return tree is None
#  a[2,None,None],它表示的是根节点为2，没有子节点，a[0]为根节点，a[1]为左子节点，a[2]为右子节点。
# 返回树的根
def root(tree):return tree[0]def left(tree):return tree[1]def right(tree):return tree[2]# 插入一个根节点
def set_root(tree, data):tree[0] = datadef set_left(tree, left):tree[1] = leftdef set_right(tree, right):tree[2] = rightt=Bintree(2, Bintree(4), Bintree(8))
set_left(left(t),Bintree(5))
set_right(left(t),Bintree(6))
set_left(left(left(t)),Bintree(9))
set_left(right(t),Bintree(7))
set_right(right(t),Bintree(1))
print(t)# print(root(t))
# print(left(t))
# print(right(t))

先序、中序、后序遍历：

#    先序遍历（先根节点，再左节点，后右节点）
def Before(tree):if is_empty_Bintree(tree)==False:a=root(tree)if a==None:passelse:print(a)Before(left(tree))Before(right(tree))return None
# Before(t)# 中序遍历（先左节点，再根节点，后右节点）
def Medium(tree):if is_empty_Bintree(tree)==False:Medium(left(tree))a=root(tree)if a==None:passelse:print(a)Medium(right(tree))return None
# Medium(t)#  后序遍历（先左节点，再右节点，后根节点）
def After(tree):if is_empty_Bintree(tree) == False:After(left(tree))After(right(tree))a = root(tree)if a == None:passelse:print(a)return None
After(t)

5、Huffman树

5.1 霍夫曼编码

1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。

霍夫曼编码是一种经典的数据压缩方法，可以压缩图像、音频、表格等。这种压缩方案主要用于JPEG和MPEG-2。

让我们来看下方的字符串：

A DEAD DAD CEDED A BAD BABE A BEADED ABACA BED

这里一共有46个字符，每个字符占8个比特(bit)，所以一共有46*8=368个比特(bit)。如果我们使用霍夫曼编码的话，可以将这368个比特(bit)压缩到更小的尺寸。

在上面的字符串中，如果我们使用等长编码（Equal Length Code），将每个字符设计成长度为3的二进制编码，将会得到46*3=138个比特（长度为138）。但等长编码有一个弊端，即所有字符的长度相同导致编码结果太长，占用了太多计算机空间和网络带宽。

所以变长编码（Variable Length Code）应运而生，但同时也带来一个问题：二进制编码中，只有0和1，如果每个字符的位数不固定，则很难确定从哪里开始，以及到哪里停止，这就很容易产生歧义。虽然可以使用分隔符，但是这样一来却增加了消息长度。

这时，霍夫曼编码出现了。霍夫曼编码所使用的基本策略是：出现频率高的字符使用较短的编码，出现频率低的字符则使用较长的编码。霍夫曼编码使用前缀码（Prefix code）解决了前述的歧义问题，前缀码，即表示某些特定符号的位串永远不是代表任何其他符号的位串的前缀。

注：前缀码（Prefix code）, 有时称为“无前缀码（Prefix-free code）”。

这种方式通过构建霍夫曼树（Huffman tree）来完成。

5.2 霍夫曼树相关的几个名词

图 1

路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。

路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。

结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作WPL(Weighted Path Length) 。例如图 1 中所示的这颗树的带权路径长度为：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

5.3 什么是霍夫曼树

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“霍夫曼树”或者“哈夫曼树”。

在构建霍夫曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。

5.4 构建霍夫曼树的过程

对于给定的有各自权值的 n个结点，构建霍夫曼树有一个行之有效的办法：

在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复步骤 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是霍夫曼树。

图 2

图 2 中，（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是霍夫曼树。

5.5 霍夫曼树结点结构

构建霍夫曼树时，首先需要确定树中结点的构成。由于霍夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向父结点的指针。但是在使用霍夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左子节点和右子节点的指针。

class Node(object):def __init__(self,name=None,value=None):self._name=nameself._value=valueself._left=Noneself._right=None

5.6 构建霍夫曼树的算法实现

构建霍夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。

查找权重值最小的两个结点的思想是：从数组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：

如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
如果介于两个结点权重值之间，替换原来较大的结点；

while len(self.a)!=1:    self.a.sort(key=lambda node:node._value,reverse=True)# 合并两个最小值为一个新节点c = Node(value=(self.a[-1]._value + self.a[-2]._value))# 原有集合移除最小值c._left=self.a.pop(-1)c._right=self.a.pop(-1)# 新节点添加到原集合self.a.append(c)
self.root = self.a[0]