数据结构习题详解ustc

金培晟 Jarfield

第六章 树和二叉树

6.1

【题目】试分别绘出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。

【解析】

• “树”默认有根的普通树（孩子个数不限、孩子之间无左右次序），忽略结点标号，仅按形态区分。3 个结点时共有 2 种不同形态：一条链、以及根有两个孩子的“星形”。

• “二叉树”中左右次序有别（有序二叉树），因此 3 个结点时的不同形态数为 Catalan 数 ：一棵满二叉三结点树 + 四种单支/折线形（分别位于左或右，或呈“折”形）。

【答案】

一、具有3个结点的树

1. ●
   |
   ●
   |
   ●
      

2.   ●
    / \
   ●   ●
      

二、具有 3 个结点的二叉树

1.   ●
    / \
   ●   ●
   
      

2.     ●
      /
     ●
    /
   ●

3.   ●
    /
   ●
    \
     ●
      
      

4. ●
    \
     ●
      \
       ●
      
      

5. ●
    \
     ●
    /
   ●
      
      

6.4

【题目】一个深度为 H 的满 k 叉树有如下性质：第 H 层上所有结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树。如果从 1 开始按自上而下、自左向右的次序对全部结点编号，问：
(1) 各层的结点数目是多少？
(2) 编号为 i 的结点的父结点(若存在)的编号是多少？
(3) 编号为 i 的结点的第 j 个孩子(若存在)的编号是多少？
(4) 编号为 i 的结点有右兄弟的条件是什么？其右兄弟的编号是多少？

【解析】

• 假定：层次从 1 开始计数（根在第 1 层，叶在第 H 层），k≥2。
• 满 k 叉树第 t 层结点数为 ；到第 t 层的累计结点数为 。
• 全树结点总数 。
• 按层序（自上而下、左到右）从 1 编号时，可把“父与其 k 个孩子”看作连续块：
  • 结点 i 的第 j 个孩子（1≤j≤k）紧跟在前面 个孩子之后，因此位于下标 。
  • 除根外，每个结点 i（i≥2）都处在其父亲的 k 个孩子块中；块的起点决定了父编号公式。
• 右兄弟：同一父亲的孩子相邻，结点 i 不是其父亲的第 k 个孩子时，右兄弟就是 i+1。用模运算表示即 （且 i>1）。

【答案】
(1) 第 t 层（t=1,2,…,H）的结点数：。

累计到第 t 层：；全树总数：。

(2) 结点 i 的父结点编号：

(3) 结点 i 的第 j 个孩子（1≤j≤k）编号：

存在条件：结点 i 不在第 H 层（等价于 ）。

(4) 右兄弟存在的充要条件： 且 （即 i 不是其父亲的第 k 个孩子）。
此时右兄弟编号：。

6.5

【题目】 已知一棵度为 的树中有 个度为 1 的结点， 个度为 2 的结点，…， 个度为 的结点，问该树中有多少个叶子结点？

【解析】

• 约定：“度”为孩子数，叶子结点的度为 0，记叶子数 。

• 设全树结点总数 。树的边数：。

• 另一方面，各内部结点的出度和即边数：。

• 两式相等并整理：
  
  即叶子结点数与各度结点数的关系式。

【答案】

（其中 为叶子结点个数）

6.11

【题目】 已知某二叉树的中序序列为 DCBGEAHFIJK，后序序列为 DCEGBFHKJIA，请画出该二叉树。

【解析】

• 根结点 = 后序最后一项 A。
• 按 A 切分中序：左中序 DCBGE，右中序 HFIJK。
  去掉 A 的后序为 DCEGBFHKJI，对应分为左后序 DCEGB 与右后序 FHKJI。
• 左子树（中序 DCBGE，后序 DCEGB）：
  • 根 B（左后序末）。
  • 以 B 切分中序：左 DC、右 GE；后序相应为 DC、EG。
  • 左部分根 C（DC 末），其左孩子 D；右部分根 G（EG 末），其右孩子 E。
• 右子树（中序 HFIJK，后序 FHKJI）：
  • 根 I（右后序末）。
  • 以 I 切分中序：左 HF、右 JK；后序相应为 FH、KJ。
  • 左部分根 H（FH 末），其右孩子 F；右部分根 J（KJ 末），其右孩子 K。

【答案】

       A
     /   \
    B     I
   / \   / \
  C   G H   J
 /     \  \   \
D       E  F   K

6.14

【题目】 假设某个电文由 8 个字母组成，每个字母在电文中出现的次数分别为 。试回答：
(1) 画出 Huffman 树；
(2) 写出每个字母的 Huffman 编码；
(3) 最优二进制编码后，电文的二进制位数。

【解析】

• 采用 Huffman 贪心合并（每次取当前最小的两棵子树合并）。约定：左分支记 ，右分支记 。
• 合并过程（频次作为权重）：
  7. （根）

说明：Huffman 在相同权的分支选择上可能有多种形态，编码不唯一，但总位数最优值相同。

【答案】
(1) Huffman 树（左 / 右 ）：

          (100)
         /     \
     (40)       (60)
    /    \     /     \
b:19    g:21 (28)     e:32
             /   \
          (11)   (17)
          / \     / \
        (5) d:6 a:7 h:10
        / \
      c:2 f:3

(2) Huffman 编码（左 / 右 ）：

字母	频次	编码	码长	频次×码长
a	7	1010
b	19	00
c	2	10000
d	6	1001
e	32	11
f	3	10001
g	21	01
h	10	1011

(3) 电文最优总二进制位数：