树形结构是复杂结构中最简单的一类结构。
树形结构也是由结点和结点之间的连接关系构成，但其结构和线性结构不同，最重要的特征包括：
1）一个结构如果不空，其中就存在着唯一的起始结点，称为树根(root)。
2）按结构的连接关系，树根外的其余结点都有且只有一个前驱(这点与线性结构一样)。但另一方面，一个结点可以有0个或多个后继(因此与线性结构不同)。另外，在非空的树结构中一定有些结点并不连接到其他结点，这些结点与表的尾结点性质类似，但一个树结构里可以存在多个这种结点。
3）从树根结点出发，经过若干次后继关系可以到达结构中的任一结点。
4）结点之间的联系不会形成循环关系，这也说明，结点之间的联系形成了一种序，但一般而言不像线性表那样形成一个全序。
5）从这种结构里的任意两个不同结点出发，通过后继关系可达的两个结点集合，或者不相交，或者一个集合是另一个集合的子集。
6.1 二叉树：概念和性质
二叉树是一种最简单的树形结构，其特点是：
1）树中每个结点最多关联到两个后继结点(0、1、2)。
2）一个结点关联的后继结点明确地分左右，或为其左关联结点，或为其右关联结点。
特点2是二叉树与度为2的树的本质区别。
6.1.1 概念和性质
定义和图示
几个基本概念
不包含任何结点的二叉树称为空树；只包含一个结点的二叉树是一棵单点树；一般而言，一棵二叉树可以包含任意个(但有穷个)结点。
一棵二叉树的根结点称为该树的子树根结点的父结点；与之对应，子树的根结点称为二叉树树根结点的子结点。父结点和子结点的概念是相对的。
可以认为从父结点到子结点有一条连线，称为从父结点到子结点的边。边是有方向的，形成一种单方向的父子关系。基于父子关系可以定义其传递关系，称为祖先/子孙关系。父结点相同的两个结点互为兄弟结点。一棵二叉树(或其中子树)的根结点r是这棵树(或这棵子树)中所有其他结点的祖先结点，而这些结点都是r的子孙结点。
二叉树中有些结点的两棵子树都为空能够，没有子结点，这种结点称为叶子结点。树中其余结点称为分支结点。对于二叉树，只有一个分支时必须说明它是其左分支还是右分支。
一个结点的子结点个数称为该结点的度数。易见，叶子结点的度数为0，分支结点的度数为1或2。
一棵二叉树只有五种可能的形态：
路径，结点的层和树的高度
根据祖先结点和子孙结点的定义，从一个祖先结点到其任何子孙结点都存在一系列的边，形成从前者到后者的联系。这样一系列首尾相连的边称为树中的一条路径。路径中边的条数称为该路径的长度。易见，从一个结点到其子结点有一条长度为1的路径。为统一起见，也认为从每个结点到其自身有一条长度为0的路径。显然，从一棵二叉树的根结点到该树中的任一结点都有路径，而且路径的长度都唯一。对二叉树的任意子树也有同样结论。
二叉树是一种层次结构。将其树根看作最高层元素，如果有子结点，其子结点看作下一层元素。规定二叉树树根的层数为0。对位于k层的结点，其子结点是k+1层的元素，如此下去，二叉树的所有结点可以按照这种关系分为一层层的元素。易见，从树根到树中任一结点的路径的长度就是该结点所在的层数，也称为该结点的层数。
一棵二叉树的高度(或深度)是树中结点的最大层数。树的高度是二叉树的整体性质。单点树的高度为0。不讨论空树的高度。
上述这些概念对一般树结构也适用。
二叉树的性质
作为数据结构，二叉树最重要的性质就是树的高度和树中可以容纳的最大结点个数之间的关系。树的高度类似于表长，是从根结点到其他结点的最大距离。在长为n的表里只能容纳n个结点，而在高为h的二叉树中则可能容纳大约2h个结点。这是表与树最大的不同点。
性质6.1 在非空二叉树第i层中最多有2i 个结点(i >= 0)。
性质6.2 高度为h的二叉树最多有2h+1–1个结点(h >= 0)。
性质6.3 对于任何非空二叉树，如果其叶结点的个数为n0，度数为2的结点个数为n2，那么n0 = n2+1。
满二叉树，扩充二叉树
如果二叉树中所有分支结点的度数都为2，则称为满二叉树。满二叉树是一般二叉树的一个子集。
性质6.4 满二叉树的叶子结点比分支结点多一个。(性质6.3的一个推论)
对二叉树T，加入足够多的新叶子结点，使T的原有结点(包括叶子结点)都变成度数为2的分支结点，得到的二叉树称为T的扩充二叉树。扩充二叉树中新增的结点称为外部结点，原树T的结点称为内部结点。空树的扩充二叉树规定为空树。
从形态看，任何二叉树的扩充二叉树都是满二叉树。根据性质6.4，扩充二叉树的外部结点个数比内部结点个数多1。
性质6.5 (扩充二叉树的内部和外部路径长度) 扩充二叉树的外部路径长度E为从树根到树中各外部结点的路径长度之和，内部路径长度I为从树根到树中各内部结点的路径长度之和，如果该树有n个内部结点，那么E=I+2*n。
完全二叉树
对于一棵高度为h的二叉树，如果从第0层至第h-1层的结点都满，如果最下一层的结点不满，则所有结点在最左边连续排列，空位都在右边，这样的二叉树称为完全二叉树。
性质6.6 n个结点的完全二叉树，高度h不大于log2n的最大整数。
2h-1 < n <= 2h+1-1
2h <= n < 2h+1
h <= log2n < h+1
性质6.7 (完全二叉树) 如果n个结点的完全二叉树按层次并按从左到右的顺序从0开始编号，对任一结点i (0 <= i <= n-1)都有：
1. 序号为0的结点为根。
2. 对于i>0，其父结点的编号为(i - 1) // 2。
3. 若2*i+1<n，其左子结点序号为2*i+1，否则它无左子结点。
4. 若2*i+2<n，其右子结点序号为2*i+2，否则它无右子结点。
5. 第h层的第一个结点序号为2h-1，有2h个元素，最后一个结点序号为2h+1-2。
6. 一个结点的左子结点序号为奇数，右子结点序号为偶数。
性质6.7是完全二叉树最重要的性质，使其可以方便地存入一个表或数组，直接根据元素下标就能找到一个结点的子结点或父结点，无须以其他方式记录树结构信息。
这说明从完全二叉树到线性结构有自然的双向映射，可以方便地从相应线性结构恢复完全二叉树。而一般二叉树没有这种性质。
一般而言，对于n个结点的二叉树有如下情况(直观看法)：
1）如果它足够“丰满整齐”(树中很少度数为1的分支结点，且最长路径的长度差不多)，树中最长路径的长度将为log2n。例如，完全二叉树。
2）如果它比较“畸形”，最长的长度可能达到n。
也就是说，一般而言，n个结点的二叉树中最长路径为n；对于所有的n个结点的二叉树，其最长路径的平均值为log2n。
6.1.2 抽象数据类型
python中，空二叉树用None表示。
6.1.3 遍历二叉树
每棵二叉树有唯一的根结点，可以将其看作这棵二叉树的唯一标识，是基于树结构的处理过程的入口。从根结点出发应该能找到树中所有信息，其基础是从父结点能找到两个子结点。
很多复杂的二叉树操作需要基于遍历实现。例如找一个结点的父结点，在二叉树里做这件事就像在单链表里找前一结点。
遍历二叉树，以根为起始点，存在两种基本方式：
1）深度优先遍历，顺着一条路径尽可能向前探索，必要时回溯。对于二叉树，最基本的回溯情况是检查完一个叶子结点，由于无路可走，只能回头。
2）宽度优先遍历，在所有路径上齐头并进。
深度优先遍历
按深度优先方式遍历一棵二叉树，需要做三件事：遍历左子树、遍历右子树、访问根结点(可能需要操作其中的数据)，如图6.8：
选择不同的执行顺序，可以得到三种常见的遍历顺序(假定总是先处理左子树，否则就有6种)：
1）先根序遍历(按照DLR顺序)
2）中根序遍历(按LDR)
3）后根序遍历(LRD)
由于二叉树的子树也是二叉树，将一种具体的遍历顺序继续运用到子树的遍历中，就形成了一种遍历二叉树的统一方法。
遍历过程中，遇到子树为空的情况，就立即结束处理并转去继续做下一步工作。
例子：
先根序列：A B D H E I C F J K G
中根序列：D H B E I A J F K C G
后根序列：H D I E B J K F G C A
如果二叉树中每个结点都有唯一标识，就可以用结点标识描述这些序列(如上图)。
给定的二叉树，其先根序列、中根序列、后根序列都是唯一确定了的。但反过来，给定了一棵二叉树的任一种遍历序列，无法唯一确定相应的二叉树。
如果给定了一棵二叉树的中根序列，再给定一个遍历序列(先根或后根)，就可以唯一确定相应的二叉树。
宽度优先遍历
按二叉树的层次逐层访问树中各结点。与状态空间搜索的情况一样，这种遍历不能写成一个递归过程。
在宽度优先遍历中只规定了逐层访问，并没有规定同一层结点的访问顺序。但从算法的角度看，必须规定一个顺序，常见的是在每一层里都从左到右逐个访问，实现这一算法需要用一个队列作为缓存。
宽度优先遍历又称为按层次顺序遍历，这种遍历产生的结点序列称为二叉树的层次序列。图6.9的层次序列为A B C D E F G H I J K。
遍历与搜索
二叉树可以看作一个状态空间：根结点对应状态空间的初始状态，父子结点链接对应状态的邻接关系。按照这种看法，一次二叉树遍历就是一次覆盖整个状态空间的搜索，前面所有有关状态空间搜索的方法和实现技术都可以原样移植到二叉树遍历问题中。例如，递归的搜索方法、基于栈的非递归搜索(即深度优先遍历)。基于队列的宽度优先搜索对应于这里的层次序遍历。
在二叉树遍历中，从一条路走下去，绝不会与另一条路相交，不必考虑循环访问的问题。
遍历是一种系统化的结点枚举过程，实际中未必需要检查全部结点，有时需要在找到所需信息后结束。在二叉树上也可能需要做这种搜索。
在状态空间的搜索过程中记录从一个状态到另一个状态的联系，将其看作结点间链接，就会发现这种搜索过程实际上构造出了一棵树，称为搜索树。一般而言，这样形成的结构不是二叉树而是一般的树。但无论如何，这种状态都进一步说明了树的遍历与状态空间搜索之间的紧密联系。
6.2 二叉树的list实现
简单看，二叉树结点也就是一个三元组，元素是左右子树和本结点数据。list和tuple都可以用于组合这样的三个元素，二者差异仅在于变动性。
6.2.1 设计和实现
二叉树是递归结构，list也是递归结构。基于list很容易实现二叉树，可以采用下面的设计：
1）空树用None表示。
2）非空二叉树用包含三个元素的列表[d, l, r]表示。
这样就把二叉树映射到一种分层的list结构，每棵二叉树都有与之对应的list。
例子，
对应
二叉树函数定义示意，
1 def BinTree(data, left=None, right=None): 2 return [data, left, right] 3 4 def is_empty_BinTree(btree): 5 return btree is None 6 7 def root(btree): 8 return btree[0] 9 10 def left(btree): 11 return btree[1] 12 13 def right(btree): 14 return btree[2] 15 16 def set_root(btree, data): 17 btree[0] = data 18 19 def set_left(btree, left): 20 btree[1] = left 21 22 def set_right(btree, right): 23 btree[2] = right 24 25 # 基于上述构造函数的嵌套调用，可以做出任意复杂的二叉树。 26 t1 = BinTree(2, BinTree(4), BinTree(8)) 27 print(t1) # [2, [4, None, None], [8, None, None]] 28 29 # 可以修改二叉树的任意部分 30 set_left(left(t1), BinTree(5)) # 修改t1的左子树的左子树 31 print(t1) # [2, [4, [5, None, None], None], [8, None, None]] list内部的嵌套层数等于树的高度。
6.2.2 二叉树的简单应用：表达式树
二元表达式和二叉树
数学表达式(算术表达式)具有分层次的递归结构，一个运算符作用于相应运算对象，其运算对象又可以是任意复杂的表达式。二叉树的递归结构正好用来表示这种表达式：二叉树中结点与子树的关系可用于表示运算符对运算对象的作用关系。
只考虑二元表达式：
1）以基本运算对象(数和变量)作为叶结点中的数据。
2）以运算符作为分支结点的数据：
1. 其两棵子树是它的运算对象。
2. 子树可以是基本运算对象，也可以是任意复杂的二元表达式。
一个结构正确的二元表达式对应于一棵满二叉树。
例题：
先根序、后根序、中根序。
构造表达式
由于建立起来的属性表达式绝不会变化，数学运算和操作都是基于已有表达式构造新表达式。因此，一种合理方式是把它实现为一种“不变”的二叉树，下面用tuple作为实现基础。
为使有关表示更简洁，对上面的二叉树表示方法做一下简化：将基本运算对象直接放在空树的位置，作为基本对象。例如表达式“3 * (2 + 5)”按照上面的表示为
1 ('*', (3, None, None),
2 ('+', (2, None, None), (5, None, None)))
去掉没有实际意义的None
1 ('*', 3, ('+', 2, 5))
采用简化的表达方式，表达式由两种结构组成：
1）如果是序对(tuple)，就是运算符作用于运算对象的复合表达式。
2）否则就是基本表达式，也就是数或变量。
上述两条可用于解析表达式的结构，实现对表达式的处理。
下面定义几个表达式构造函数：
1 def make_sum(a, b): 2 return ('+', a, b) 3 4 def make_prod(a, b): 5 return ('*', a, b) 6 7 def make_diff(a, b): 8 return ('-', a, b) 9 10 def make_div(a, b): 11 return ('/', a, b) 12 13 # 其他构造函数与此类似，略
开始构造，
1 res = make_prod(3, make_sum(2, 5))
2 print(res) # ('*', 3, ('+', 2, 5))
用字符串表示变量，就能构造出各种代数表达式，例如
1 res = make_sum(make_prod('a', 2), make_prod('b', 7))
2 print(res) # ('+', ('*', 'a', 2), ('*', 'b', 7))
在定义表达式处理函数时，经常需要区分基本表达式(直接处理)和复合表达式(递归处理)。为分辨这两种情况，定义一个判别是否为基本表达式的函数：
1 def is_basic_exp(a): # 基本表达式为非元组 2 return not isinstance(a, tuple) 3 4 # 判断是否为数值 5 def is_number(x): 6 # return (isinstance(x, int) or isinstance(x, float) or isinstance(x, complex)) 7 return type(x) in [int, float, complex]
表达式求值
表达式求值规则：
1）对表达式里的数和变量，其值就是它们自身。
2）其他表达式根据运算符的情况处理，可以定义专门的处理函数。
3）如一个运算符的两个运算对象都是数，就可以求出一个数值。
1 #!coding:utf8 2 3 def make_sum(a, b): 4 return ('+', a, b) 5 6 def make_prod(a, b): 7 return ('*', a, b) 8 9 def make_diff(a, b): 10 return ('-', a, b) 11 12 def make_div(a, b): 13 return ('/', a, b) 14 15 # 其他构造函数与此类似，略 16 17 def is_basic_exp(a): # 基本表达式为非元组 18 return not isinstance(a, tuple) 19 20 # 判断是否为数值 21 def is_number(x): 22 # return (isinstance(x, int) or isinstance(x, float) or isinstance(x, complex)) 23 return type(x) in [int, float, complex] 24 25 # ('+', ('*', 'a', 2), ('*', 'b', 7)) 26 def eval_exp(e): 27 if is_basic_exp(e): 28 return e 29 # 否则就是元组 30 op, a, b = e[0], eval_exp(e[1]), eval_exp(e[2]) 31 if op == '+': 32 return eval_sum(a, b) 33 elif op == '-': 34 return eval_diff(a, b) 35 elif op == '*': 36 return eval_prod(a, b) 37 elif op == '/': 38 return eval_div(a, b) 39 else: 40 raise ValueError('unknown operator', op) 41 42 def eval_sum(a, b): 43 if is_number(a) and is_number(b): 44 return a + b 45 if is_number(a) and a == 0: 46 return b 47 if is_number(b) and b == 0: 48 return a 49 return make_sum(a, b) 50 51 def eval_diff(a, b): 52 if is_number(a) and is_number(b): 53 return a - b 54 return make_diff(a, b) 55 56 def eval_prod(a, b): 57 if is_number(a) and is_number(b): 58 return a * b 59 return make_prod(a, b) 60 61 def eval_div(a, b): 62 if is_number(a) and is_number(b): 63 return a / b 64 if is_number(a) and a == 0: 65 return 0 66 if is_number(b) and b == 1: 67 return a 68 if is_number(b) and b == 0: 69 raise ZeroDivisionError 70 return make_div(a, b) 71 72 73 e = ('+', ('*', 5, 2), ('*', 'b', 7)) 74 print('yangxl', eval_exp(e))
扩充。。。
6.3 优先队列
优先队列是一种重要的缓存结构。从原理上说，优先队列与二叉树没有直接关系。但是基于对一类二叉树的认识，可以做出优先队列的一种高效实现。因此，本节可看作二叉树的应用。
6.3.1 概念
作为缓存结构，优先队列与栈和队列类似，可以将数据元素保存其中，可以访问和弹出。优先队列的特点是存入其中的每项数据都另外附有一个数值，表示这个项的优先程度，即优先级。优先队列应该保证，在任何时候访问或弹出的，总是优先级最高的元素。如果优先级最高的元素不止一个，具体访问或弹出哪一个由内部实现决定。
6.3.2 基于线性表的实现
首先考虑基于连续表实现优先队列。
有关实现方法的考虑
由于连续表可以存储数据元素，显然有可能作为优先队列的实现基础。数据项在连续表里的存储顺序可用于表示数据之间的某种顺序关系，对于优先队列，这个顺序可用于表示优先级关系，例如，让数据的存储位置按优先顺序排列。
但从使用的角度看，用户只关心优先队列的使用特性。按优先级顺序存储数据项是一种可能，但不必需。不难想到，实际上存在着两种可能的实现方案：
1）在存入数据时，保证表中元素始终按优先级顺序排列(作为一种数据不变式)，任何时候都可以直接取到当时表里最优先的元素。这种方式存入麻烦，但访问和弹出方便。
2）存入数据时采用最简单的方式(顺序表存入尾端，链表存入首端)。需要取用时，通过检索找到最优先元素。这种方式把选择最优元素的工作推迟到取用环节，存入效率高但取用麻烦。
在加入新元素时，设法确定正确的插入位置，保证表元素始终按优先顺序排列。为保证访问和弹出操作都能在O(1)时间完成，优先级最高的数据项应出现在表的尾端。
基于list实现优先队列
应该注意：任何时候都只能在合法范围内使用下标，超出范围的赋值或取值操作会引发IndexError异常。
比较优先级时，假定值较小的元素优先级更高。
1 #!coding:utf8 2 3 class PrioQueueError(ValueError): 4 pass 5 6 class PrioQueue: 7 def __init__(self, elist=[]): 8 ''' 9 :param elist: 引入参数可以提供一组初始元素。以可变对象作为默认值是一种危险动作，应特别注意(因为python中变量保存的是一个引用，例如li=[1, 2, 3], li2=li1, 如果修改li2, li就会改变)。 10 用list转换有两个作用，首先是对实参表(包括默认值空表)做一个拷贝，避免共享(原因同上)；
另外，这样可使实参是任何可迭代对象。 11 ''' 12 self._elems = list(elist) 13 self._elems.sort(reverse=True) 14 15 def enqueue(self, e): 16 ''' 17 需要先找到插入位置，比如把6插入[9, 7, 5, 3, 1]中 18 ''' 19 i = 0 20 while i < len(self._elems) and self._elems[i] > e: # 使用下标时，要时刻注意范围。 21 i += 1 22 self._elems.insert(i, e) 23 24 def is_empty(self): 25 return not self._elems 26 27 def peek(self): 28 if self.is_empty(): 29 raise PrioQueueError('no') 30 return self._elems[-1] 31 32 def dequeue(self): 33 if self.is_empty(): 34 raise PrioQueueError('no') 35 return self._elems.pop()
对连续表实现的分析
插入操作的复杂度为O(n)，其他操作都是O(1)。即使插入时表的存储区满，需要换一块存储，复杂度的量级仍是O(n)。
无论采用顺序表还是链表，在插入元素或取出元素时总有一种是O(n)操作。
6.3.3 树形结构和堆
下面考虑改善优先队列操作性能的可能性。
线性和树形结构
首先分析效率低的原因。按序插入操作低效，其根源是需要沿着表顺序检索插入位置。表长度为n，检索必然需要O(n)时间。这就说明，只要元素按优先级顺序线性排列，就无法避免线性复杂性问题。因此，必须考虑其他数据结构组织方式。
堆及其性质
从结构上看，堆就是结点里存储数据的完全二叉树，但堆中数据的存储要满足一种特殊的堆序：任一结点里所存的数据(按所考虑的序)先于或等于其子结点里的数据。
根据堆的定义，不难看到：
1）在一个堆中从树根到任何一个叶子结点的路径上，各结点里所存的数据按规定的优先关系(非严格)递减。
2）堆中最优先的元素必定位于二叉树的根结点里(堆顶)，O(1)时间就能得到。
3）位于树中不同路径上的元素，这里不关心其顺序关系。
如果所要求的序是小元素优先，构造出来的堆就是小顶堆，堆中每个结点的数据均小于或等于其子结点的数据。如果要求大元素优先，构造出来的堆就是大顶堆。
一棵完全二叉树可以自然而且信息完全地存入一个连续的线性结构，因此，一个堆也可以自然地存入一个连续表，通过下标就能找到树中任一结点的父/子结点。
堆和完全二叉树还有以下性质：
Q1 在一个堆的最后加一个元素(在相应连续表的最后加一个元素)，整个结构还是一棵完全二叉树，但未必是堆(因为未必满足堆序)。
Q2 一个堆去掉堆顶，其余元素形成两个“子堆”，完全二叉树的父子结点下标计算规则仍然适用，堆序仍然成立。
Q3 给Q2的两个子堆加入一个根元素，得到的又是一个完全二叉树，但未必是堆(还是堆序问题)。
Q4 去掉一个堆中的最后元素，剩下的元素仍构成一个堆。
堆与优先队列
现在考虑基于堆的概念和结构实现一种优先队列结构。
首先，用堆作为优先队列，可以直接得到堆中的最优先元素，O(1)时间。但要实现优先队列，还需要解决两个问题：
1）如何实现插入元素的操作：向堆中加入一个新元素，必须能通过操作，得到一个包含了所有原有元素和新元素的堆。
2）如何实现弹出元素的操作：从堆中弹出最小元素后，必须能把剩余元素重新做成堆。
插入和弹出都是O(logn)操作，其他操作都是O(1)。
6.3.4 优先队列的堆实现
解决堆插入和删除的关键操作称为筛选，又分为向上筛选和向下筛选。
插入元素和向上筛选
根据性质Q1，在堆的最后加入一个元素，得到的结果还是完全二叉树，但未必是堆，为把这样的完全二叉树恢复为堆，只需做一次向上筛选。
向上筛选的方法：不断用新加入的元素(设为e)与其父结点比较，如果e较小就交换两个元素的位置。通过这样的比较和交换，e不断上移，直到e的父结点不大于e或者e到达根结点，这时经过e的所有路径上的元素满足所需顺序，其余路径仍保持有序，因此这棵完全二叉树满足堆序，整个结构已恢复为一个堆。
向上筛选操作中比较和交换的次数不会超过二叉树中最长路径的长度。根据完全二叉树的性质，加入元素操作可以在O(logn)时间完成 (在尾端加入元素是O(1)操作，向上筛选时是逐层比较，所以是logn)。
弹出元素和向下筛选
由于堆顶元素就是最优先元素，应该弹出的就是它。但弹出堆顶元素后，剩下的元素已经不再是堆。根据性质Q2，弹出堆顶元素后，剩下的元素可以看作两个“子堆”。根据性质Q3，只需填补一个堆顶元素就能得到一个完全二叉树。根据性质Q4，取出原堆最后一个元素，其余元素仍然是堆。把这个元素放到堆顶就可以得到一个完全二叉树。这种情况下恢复堆的操作称为向下筛选。
假定两个子堆为A、B，根元素为e，操作步骤如下：
1）用e与A、B两个子堆的顶元素比较，最小者作为堆顶。
1. 若e不是最小，最小的必为A或B的根。设A的根最小，将其移到堆顶，相当于删除了A的顶元素。
2. 下面考虑把e放入去掉堆顶的A，这是规模更小的同一问题。
3. B的根最小的情况可以同样处理。
2）如果某次比较中e最小，以它为顶的局部树已成为堆，整个结构也成为堆。
3）或者e已落到底，这时它自身就是一个堆，整个结构也成为堆。
弹出栈顶元素，从堆最后取一个元素作为完全二叉树的根这两步都是O(1)操作，向下筛选这一步需要从完全二叉树的根开始做，一步操作需要做两次比较(先比较左右子结点选出较小结点，再拿较小结点与父结点比较)，操作次数不超过树中最长路径的长度。根据完全二叉树的性质，弹出元素也是O(logn)操作。
用堆实现的优先队列，加入和弹出都是O(logn)操作。
基于堆的优先队列类
在这个类的对象里，还是用list存储元素，在尾端加入元素，以首端作为堆顶。与前面基于顺序表实现的情况相反。
1 #!coding:utf8 2 3 class PrioQueueError(ValueError): 4 pass 5 6 class PrioQueue: 7 def __init__(self, elist=[]): 8 self._elems = list(elist) 9 if elist: 10 self.buildheap() # 传入的列表未必满足堆序 11 12 def is_empty(self): 13 return not self._elems 14 15 def peek(self): 16 if self.is_empty(): 17 raise PrioQueueError('error') 18 return self._elems[0] # 堆顶 19 20 def enqueue(self, e): 21 self._elems.append(None) # 加入一个假元素 22 self.siftup(e, len(self._elems)-1) 23 24 # 向上筛选，每步操作比较一次，O(logn)操作就是指筛选过程。 25 def siftup(self, e, last): 26 elems, i, j = self._elems, last, (last-1)//2 # 结点及其父结点的索引 27 while j >= 0 and e < elems[j]: # 树上是错的 29 elems[i] = elems[j] 30 # i = j 31 # j = (i-1)//2 # 更新后的i 32 i, j = j, (j-1)//2 # 可以认为是同时进行的，不分先后 33 # print('before', elems) # 当插入第三个数据时，[6, 8, 7] 34 elems[i] = e # 修改值，O(1)操作 35 36 def dequeue(self): 37 if self.is_empty(): 38 raise PrioQueueError('error') 39 elems = self._elems 40 e0 = elems[0] # 堆顶 41 e = elems.pop() 42 if len(elems): 43 self.siftdown(e, 0, len(elems)) 44 return e0 45 46 # 向下筛选 47 def siftdown(self, e, begin, end): # 不包括end 48 elems, i, j = self._elems, begin, begin*2+1 49 while j < end: # end位置没数值，所以j不能等于end 50 if j+1 < end and elems[j+1] < elems[j]: # `j+1 < end`表示有右子结点 51 j += 1 # 指向较小的值 52 if e < elems[j]: # 这里没有加"="，可以保证在关键码相等的情况下，先进先出。 53 break 54 elems[i] = elems[j] 55 i, j = j, 2*j+1 56 elems[i] = e 57 58 # 只在初始化时执行一次 59 def buildheap(self): 60 end = len(self._elems) 61 for i in range((end-2)//2, -1, -1): # 从下往上的向下筛选 # 循环导致堆构建操作是O(n)时间 62 self.siftdown(self._elems[i], i, end) 63 64 65 # prio = PrioQueue() 66 # print(prio._elems) 67 # prio.enqueue(8) 68 # print(prio._elems) 69 # prio.enqueue(7) 70 # print(prio._elems) 71 # prio.enqueue(6) 72 # print(prio._elems) 73 # prio.enqueue(5) 74 # print(prio._elems) 75 # prio.enqueue(4) 76 # print(prio._elems) 77 # [] 78 # [8] 79 # [7, 8] 80 # [6, 8, 7] 81 # [5, 6, 7, 8] 82 # [4, 5, 7, 8, 6]
self._elems序列就是堆的序列，二者在顺序上是一一对应的。
最后一个结点的父结点就是最后一个分支结点。
先考虑插入和删除操作，再考虑根据初始列表建堆的操作，因为建堆操作用到了在删除操作中的向下筛选方法。
最后考虑堆的初始创建，这里要基于一个已有的list建立初始堆。具体做法基于如下事实：一个元素的序列已经是堆；如果元素位置合适，在表里已有的两个“子堆”上加一个元素，通过一次向下筛选，就可以把这部分元素调整为一个更大的子堆。
把初始的表看作一棵完全二叉树，从下标(len-2)//2的位置开始，后面的表元素都是二叉树的叶子结点，也就是说，它们中的每一个已是一个堆。从这里开始向前做，也就是从完全二叉树的最下最右分支结点开始，向左一个个建堆，然后再到上一层建堆，直至整个表建成一个堆。
如果一个结点的下标为i(不管是左子结点还是右子结点)，则其父结点的下标为(i-1)//2。
构建操作的复杂性
总结：基于堆的概念实现优先队列，创建操作的时间复杂度为O(n)，该操作只做一次。插入和弹出操作的复杂度为O(logn)，效率比较高。插入操作的第一步是在表的最后加入一个元素，可能导致替换存储区，因此可能出现O(n)的最坏情况，但这保证了不会因为堆满而导致操作失败。空间复杂度都为O(1)。
6.3.5 堆的应用：堆排序
如果在一个连续表里存储的数据是一个小顶堆，按优先队列的操作反复弹出堆顶元素，能够得到一个递增序列。这种方式可用于对连续表进行排序。
使用堆排，还需要解决两个问题：
1）连续表里的初始元素序列通常不满足堆序。解决方法就是初始建堆操作。
2）选出的元素放在哪里？能否不使用其他空间。解决方法：每弹出一个元素，表尾就会空出一个位置，正好用于存放弹出元素。
1 def heap_sort(elems): 2 def siftdown(elems, e, begin, end): 3 i, j = begin, begin * 2 + 1 4 while j < end: 5 if j + 1 < end and elems[j + 1] < elems[j]: 6 j += 1 7 if e < elems[j]: 8 break 9 elems[i] = elems[j] 10 i, j = j, 2 * j + 1 11 elems[i] = e 12 13 end = len(elems) 14 for i in range(end // 2, -1, -1): # 从下往上的向下筛选 15 siftdown(elems, elems[i], i, end) 16 # 逐个取出最小元素将其放在表的最后，放一个退一步，得到从大到小排列的序列 17 for i in range(end-1, 0, -1): 18 e = elems[i] 19 elems[i] = elems[0] 20 siftdown(elems, e, 0, i) # 每次参与向下筛选的都少一个
复杂度分析，初始建堆为O(n)时间，第二个循环总开销为O(nlogn)。空间复杂度为O(1)。
利用小根堆排出来的是递减序列，利用大根堆排出来的是递增序列。
6.4 应用：离散时间模拟
。。。
6.5 二叉树的类实现
基于顺序表的二叉树，前面已讲过，下面是基于链表的。
6.5.1 二叉树结点类
1 class BinTNode: 2 def __init__(self, data, left=None, right=None): 3 ''' 4 :param data: 结点数据 5 :param left: 左子结点 6 :param right: 右子结点 7 left和right为默认值时，data为叶子结点。 8 ''' 9 self.data = data 10 self.left = left 11 self.right = right
基于BinTNode类构造的二叉树具有递归的结构，很容易采用递归方式处理。下面两个函数展示了处理这种二叉树的典型技术：
1 def count_BinTNodes(t): 2 if t is None: 3 return 0 4 else: 5 return 1 + count_BinTNodes(t.left) + count_BinTNodes(t.right) 6 7 def sum_BinTNodes(t): 8 if t is None: 9 return 0 10 else: 11 return t.data + sum_BinTNodes(t.left) + sum_BinTNodes(t.right)
递归定义的二叉树操作具有同一的模式，包括两个部分：
1）描述对空树的处理，应直接给出结果。
2）描述非空树情况的处理：
1. 如何处理根结点(直接给出结果，如上面两个函数中的`1`和`t.data`)。
2. 通过递归调用分别处理左右子树。
3. 基于上述三个部分的结果得到整个树的结果。
6.5.2 遍历算法
递归定义的遍历函数
要实现按深度优先方式遍历二叉树，采用递归方式定义函数非常简单。
1 # 按先根序遍历二叉树的递归函数 2 def preorder(t, proc): # 假定t的实际参数是BinTNode对象。 3 if t is None: 4 return 5 proc(t.dat) 6 preorder(t.left) 7 preorder(t.right)
按中根序和后根序遍历二叉树的函数与此类似，只是其中几个操作的排列顺序不同。
宽度优先遍历
要实现按宽度优先方式遍历二叉树，需要一个队列。使用前面定义的SQueue类。
1 def levelorder(t, proc): 2 qu = SQueue() # 队列 3 qu.enqueue(t) 4 # 首先把根结点入队，之后出队时将其左右子结点入队，这样每出队一层，就会入队下一层。 5 while not qu.is_empty(): 6 t = qu.dequeue() 7 if t is None: # 空树 8 continue 9 if t.left: 10 qu.enqueue(t.left) 11 if t.right: 12 qu.enqueue(t.right) 13 proc(t.dat)
非递归的先根序遍历函数
下面讨论非递归定义的深度优先遍历算法。
在三种深度优先遍历中，先根序遍历方式的非递归描述最简单。
根据已有认识，在这个函数里需要一个栈，保存树尚未访问过的信息。
思路：
1）由于采用先根序，遇到结点就应该访问，下一步应该沿着树的左枝下行。
2）但结点的右分支还没访问，因此需要记录，将右子树存入栈。
3）遇到空树时回溯(空树指的是叶子结点的左右子树)，取出栈中保存的一个右分支(最下层的那个右分支)，像一棵二叉树一样遍历它。
循环中需要维持一种不变关系：假设变量t一直取值为当前待遍历子树的根，栈中保存着前面遇到但尚未遍历的那些右子树。这样，只要当前树非空或栈不为空，就继续循环。
循环体中应该先处理当前结点的数据，而后沿着树的左分支下行，一路上把经过结点的右分支压入栈，与此也需要用一个循环。内部循环直至遇到空树时回溯，从栈中弹出一个元素(最近的一棵右子树)，要做的工作也是遍历一棵二叉树。
1 def preorder_nonrec(t, proc): 2 s = SStack() 3 while t or not s.is_empty(): # 首次弹出的是None，如果不判断栈为空程序就终止了 5 while t: 6 proc(t.data) 7 # if t.right: # 如果加上了这个条件，单点树会在pop时报错 8 s.push(t.right) 9 t = t.left 10 t = s.pop()
或者，
1 def preorder_nonrec(t, proc): 2 ls = LStack() 3 while t or not ls.is_empty(): 4 if t: 5 proc(t.data) 6 ls.push(t.right) 7 t = t.left 8 continue 9 t = ls.pop() 10 11 t = BinTNode(3, BinTNode(2, BinTNode(4, BinTNode(5), BinTNode(9)), BinTNode(7)), BinTNode(1, None, BinTNode(6))) 12 preorder_nonrec(t, print)
时间复杂度：在整个执行中将访问每个结点一次，所有右子树被压入、弹出栈各一次(栈操作为O(1))，proc(t.data)操作的复杂性与树的大小无关，所以整个遍历过程需要花费O(n)时间。
空间复杂度：关键因素是，遍历过程中栈可能达到的最大深度，而栈的最大深度由被遍历的二叉树的高度决定。由于二叉树高度可能达到O(n)，所以在最坏情况下，算法的空间复杂度是O(n)。由于n个结点的二叉树的平均高度是O(logn)，所以非递归先根序遍历的平均空间复杂度为O(logn)。
特别提醒：只把非空的右子树入栈，可以减少一些空间开销。
通过生成器函数遍历
用python写程序，在考虑遍历数据汇集结构的时候，总应该想到迭代器。这句话逼格满满啊(doghead)。
非递归的后根序遍历算法
。。。
二叉树遍历小结：
6.5.3 二叉树类
1 class BinTNode: 2 def __init__(self, data, left=None, right=None): 3 self.data = data 4 self.left = left 5 self.right = right 6 7 class BinTree: 8 def __init__(self): 9 self._root = None 10 11 def is_empty(self): 12 return self._root == None 13 14 def root(self): 15 return self._root 16 17 def leftchild(self): 18 return self._root.left 19 20 def rightchild(self): 21 return self._root.right 22 23 def set_root(self, rootnode): 24 self._root = rootnode 25 26 def set_left(self, leftchild): 27 self._root.left = leftchild 28 29 def set_right(self, rightchild): 30 self._root.right = rightchild
看着没啥用。
6.6 哈夫曼树
哈夫曼树是一种重要的二叉树，在信息领域有重要的理论和实际价值。
6.6.1 哈夫曼树和哈夫曼算法
构造哈夫曼树的算法
从任意的实数集合构造出与之对应的哈夫曼树。构造算法描述如下：
注意，给定集合W上的哈夫曼树不唯一。如果T是集合W上的哈夫曼树，交换其中任意一个或多个结点的左右子树，得到的仍是W上的哈夫曼树。
6.6.2 哈夫曼算法的实现
构造算法
显然，构造算法执行中需要维护一组二叉树，而且要知道每棵树的权值。可以考虑用二叉树的结点类构造哈夫曼树，在树根结点记录树的权值。
在算法执行中，需要不断选出权值最小的两棵二叉树，并基于它们构造一棵新二叉树。很容易想到，最佳选择是用一个优先队列存放这组二叉树，按二叉树根结点的权。值排列优先顺序，从小到大。
算法开始时建立起一组单点树，以权值作为优先码存入优先队列，要求先取出优先队列里的最小元素，然后反复做下面两件事，直至优先队列里只有一个元素：
1）从优先队列里弹出两个权值最小的二叉树。
2）基于所取的两棵二叉树构造一棵新二叉树，其权值为两棵子树的权值之和，并将新构造的二叉树压入优先队列。
除此之外，还有两个问题必须解决：需要为二叉树定义一个序，权值小的二叉树在前；需要检查优先队列中的元素个数，以便在只剩一棵时结束。
1 class BinTNode: 2 def __init__(self, data, left=None, right=None): 3 self.data = data 4 self.left = left 5 self.right = right 6 7 class HTNode(BinTNode): 8 '''增加了一个"小于"比较操作，用于HTNode对象比较大小，PrioQueue.siftup方法用到了''' 9 def __lt__(self, other): 10 return self.data < other.data 11 12 # PrioQueue.downsift方法用到了 13 def __ge__(self, other): 14 return self.data >= other.data 15 16 class HuffmanPrioQ(PrioQueue): 17 '''增加了一个检查队列中元素个数的方法''' 18 def number(self): 19 return len(self._elems) 20 21 def huffman(weights): 22 trees = HuffmanPrioQ() 23 for w in weights: 24 trees.enqueue(HTNode(w)) 25 while trees.number() > 1: 26 w1 = trees.dequeue() 27 w2 = trees.dequeue() 28 trees.enqueue(HTNode(w1.data + w2.data, w1, w2)) 29 return trees.dequeue() # 返回的就是对应二叉树 30 31 lst = [2, 3, 7, 10, 4, 2, 5] 32 t = treesman(lst)
HTNode中重新定义了几个比较对象大小方法。惊艳到我了。。
算法分析
哈夫曼树构造算法的时间复杂度主要是两个循环。第一个循环建立起m棵二叉树，并把它们加入到优先队列，这部分的时间复杂度为O(m*logm)。如果采用初始建堆的方法，可以把这部分的时间复杂度降为O(m)，但空间消耗会增加，代码中已给出。第二个循环需要做m-1次，每次减少一棵树。构造新树的时间复杂度与m无关，是O(1)操作，这部分的时间复杂度也为O(m*logm)。所以这个算法的时间复杂度为O(m*logm)。
算法执行中，构造出一棵包含2m-1个结点的树，所以其空间复杂度为O(m)。
6.6.3 哈夫曼编码
哈夫曼树有许多应用，针对不同应用，需要给树中的权值赋予不同的意义。一个重要应用是哈夫曼编码，这是当年哈夫曼研究并提出哈夫曼树的出发点，在信息理论里有重要的理论意义和实际价值。
哈夫曼编码的生成
例子，
编码方式不唯一，因为哈夫曼树不唯一。
还没实现代码。。
6.7 树和树林
一般的树和树的集合，称为树林。树代表很广泛的一类树形结构，在许多方面有与二叉树类似的概念，但二叉树并不是树的特例。
作为树形结构，树具有前面提出的树形结构的所有共性性质。
6.7.1 实例和表示
集合表示，
图示表示，
嵌套括号表示法，
6.7.2 定义和相关概念
树是具有递归性质的结构，其定义也是递归的。
相关概念
一些概念与二叉树类似。除此之外，在有序树中可以考虑子结点的顺序，因此可以说最左结点。与二叉树不同的是，树的度数可以任意，这里定义为该树中度数最大的结点的度数。
最后请注意，二叉树中的子结点有明确的左右之分，而且其结点的最大度数为2。在度数为2的有序树中结点也有序且最大度数为2。但二者却是不同的概念。不同之处只有一点：假设树中的某个分支结点只有一个子结点，在二叉树中必须说明它是左分支还是右分支，而在度数为2的有序树中就没有这个概念了。
树林
0棵或多棵树(显然互不相交)的集合称为一个树林。
树、树林与二叉树的关系
存在一种一一对应关系，可以把任何一个(有序)树林映射到一棵二叉树，而其逆映射把这棵二叉树映射回原来的树林。这个映射定义如下：
树的性质
6.7.3 抽象数据类型和操作
树的遍历
与二叉树类似。
6.7.4 树的实现
。。。