数据结构与算法之树形结构

树形结构是一种比线性结构更复杂的结构，与线性结构一样，是一种在逻辑上是有序的结构。树形结构（如果非空）具有一个顶点，称为起始结点，起始结点下又连接着其他结点，一直往下延伸。树形结构逻辑上有序的意思就是从起始结点往下延伸的顺序。 以下用一张图来描述下树的一些基本属性：

了解了树的一些基本属性后，我们来看看树的特例之一：二叉树

为什么说二叉树是树的特例呢？因为二叉树是一个最简单的树形结构，它的每个结点的后继结点至多有两个，所以后继结点可能为0,1,2。而且明确定义了后继结点中谁是左结点，谁是右结点。为了便于理解，我通过一张图来描述一下常见的二叉树的图形结构：

性质一：如果一个树中定义根结点的层数为0，以i代表其它结点的层数，那么第i层最多为2^i个结点 说明：第一层是根结点，为1个结点=2º=1，如果为满二叉树，那么第二层就最多为2个结点=2¹=2，依次类推 性质二：如果一个树的高度为h，定义根结点的高度为0，那么一个高度为h的树中最多有2(h+1)-1个结点，最少有2h-1个结点 性质三：对于任何非空二叉树T，如果其叶子结点的个数为N0，其度为2的结点的个数为N2，则N0=N2+1 说明：一个层数为1的二叉树，定义根结点的层数为0，那么它的度为2的结点为0或者1，它的叶子结点为1或者2，一个层数为2的二叉树，它的度为2的结点为0，1，2或3，它的叶子结点为1,2,3,4。依次类推。在此有两种情况可以帮助理解： 1、当往树中添加一个结点时，如果此结点不能构成它的双亲结点度为2，那么此种情况并不影响树中叶子结点的个数，比如看下图： 此种情况时，并不会改变树中叶子结点个数，比如左图中有叶子结点C,D。在C中添加了E的左子结点后，树中有叶子结点D，E。还是两个叶子结点，此种情况并不影响N0=N2+1的结果。 2、当往树中添加一个结点时，如果此结点加入后，它的双亲结点的度从1变成2，此时，度为2的结点个数+1，叶子结点也加1，也不影响N0=N2+1的结果。 综合上述两种情况，N0=N2+1的结果只需要从单点树（就是只有一个根结点的树）中来验证即可，因为单点树只要满足了此条性质，无论往单点数加什么结点，都不会影响这条性质的结果。在单点树中N0=1，N2=0，所以N0=N2+1 性质四：满二叉树的叶子结点比分支结点多一个 说明：满二叉树中的结点要么是叶子结点，要么就是度为2的分支结点，推论跟性质三类似，可以作为参考 性质五：n个结点的完全二叉树的高度h为不大于㏒₂ⁿ的最大整数。 说明：根据性质二与完全二叉树的性质可得出，2h-1 0 and e < elems[j]: elems[i] = elems[j] i = j j = (j - 1) // 2 elems[i] = e def dequeue(self): """ 出队 :return: """ if self._elems is None: raise priorityQueueError("in dequeue") # 弹出首端元素 elems = self._elems e0 = elems[0] prio_elem = elems.pop() # 重新构建堆序 if len(elems) == 0: raise priorityQueueError("no more elements") self.siftdown(prio_elem, 0, len(elems)) return e0 def siftdown2(self): """ 弹出首端元素后，构建堆序 思路：每次都补前面的一个坑。直到到达堆的尾部 缺陷：到了叶子结点的时候，有三种情况需要判断，逻辑复杂 情况1：如果只有一个结点的话，直接将此结点放入坑中即可。 情况2：如果有两个结点， 需要选一个较小的结点去填坑 情况3：如果选择的结点为右结点，结束即可，如果选择的结点为左结点，则需要将右结点左移一位，用于补位 :return: """ elems = self._elems i, j = 2 * parent_index + 1, 2 * parent_index + 2 parent_index = 0 while 2 * parent_index + 1 < len(elems) - 1: if elems[i] 1: t1 = trees.dequeue() t2 = trees.dequeue() x = t1.data + t2.data trees.enqueue(HTNode(x, t1, t2)) return trees.dequeue()

4、哈夫曼编码的应用 哈夫曼编码可以支持对数据的解压缩。而且是无损的。 5、其它 哈夫曼编码又分为自适应的与非自适应的。适应性哈夫曼编码（Adaptive Huffman coding），又称动态哈夫曼编码（Dynamic Huffman coding），是基于哈夫曼编码的适自适应编码技术。它允许在符号正在传输时构建代码，允许一次编码并适应数据中变化的条件，即随着数据流的到达，动态地收集和更新符号的概率（频率）。一遍扫描的好处是使得源程序可以实时编码，但由于单个丢失会损坏整个代码，因此它对传输错误更加敏感（摘自百度百科）。非适应性的又称为静态哈夫曼编码，静态哈夫曼编码需要先扫码编码原文，得到文本频率，然后再次扫码编码原文进行编码，所以静态哈夫曼编码在内存使用上，效率上都劣于动态哈夫曼编码。

总结： 1、树形结构相较于线性结构，是具有层次关系。在我们生活中，比如家里的祖辈关系、公司的组织结构关系等等都是属于树形结构。 2、二叉树是树形结构中的一种，二叉树顾名思义，就是两个分叉的树，所以二叉树的每一个结点至多有两个子结点。 3、二叉树的遍历有深度优先与广度优先两种，深度优先又分为先序根、中序根、后序根三种 4、在二叉树中又存在一种特殊的二叉树，为完全二叉树。在结构上很像完全二叉树的可以更优的实现优先队列的结构为：堆 5、二叉树的另一项重要应用就是哈夫曼树，哈夫曼树是哈夫曼编码过程中所构建的一种最优二叉树，它广泛应用于解压缩领域，是一种一致性无损压缩算法。 6、二叉树只是树形结构的一种，且是最简单的一种，还有多种应用广泛的树形结构并没有介绍，比如： 基于二叉树的扩展：二叉搜索（排序）树等 平衡树类：AVL、红黑树、B树、B+树等 图论相关：最小生成树等

相关推荐阅读： 数据结构与算法之二叉树扩展 数据结构与算法之队列与栈 深度优先与广度优先算法 图转换成树，最小生成树