【www.gbppp.com--题目解答】
第5章 树
【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。
图5-1 解：
（1）叶子结点有：B、D、F、G、H、I、J。 （2）非终端结点有：A、C、E。
（3）每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。 （4）树的深度为3。
【例5-2】一棵度为2的树与一棵二叉树有什么区别？
解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别？
解：区别有两点：
（1）二叉树的一个结点至多有两个子树，树则不然；
（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。
【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。
解：如图5-2(a)所示，具有3个结点的树有两种不同形态。
图5-2(a) 如图5-2(B)所示，具有3个结点的二叉树有以下五种不同形态。
图5-2(b)
【例5-5】如图5-3所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。
解：
（1）顺序表示。
（2）该二叉树的二叉链表表示如图5-4所示。
图5-4
【例5-6】试找出满足下列条件的所有二叉树：
（1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。 解：
（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；
（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；
（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。
【例5-7】如图5-5所示的二叉树，要求：
（1）写出按先序、中序、后序遍历得到的结点序列。
（2）画出该二叉树的后序线索二叉树。 解：
（1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA （2）其后序线索二叉树如图5-6所示。
图5-5
图5-6
【例5-8】将图5-7所示的树转换为二叉树。 I J 图5-7
解：第一步，加线。第二步，抹线。第三步，旋转。过程如图5-8所示。
E C E
I J I J
L
图5-8(b) 第二步 抹线 图5-8(a) 加线
C F
E
K G
L H
I
J
图5-8(c) 第三步 旋转
C
J F I
图5-9
【例5-9】将如图5-9所示的二叉树转换为树。
解： 第一步，加线。第二步，抹线。第三步，调整。过程如图5-10所示。
J I J J I I
第一步 第二步 第三步
图5-10
【例5-10】将如图5-11所示的森林转换成二叉树。
I F
图5-11
解： 步骤略，结果如图5-12所示。
J
F
I J
图5-12
【例5-11】假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。
解： 根据题意，设这8个字母对应的权值分别为（5，25，4，7，9，12，30，8），并且n=8。
（1）设计哈夫曼树的步骤如图5-13所示。
5 4 7 9 8 第一步：【关于树的问题和解答,】
第二步： 7 9 8
第四步：第三步：
9
第五步：
第七步： 9
第六步： 4
第八步：
7 9 4 5
9
8 4 5 7
图5-13
（2）设计哈夫曼编码
利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：
A:0011 B:01 C:0010 D:1010
《测树学（本科）》在线作业及答案
一、单选题（共 15 道试题，共 75 分。） 1. 区划森林的最小地域单位是（ B）。
A. 标准地
B. 林分
C. 小班
D. 样地 满分：5 分
2. 下列关于树木生长方程的特点，错误的是（C ）。
A. 当t=0时，y(t)=0，这是树木生长方程需满足的初始条件；
B. y(t)存在一条渐近线y(t)=A，A是该树木生长极大值；
C. 由于树木生长是依靠细胞的增殖不断增长的，所以y(t)是关于年龄t的单调增函数；
D. y(t)是关于t的连续光滑的函数曲线。 满分：5 分
3. 由于受外界外界环境条件的制约，是年轮环带产生不完整的现象称为（C ）
A. 年轮变态
B. 年轮畸形
C. 年轮变异
D. 年轮消失 满分：5 分
4. 树干材积与以胸高断面积为底面积、以树高加3米为高的比较圆柱体体积之比称作（A ）。
A. 平均实验形数
B. 绝对形数
C. 正形数
D. 胸高形数 满分：5 分
5. 平均断面积近似求积式是在假设树干干形为（ C）的条件下得到的。
A. 圆柱体
B. 圆锥体
C. 抛物体
D. 凹曲线体 满分：5 分
6. 伐倒木近似求积式中误差百分率最小的是（C ）
A. 中央断面积近似求积式
B. 平均断面积近似求积式
C. 牛顿近似求积式
D. 都一样 满分：5 分
7. 林分平均胸径是指（B）
A. 林分内所有林木直径的算术平均值
B. 林分平均断面积所对应的直径
C. 林分内具有平均生长状态的树木的直径
D. 林分内具有指定平均材积的树木的直径 满分：5 分
8. 在树木各调查因中，断面积生长率Pg与胸径生长率PD的关系式是（ B）。
A. Pg=PD
1
B. Pg=2PD
C. Pg=1/2PD
D. Pg=1/4PD 满分：5 分
9. 树干的横断面形状更接近于（ B）。
A. 圆形
B. 椭圆形
C. 不规则的封闭曲线
D. 不确定 满分：5 分
10. （A ）是可以直接测定的因子
A. 胸径
B. 断面积
C. 材积
D. 形数 满分：5 分
11. 角规绕测树木时，当缺口与树木胸径相切时，记数为（B ）。
A. 1
B. 0.5
C. 2
D. 0 满分：5 分
12. 在坡地上测量胸径时，测者所处位置应为（A）
A. 坡上
B. 坡下
C. 平坡处
D. 以上都可以 满分：5 分
13. 在树种组成式中，某一树种的蓄积量不足林分总蓄积的2％，则在组成式中如何表示（ ）。
A. 1
B. +
C. -
D. 忽略不计 满分：5 分
14. 孔兹干曲线式y2=pxr中x代表（C ）。
A. 树干根颈到横断面的长度
B. 树干横断面的半径
C. 树干梢头到横断面的长度
D. 树干横断面的周长 满分：5 分
15. 采用平均标准木法测定林分蓄积量时，平均标准木是指树木具有（A ）。
A. 平均材积
B. 平均断面积
C. 平均直径
D. 平均高 满分：5 分
2
二、多选题（共 5 道试题，共 25 分。）
1. （BCD）可以独立反映树木干形。
A. 胸高形率
B. 绝对形率
C. 正形数
D. 正形率 满分：5 分
2. 标准地的形状有（ABC）。
A. 方形
B. 圆形
C. 带状
D. 任意形状 满分：5 分
3. 下列划分林分的标准，正确的是（ABC）。
A. 各林层每公顷蓄积量大于30m3；
B. 相邻林层间林木平均高相差20%以上；
C. 各林层平均胸径在8cm以上；
D. 主林层郁闭度大于0.4，其他林层大于0.1； 满分：5 分
4. 立木材积近似求积式包括（BC）。
A. 平均断面积求积式
B. 平均实验形数
C. 形数法
D. 中央断面积求积式 满分：5 分
5. 下列关于树木生长方程的特点，正确的是（ABD）。
A. 当t=0时，y(t)=0，这是树木生长方程需满足的初始条件；
B. y(t)存在一条渐近线y(t)=A，A是该树木生长极大值；
C. 由于树木生长是依靠细胞的增殖不断增长的，所以y(t)是关于年龄t的单调增函数；
D. y(t)是关于t的连续光滑的函数曲线； 满分：5
3
第六章 树 习题答案 一、基础知识题 6.1.假设在树中，结点 x 是结点 y 的双亲时,用(x,y)来表示树边.已知一棵树边 的集合为 {(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c ,h),(a,c)}用树形表示法出此树，并回答下列问题： (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是 g 的双亲? (4)哪些是 g 的祖 先? (5)哪些是 g 的孩子? (6)哪些是 e 的子孙? (7)哪些是 e 的兄弟?哪些是 f 的兄 弟? (8)结点 b 和 n 的层次各是多少? (9)树的深度是多少? (10)以结点 c 为根的子 树的深度是多少? (11) 树的度数是多少? a 是根结点； dmnfjkl 是叶结点； c 是 g 的双亲； c,a 是 g 的祖先； j,k 是 g 的孩子； imn 是 e 的子孙； d 是 e 的兄弟；g,h 是 f 的兄弟； b 的层次是 2；n 的层次是 5； 树的深度是 5； 以 c 为根的子树深度是 3； 树的度数是 3； 6.2 一棵度为 2 的有序树与一棵二叉树有何区别? 答： 一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于 另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区 分其左右次序，而二叉树无论其孩子数是否为 2，均需确定其左右次序，也就是 说二叉树的结点次序不是相对于另一结点而言而是确定的。 6.3 试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。 6.4 已知一棵度为 m 的树中有 n1 个度为 1 的结点，n2 个度为 2 的结点，...nm 个度为 m 的结点，问该树中有多少片叶子? 解： 设该树中的叶子数为 n0 个。该树中的总结点数为 n 个，则有： n=n0+n1+n2+…+nm (1) 又有除根结点外， 树中其他结点都有双亲结点， 且是唯一的(由树中的分支表示)， 所以，有双亲的结点数为： n-1=0*n0+1*n1+2*n2+…+m*nm (2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm 6.5 一个深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余 各层上每个结点都有 k 棵非空子树。 如果按层次顺序(同层自左至右)从 1 开始对 全部结点编号，问： (1)各层的结点数目是多少? (2)编号为 i 的结点的双亲结点(若存在)的编号是多少? (3)编号为 i 的结点的第 j 个孩子结点(若存在)的编号是多少? (4)编号为 i 的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 解： (1) 层号为 h 的结点数目为 kh-1 (2) 编号为 i 的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k 的最大整数。也就是(i-2)与 k 整除的结果.以下/表示整除。 (3) 编号为 i 的结点的第 j 个孩子结点编号是：k*(i-1)+1+j; (4) 编号为 i 的结点有右兄弟的条件是(i-1)能被 k 整除 右兄弟的编号是 i+1. 6.6 高度为 h 的完全二叉树至少有多少个结点?至多有多少个结点?
解： 高度为 h 的完全二叉树至少有 2h-1 个结点，至多有 2h-1 个结点(也就是满二 叉树)。 6.7 在具有 n 个结点的 k 叉树(k>=2)的 k 叉链表表示中，有多少个空指针? 解： n 个结点的 K 叉树共有 n*k 个指针域， 已使用的指针域为 n-1,所以空指针的 个数为：n(k-1)+1; 6.8 假设二叉树包含的结点数据为 1，3，7，12。【关于树的问题和解答,】(1)画出两棵高度最大的二叉树； (2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。 解： (1)高度最大的两棵二叉树如图： ○1 / ○3 / ○7 / ○2 / ○12 ○1 \ ○3 \ ○7 \ ○2 \ ○12 (2)两棵完全二叉树如下： ○12 / \ ○7 ○3 / \ ○1 ○2 ○12 / \ ○7 ○3 / \ ○2 ○1 (1)前序序列和中序序列相同； 6.9 试找出分别满足下面条件的所有二叉树： (2)中序序列和后序序列相同； (3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。答： (1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树 (右单支树)。 (2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树 (左单支树)。 (3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。 (4) 前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。 6.10 试采用顺序存储方法和链接存储方法分别画也 6.30 所示各二叉树的存储 结构。 解： (2)链式存储结构： 6.11 分别写出图 6.30(下图)所示各二叉树的前序、中序和后序序列。 解： (a)前序序列：12345 中序序列：24531 后序序列：54321 (b)前序序列：12345 中序序列：13542 后序序列：54321 (c)前序序列：12357864 中序序列：17583524 后序序列：78563421 (d)前序序列：124735689 中序序列：742153896 后序序列：742589631 6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或 由其后序序列和中序序列均能唯一地确定一棵二叉树， 但由前序序列和后序序列 却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为 ABDGHCEFI 和 GDHBAECIF， 请画出此二叉树。 (2)已知一棵二叉树的在序序列和后序序列分别为 BDCEAFHG 和 DECBHGFA，请 画出此二叉树。 (3)已知一棵二叉树的前序序列和后序序列分别为 AB 和 BA，请画出这两棵不 同的二叉树。 解： (1)已知二叉树的前序序列为 ABDGHCEFI 和中序序列 GDHBAECIF，则可以根据 前序序列找到根结点为 A，由此，通过中序序列可知它的两棵子树包分别含有 GDHB 和 ECIF 结点，又由前序序列可知 B 和 C 分别为两棵子树的根结点...以此 类推可画出所有结点： ○A / \ ○B ○C / ○D / \ ○G ○H ○I / \ ○E○F / (2)以同样的方法可画出该二叉树：
○A / \ ○B ○F \ ○C / \ ○D ○E ○H \ ○G \
(3)这两棵不同的二叉树为：
○A / ○B
○A \ ○B
6.13 对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉 树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树 的层次序列为 ABCDEFGHIJ,中序序列为 DBGEHJACIF，请画出此二叉树。
解： 类似于上一题的分析方法，可画出二叉树的所有结点：
○A / ○B / ○D ○E / \ G○ H○ ○I \ ○J 6.14 试画出图 6.30(下图)所示各二叉树的前序、中序和后序线索树及相应的线 索链表。 \ ○F / \ ○C \
答：略 6.15 在何种线索树中， 线索对求指定结点在相应次序下的前趋和后继并无帮助?
答： 分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时， 线索无帮助 作用。 6.16 对图 6.31 所示的森林：
(1)求各树的前序序列和后序序列； (2)求森林的前序序列和后序序列； (3)将此森林转换为相应的二叉树； (4)给出(a)所示树的以亲链表表示、孩子链表表示、双亲孩子链表表示及孩子 兄弟链表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些 易于求指定结点的后代?
解： (1) (a)的前序序列：ABCDEF 后序序列：BDEFCA (b)的前序序列：GHIJK 后序序列：IJKHG
(c)的前序序列：LMPQRNO 后序序列：QRPMNOL
(2) 此森林的前序序列： ABCDEFGHIJKLMPQRNO013456789 0234579 0123456789 *123456789 012345678 012345689023456789*123456789 0123456789 *123456789 0123456789 *123456789 0123456789 0123456789 此森林的后序序列： BDEFCAIJKHGQRPMNOL
(3) 森林转化为二叉树的过程见动画：
(4) 略 6.17 画出图 6.32(下图)所示的各二叉树所对应的森林。
解：各二叉树所对应森林如下：
(a) ○A
(b) ○A / ○B / ○C
(c) ○A
○B
○C
(d) ○A | ○B
○C
(e) ○A
○C
○F
○I
/ ○B / | \
\ ○E
| ○L
○D○H○K | |
○G ○J 6.18 高度为 h 的严格二叉树至少有多少个结点?至多有多少个结点?
答： 所谓严格二叉树是指该树中没有度数为 1 的分支结点的二叉树。 所以： 高度为 h 的的严格二叉树至少有 2h-1 个结点； 至多有 2h-1 个结点(即 满二叉树)。 6.19 在什么样的情况下，等长编码是最优的前缀码?
答: 在每个字符的使用概率相同的情况下， 也即在哈夫曼树中每片叶子的权重相 等的时候，等长编码是最优的前缀码。 6.20 下述编码哪一组不是前缀码?
{00,01,10,11},{0,1,00,11},{0,10,110,111}
答： 第二组不是前缀码。因为 0，1 分别是 00 和 11 的前缀。(前缀码是指该编码 集中的任一编码不是其他编码的前缀) 6.21 假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成， 8 个字 这 母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03
,0.21,0.10}. (1)为这 8 个字母设计哈夫曼编码。 (2)若用这三位二进制数(0…7)对这 8 个字母进行等长编码，则哈夫曼编码的 平均码长是等长编码的百分之几?它使电文总长平均压缩多少? 解： (1)哈夫曼编码 根据上图可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 (2)用三位二进行数进行的等长编码平均长度为 3，而根据哈夫曼树编码的 平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的 87%。 所以平均压缩率为 13%。 二、 算法设计题 6.22 二叉树的遍历算法可写为通用形式。例如通用的中序遍历为： void Inorder(BinTree,T,void(* visit)(DataType x)){ if (T){ Inorder(T->lchild,Visit);//遍历左子树 Visit(T->data);//通过函数指针调用它所指的函数来访问结点 Inorder(T->rchild,Visit);//遍历右子树 } } 其中 Visit 是一个函数指针，它指向形如 void f(DataType x)的函数。因此我们可以将访问结点的操作写 在函数 f 中通过调用语句 Inorder(root,f)将 f 的地址传递给 Visit,来执行遍历操作。请写一个打印结点数据的 函数，通过调用上述算法来完成书中 6.3 节的中序遍历。 解： 函数如下： void PrintNode(BinTree T) { printf("%c",T->data); } //定义二叉树链式存储结构 typedef char DataType;//定义 DataType 类型 typedef struct node{ DataType data; struct node *lchild, *rchild;//左右孩子子树 }BinTNode; //结点类型 typedef BinTNode *BinTree ;//二叉树类型 void Inorder(BinTree T,void(* Visit)(DataType x)) { if(T) { Inorder(T->lchild,Visit);//遍历左子树 Visit(T->data); //通过函数指针调用它所指的函数访问结点 Inorder(T->rchild,Visit);//遍历右子树 } } 6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。 解： (1)求结点数的递归定义为： 若为空树，结点数为 0 若只有根结点，则结点数为 1； 否则，结点数为根结点的左子树结点数+右子树结点数+1 (2)求叶子数的递归定义为： 若为空树，叶子数为 0 若只有根结点，则叶子数为 1； 否则，叶子数为根结点的左子树叶子数+右子树叶子数 typedef char DataType;//定义 DataType 类型 typedef struct node{ DataType data; struct node *lchild, *rchild;//左右孩子子树 }BinTNode; //结点类型 typedef BinTNode *BinTree ;//二叉树类型 int Node(BinTree T) {//算结点数 if(T) if (T->lchild==NULL)&&(T->rchild==NULL) return 1; else return Node(T->lchild)+Node(T->rchild)+1; else return 0; } int Leaf(BinTree T) { //算叶子数 if(T) if (T->lchild==NULL)&&(T->rchild==NULL) return 1; else return Leaf(T->lchild)+Node(T->rchild); else return 0; } 6.24 以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有 结点数最多的那一层上
的结点总数。 解： (1)根据递归定义：二叉树的高度为： 当为空树时，高度为 0； 当只有一个结点时，高度为 1； 其他情况：高度为 max(根的左子树高度，根的右子树高度)+1 int Height(BinTree T) { int hl,hr; if(T) {//非空树 if(t->lchild==NUll)&&(t->rchild==NULL)//只含一个根结点 return 1; else { hl=height(t->lchild);//根的左子树高度 hr=height(t->rchild);//根的右子树高度 if (hl>=hr) return hl+1; else return h2+1; } } else return 0; } (2)要求二叉树的宽度的话，则可根据树的高度设置一个数组 temp。temp[i]用于存放第 i 层上的结点数 (即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返 回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。 #define M 10 //假设二叉树最多的层数 int Width(BinTree T) { int static n[M];//向量存放各层结点数 int static i=1; int static max=0;//最大宽度 if(T) { if(i==1) //若是访问根结点 { n[i]++; //第 1 层加 1 i++; //到第 2 层 if(T->lchild)//若有左孩子则该层加 1 n[i]++; if(T->rchild)//若有右孩子则该层加 1 n[i]++; } else { //访问子树结点 i++; //下一层结点数 if(T->lchild) n[i]++; if(T->rchild) n[i]++; } if(max<n[i])max=n[i];//取出最大值 Width(T->lchild);//遍历左子树 i--; //往上退一层 Width(T->rchild);//遍历右子树 } return max; }//算法结束 6.25 以二叉链表为存储结构， 写一算法交换各结点的左右子树。 答： 要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进 行交换，最后一次访问是交换根结点的子树。 void ChangeBinTree(BinTree *T) { //交换子树 if(*T) { //这里以指针为参数使得交换在实参的结点上进行后序遍历 BinTree temp; ChangeBinTree(&(*T)->lchild); ChangeBinTree(&(*T)->rchild); temp=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=temp; } } 6.26 以二叉链表为存储结构， 写一个拷贝二叉树的算法 void CopyTree(BinTree root, BinTree *newroot), 其中新树的结点是动态申请的，为什么 newroot 要说明为 BinTree 型指针的指针? 解： 因为调用函数只能进行值传递,当返回类型为 void 时，就必须把实参的地址传给函数，否则函数不会 对实际参数进行任何操作,也就得不到所需结果了。所以，newroot 要说明为 BinTree 型指针 void CopyTree(BinTree root,BinTree *newroot) { //拷贝二叉树 if(root)//如果结点非空 { //按前序序列拷贝 *newroot=(BinTNode *)malloc(sizeof(BinTNode));//生成新结点 (*newroot)->data=root->data;//拷贝结点数据 CopyTree(root->lchild,&(*newroot)->lchild);//拷贝左子树 CopyTree(root->rchild,&(*newroot)->rchild);//拷贝右子树 } else //如果结点为空 *newroot=NULL;//将结点置空 } 6.27 以二叉链表为存储
第六章 树 习题及答案
一、基础知识题
6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回答下列问题：
(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?
(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?
(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少?
(11) 树的度数是多少?
6.2 一棵度为2的有序树与一棵二叉树有何区别?
6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?
6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：
(1)各层的结点数目是多少?
(2)编号为i的结点的双亲结点(若存在)的编号是多少?
(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?
(4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?
6.7 在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针?
6.8 假设二叉树包含的结点数据为1，3，7，12。
(1)画出两棵高度最大的二叉树；
(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。
6.9试找出分别满足下面条件的所有二叉树：
(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；
(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。
6.10 试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。
6.11 分别写出图6.30(下图)所示各二叉树的前序、中序和后序序列。
6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
(1)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
(1)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。
6.13 对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
6.14试画出图6.30(下图)所示各二叉树的前序、中序和后序线索树及相应的线索链表。
6.15 在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助?
6.16 对图6.31所示的森林：【关于树的问题和解答,】
(1)求各树的前序序列和后序序列；
(2)求森林的前序序列和后序序列；
(3)将此森林转换为相应的二叉树；
(4)给出(a)所示树的以亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?
6.17 画出图6.32(下图)所示的各二叉树所对就的森林。
6.18高度为h的严格二叉树至少有多少个结点?至多有多少个结点?
6.19 在什么样的情况下，等长编码是最优的前缀码?
6.20 下述编码哪一组不是前缀码?
{00,01,10,11},{0,1,00,11},{0,10,110,111}
6.21 假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.
(1)为这8个字母设计哈夫曼编码。
(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?
答案：
6.1: 图见网页动画。
答：(这是测试我们对树的基本概念的掌握情况.)
a是根结点；
mndfjkl是叶结点；
c是g的双亲；
c,a是g的祖先；
j,k是g的孩子；
imn是e的子孙；
d是e的兄弟；g,h是f的兄弟；
b的层次是2；n的层次是5；
树的深度是5；
以c为根的子树深度是3；
树的度数是3；
6.2 答：一棵度为二的有序树与一棵二叉树的区别在于，有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。
6.3 答：三个结点的树如下：只有两种形态
○A ○A
/ \ |
○ ○ ○
|
○
三个结点的二叉树如下所示：有五种形态：
(1) (2) (3) (4) (5)
○A ○A ○A ○A ○A
/ \ / / \ \
○ ○ ○ ○ ○ ○
/ \ / \
○ ○ ○ ○
6.4 解：叶子数为：n0=1+0*n1+1*n2+2*n3+...(m-1)*nm
评：我们想象这棵树是从一个根开始长起来的：当一棵树仅为根时，它的叶子数为1，每"长出"一个度为1的结点都不会增加叶子数，因此第二项为0，每长出一个度为2的结点时(无论是从哪一个结点长出)可以增加1片叶子，依此类推，每长出一个度为m的结点，可以增加(m-1)片叶子，把所有的叶子加起来就成了。
6.5 解：
(1) 设层号为l的结点数目为m=k^(l-1)
(2) 编号为i的结点的双亲结点的编号是：：|_(i+k-2)/k_|(不大于(i+k-2)/k的最大整数。也就是(i+k-2)与k整除的结果.以下/表示整除。
(3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;
(4) 编号为i的结点有右兄弟的条件是(i+1)/k==(i+2)/k (整除) 并且i!=1
右兄弟的编号是i+1.
6.6 解：高度为h的完全二叉树至少有2^(h-1)个结点，至多有2^h-1个结点(也就是满二叉树)。
6.7 解：空指针的个数为：n(k-1)+1;
6.8 解：(1)高度最大的两棵二叉树如图：
○1 ○1
/ \
○3 ○3
/ \
○7 ○7
/ \
○2 ○2
/ \
○12 ○12
(2)两棵完全二叉树如下：
○12 ○12
/ \ / \
○7 ○3 ○7 ○3
/ \ / \
○1 ○2 ○2 ○1
6.9 答：空树满足所有条件。非空树如下：
(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。
(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。
(3) 前序序列和后序序列相同的二叉树是：只有根的二叉树。
(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。
6.10
评：此题测试我们对完全二叉树的掌握情况和两种存储方法的运用。
解：
顺序存储方法：
二叉树(a):
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
_____________________________________________________________
bt |5|1|2|∮|∮|3|∮|∮|∮|∮|4|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|5|
-------------------------------------------------------------
二叉树(b):
下标 0 1 2
本文来源：http://www.gbppp.com/jy/479767/
推荐访问:问题树分析法 麦肯锡问题树