chapter05
复制本地路径 | 在线编辑
1. 树和森林的表示
1.1 简述父节点+孩子节点表示法的实现方式
1.2 简述长子兄弟法的实现方式
1.3 简述森林和二叉树之间的相互转化
2. 二叉树的性质
2.1 证明对于任一节点v, depth(v) + height(v) <= height(T)
2.2 设二叉树高度为h，对于深度为k的叶节点有
3. 三种遍历
3.1 基础: 给出寻找节点succ()的代码
3.2 直接给出代码--先序遍历两个，中序遍历四个，后序遍历一个
4. 层次遍历
4.1 证明辅助队列Q.size == upper(n/2)即可保证不会溢出
4.2 根据4.1，说明哪一种情况会让Q.size的确需要那么多的容量
4.3 根据4.2，说明在这一情况中，Q.size为最大值时一共有多少次
5. 编码树
5.1 证明编码树一定是真二叉树(双子性)
5.2 证明编码树的叶子节点深度之差不超过1(层次性)
5.3 证明Huffman树仍然是真二叉树
5.4 证明Huffman树就是最优编码树
6. 完全二叉树
6.1 完全二叉树可以用向量表示，若根节点是0，那么如何判断两个节点是否是祖先-后代
6.2 完全二叉树的叶节点数为i，内部节点数为j，证明0 <= i - j <= 1
6.3 完全二叉树的层次遍历时，证明辅助对列Q.size是单峰对称的