数据结构期末复习——树与二叉树一些知识点

1. 满二叉树：一棵深度为k 且有

个结点的二叉树。（特点：每层都“充满”了结点）

1. 完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应.
2. 具有n个结点的完全二叉树的深度为log2(n)向下取整 + 1.
3. 满二叉树和完全二叉树的区别:满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例.
4. 完全二叉树中度数为1的结点的个数为0或者为1。
5. 在非空二叉树中，第i层的结点总数不超过

, i>=1.

1. 深度为h的二叉树最多有

个结点(h>=1)，最少有h个结点.

1. 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
2. 问题：具有1102个结点的完全二叉树的一定有___个叶子结点。 分析： 边数m=n-1，那么m = n1 + 2×n2； 而在完全二叉树中度数为1的点只有1个或0个，所以代入0或1，当n2为整数时得出n2的值， 再利用n0=n2+1可得叶子结点的个数。
3. 由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 关于根据先序序列和中序序列确定二叉树，由中序序列和后序遍历确立一棵二叉树的方法见链接1，链接2
4. 一棵有n个叶子结点的Huffman树有2n-1个结点.
5. 森林结点数，边数与树个数的关系

关于哈夫曼编码有这么几道题注意下：

1. 设一段文本中包含字符{a, b, c, d, e}，其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后，文本所占字节数为： (2分) A.40 B.36 C.25 D.12 思路：这道题目其实问的就是哈夫曼树的带权路径长度是多少。
2. 设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？ (2分) A.0 B.2 C.4 D.5 思路： 关于采用等长方式的编码需要多少位，可以这样想： 在等长编码中，每个对象就用两位数表示，我们可以定义a:01 b:11 c:10 d:00 按照等长编码的文本长度为2×12=24 按照哈夫曼编码文本长度为4×2+2×3+5×1+1×3=22 故节省2位。