树结构习的题目及问题解释

《树结构习的题目及问题解释》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案第5章树【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。ABCDEFGHIJ图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】树与二叉树有什么区别？解：区别有两点

2、：（1）二叉树的一个结点至多有两个子树，树则不然；（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。解：如图5-2(a)所示，具有3个结点的树有两种不同形态。图5-2(a)如图5-2(b)所示，具有3个结点的二叉树有以下五种不同形态。图5-2(b)【例5-5】如图5-3所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。解：（1）顺序表示。精彩文档实用标准文案1234567891011abcde^^^^fg（2）该二叉树的二

3、叉链表表示如图5-4所示。abcd∧efg图5-4∧∧∧∧∧∧∧【例5-6】试找出满足下列条件的所有二叉树：（1）先序序列和中序序列相同；（2）中序序列和后序序列相同；（3）先序序列和后序序列相同。解：（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。bacdef图5-5【例5-7】如图5-5所示的二叉树，要求：（1）写出按先序、中序、

4、后序遍历得到的结点序列。（2）画出该二叉树的后序线索二叉树。解：（1）先序遍历序列：ABDEFC中序遍历序列：DEFBAC后序遍历序列：FEDBCA（2）其后序线索二叉树如图5-6所示。NULLcabdef图5-6精彩文档实用标准文案A图5-7BCDEFGHIKLMJ【例5-8】将图5-7所示的树转换为二叉树。解：第一步，加线。第二步，抹线。第三步，旋转。过程如图5-8所示。A图5-8(a)第一步　加线BCDEFGHIKLMJA图5-8(b)第二步　抹线BCDEFGHIKLMJAB图5-8(c)第三步　旋转CF

5、DKGELHMIJ精彩文档实用标准文案ABCDEFHIJ图5-9【例5-9】将如图5-9所示的二叉树转换为树。解：第一步，加线。第二步，抹线。第三步，调整。过程如图5-10所示。ABDHCFEJIBACDEFHIJ第一步　　　　　　　　　第二步　　　　　　　　　第三步BACDEFHIJ图5-10【例5-10】将如图5-11所示的森林转换成二叉树。图5-11CDEFGABHILJK解：步骤略，结果如图5-12所示。CDEFGABHILJK图5-12精彩文档实用标准文案【例5-11】假定用于通信的电文由8个字符A、

6、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。第一步：25547912308（1）设计哈夫曼树的步骤如图5-13所示。第四步：2579123081554918第五步：257912308155491827第六步：25309549187128152743第二步：257912305498第三步：25791230549815第七步

7、：2530954918712815274357第八步：2595491843307128152757100图5-13（2）设计哈夫曼编码利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：A:0011B:01C:0010D:1010精彩文档实用标准文案E:000F:100G:11H:1011习题5一、单项选择题1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（1.C）个。A.4B.5C.6

8、D.72.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（2.B）个。A.15B.16C.17D.473.假定一棵三叉树的结点数为50，则它的最小高度为（3.C）。A.3B.4C.5D.64.在一棵二叉树上第4层的结点数最多为（4.D）。A.2B.4C.6D.85.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩