一般练习
1.
复习下面概念：树形结构，树根，前驱，后继，二叉树，左子树和右子树，空树，单点树，父结点/子结点，左/右子结点，父子关系，祖先/子孙关系，祖先/子孙结点，树叶，分支结点，结点的度数，路径，路径长度，结点的层数，树的高度（深度），满二叉树，扩充二叉树，内部结点和外部结点，内部路径长度和外部路径长度，完全二叉树，二叉树的遍历，深度优先遍历，先根序（先序）遍历，中根序（对称序/中序）遍历，后根序（后序）遍历，先根序列，对称（中根）序列，后根序列，宽度优先遍历（按层次顺序遍历），层次序列，表达式树，二元表达式，算术表达式，表达式求值，优先队列，优先关系，优先级，堆，堆序，小顶堆，大顶堆，筛选（向下筛选，向上筛选），堆排序，离散事件模拟，模拟框架，事件队列，宿主系统，二叉树的链接实现，二叉树结点类，非递归的二叉树遍历算法，非递归后序遍历，下行循环，二叉树类，带权扩充二叉树，哈夫曼树（最优二叉树），哈夫曼算法，哈夫曼编码，最优编码，树和树林，树根，有序树和无序树，有序树林和无序树林，搜索树，子结点引用表示法，父结点引用表示法，长子-兄弟表示法。
2.
三个结点a, b, c可以构造出多少棵不同的二叉树？请画出它们。
3.
四个结点可以构造出多少棵不同的（一般的）树？请画出它们。
4.
若一棵二叉树有10个度为2的结点，6个度为1的结点，它有几个叶结点？
5.
已知一棵二叉树有36个叶结点，这棵树的全部结点至少有多少个？
6.
将二叉树的概念推广到三叉树，一棵244个结点的三叉树至少有多高？
7.
请根据二叉树的几种结构形态，严格证明扩充二叉树的外部路径长度和内部路径长度之间的的关系式
。
8.
二叉树采用嵌套的list表示时空表表示空树。请总结出空表的个数与树中分支结点和叶结点个数的关系公式，并严格证明这一关系公式。
9.
对于图6.30中的二叉树，请：
a)
做出其先根序、中根序和后根序序列；
b)
将其转换为树（或树林），而后做出得到的树（或树林）的先根序、中根序和后根序序列；
c)
比较和讨论上面两组遍历得到的结果。
10. 对图6.30的二叉树，做出其扩充二叉树，并求出这棵扩充二叉树的内部路径长度和外部路径长度。
11. 已知一个算术表达式树的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，请给出其前缀形式。
12. 如果知道了一棵二叉树的先根序列和后根序列，能够确定原来的二叉树吗？如果能请证明之，不能请举出反例。
13. 确定所有满足下面条件的二叉树
a)
其先根序列与中根序列相同；
b)
其后根序列与中根序列相同；
c)
其后根序列的反转与其的中根序列相同；
d)
其先根序列与后根序列相同。
14. 满足什么条件的非空二叉树的先根序列正好等于其后根序列的反转？
15. 请证明下面结论：在一棵树的先根序列、中根序列和后根序列中，所有树叶结点的相对位置都一样。
16. 什么是前缀编码？说明如何利用二叉树设计二进制的前缀编码？其实前缀编码并不限于二进制编码，请考虑如何推广这个概念。
17. 下面几个符号编码集合中，哪些是或不是前缀编码：
a)
{0, 10, 110, 11101, 10111} b) {11, 10, 001, 101, 0001}
c)
{00, 010, 0110, 1010, 1001} d) {b, c, aa, ac, aba, abb, abc}
18. 假设通讯中使用的字符a, b, c, d, e, f, g, h, i,
j, k在电文中出现的频率分别是3,
8, 5, 17, 10, 6, 19, 15, 23, 16, 9，请做出相应的哈夫曼编码。
19. 假设用于通讯的电文都由8个字母组成，这些字母在电文中出现的频率分别为7, 19, 4, 6, 32,
3, 21, 12。请做出8个字母的哈夫曼编码。另外，采用0～7的二进制表示形式是另一
种编码方案。请比较这两种编码方案的优缺点。
20. 请证明哈夫曼设法的正确性，即，通过该算法构造出的二叉树一定是哈夫曼树。
21. 在一棵树中只有度数为
的结点和度数0的叶结点（也就是说，它是一棵满的k叉树）。已知树里有m个度数为k的结点，它有多少叶结点？
22. 设树林F包含三棵树，其结点个数分别为N1、N2和N3。T是与F对应的二叉树，T的根结点的右子树有多少个结点？
23. 假设树
包含
个度数为1的结点，
个度数为2的结点，……，
个度数为
的结点，该树有多少个叶结点？
24. 请考虑如何写出一个算法判断一棵二叉树是否满二叉树，另外设计一个算法判断一棵二叉树是否完全二叉树。
25. 假设现在需要交换一棵二叉树中各结点的左右子树，请设计完成这一操作的递归算法和非递归算法。
编程练习
1.
请基于6.2节的讨论，基于Python的list实现一种二叉树类。
2.
请完成6.2.2节的二元表达式求值器。
3.
请在表达式的list表示基础上完成下面工作：
a)
定义函数variables(exp)，它求出表达式exp里出现的所有变量的集合；
b)
扩充正文中的函数evel_exp，增加一个参数values，对应实参应是一个字典，以可能在表达式里出现变量为关键码，关联到变量的值。这个eval_exp求值中遇到变量时检查该字典，用字典提供对应值取代这个变量；
c)
设exp是可以包含变量的代数表达式（只有加和乘运算），请定义函数derive(exp, var)，它给出exp对变量var的导函数表达式。
4.
基于上述工作实现一个交互式的二元表达式计算器，其中定义一种（程序）变量机制，可用于记录前面输入的表达式或已做计算的值。
5.
参考6.2.2节最后的讨论，基于上一题的工作扩充，实现一个具有更广泛可用性的表达式计算器。
6.
请定义一个二元表达式类，在其中实现一些重要的表达式计算。
7.
第6.3.2节讨论了基于线性表的优先队列实现。其中在提出方法2的最后，概述了一种临时记录检索到的最优先元素的技术。请进一步开发这种技术，实现一个采用这种技术的优先队列类型。请仔细分析该节中提出的几种技术的优缺点。
8.
请修改海关检查站模拟系统，改用每个检查通道一个等待队列的管理策略。对这种新策略做一些模拟，并将模拟结果与共用等待队列的策略比较。
9.
假定一个银行网点有4个服务柜台，每个柜台前可能有一个等待队列。顾客到达时如果有空闲柜台就直接去办理业务，没有空柜台就选择当时最短的队列排队等待。此外，如果某柜台业务员空闲且其等待队列已空，该业务员将从当时有人的某个队列叫一个顾客过来。请做一个系统模拟该网点的运转：先选择一组可以根据情况设定的模拟参数，而后开发这个系统。最后选择几组不同的参数做一些模拟。
10. 第6.5.2节定义了一个输出二叉树的函数。请写一个读入这种输出形式，构造出相应的二叉树的函数。假设结点里保存的数据是整数。
11. 修改第6.5.2节给出的非递归定义的先根序遍历函数，只在右子树非空时才将其进栈。考虑这时的循环条件和函数内的语句，尽可能做些优化。
12. 请设法定义非递归的先根序和中根序遍历函数，使栈空间的使用达到最少。请论证所定义函数确实具有这种性质。
13. 请为第6.5.2节的二叉树类增加下面方法，其中相等判断、拷贝、结点计数等请考虑递归和非递归两种实现，还请考虑能否借助类中已有的遍历操作实现：
a)
一个层次序的遍历方法；
b)
方法 __eq__(self, another) 判断另一棵树another是否与self相等。两棵树相等当且仅当其结构相同且每个结点的数据相等；
c)
方法clone(self) 生成self的一个拷贝；
d)
方法count_nodes(self) 返回树中叶结点个数和非也结点个数的序对。
14. 设二叉树不同结点的标识唯一。假定有了一棵二叉树的先序序列和中序序列，分别用Python的表表示，请定义一个函数生成该二叉树的嵌套表形式。
15. 请将Python的list或tuple作为内部表示，定义一个类实现二叉树数据类型。并请对比这种实现与本章正文中定义结点类和二叉树类的实现。
16. 请考虑第6.5.3节最后提出的带父结点链接的二叉树实现方法，定义这种二叉树类，并认真研究这种类上的算法。请尽可能地利用新增加的指针提高操作效率，并设法减少算法的辅助空间开销。
17. 定义一个函数，对任何给定的字符集及其出现概率，生成对应的哈夫曼编码。
18. 请基于Python的list对象实现一个基于父结点引用的树类，参考树抽象数据类型类型，实现相关的操作。
19. 请基于子结点表技术的基本思想，设计和实现一个树类，定义必要的操作。
20. 请完成第6.7.5节提出的借助于Python语言内置类型list的树实现，定义必要的操作。也可以自己做出另一种设计。
21. 第6.7.5节的最后提出了两种树类的实现技术。请参考那里的讨论，实现一个或者两个完整的树类，实现必要的操作。
22. 假设需要保存的元素分为5个不同的优先级，但希望相同优先级的元素能按照FIFO顺序被取出使用。请设计并实现一种能满足这一需要的数据结构。