数据结构关于树的简答题详情解析

木来 木来

四、简答题

150.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果)

图片.png

151.已知一个森林的先序序列和中序序列如下,请构造出该森林。

先序序列:ABCDEFGHIJKLMNO

中序序列:CDEBFHIJGAMLONK 

图片.png

152.一棵二叉树的先序、中序、后序序列如下,其中一部分未标出,请构造出该二叉树。

(答案不唯一)

先序序列 :_ _ C D E _ G H I _ K

中序序列 :C B _ _ F A _ J K I G

后序序列 :_ E F D B _ J I H _ A 

图片.png

153.假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列DBGEHJACIF。请画出这棵二叉树。

图片.png

154已知一棵二叉树的后序遍历序列为EICBGAHDF,同时知道该二叉树的中序遍历序列为CEIFGBADH,试画出该二叉树。

图片.png

155画出同时满足下列两条件的两棵不同的二叉树。          

(1)按先根序遍历二叉树顺序为ABCDE。                   

(2)高度为5其对应的树(森林)的高度最大为4。

图片.png

156一棵非空的二叉树其先序序列和后序序列正好相反,画出这棵二叉树的形状。

图片.png

157已知一棵二叉树的中序(或中根)遍历结点排列为DGBAECHIF,后序(或后根)遍历结点排列为GDBEIHFCA,

(1)       试画出该二叉树;

(2)       试画出该二叉树的中序穿线(或线索)树;

(3)试画出该二叉树(自然)对应的森林;

图片.png

158设T是一棵二叉树,除叶子结点外,其它结点的度数皆为2,若 T中有6个叶结点,试问:

(1)       T树的最大深度Kmax=?最小可能深度Kmin=?

Kmax为6,最小可能深度为4

 

 

(2)       T树中共有多少非叶结点?

6-1=5

 

 

(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树,并计算该哈曼夫树的带权路径长度wpl。

 

哈夫曼树见下图,其带权路径长度wpl=51

图片.png

159已知一棵二叉树的前序遍历为ABECDFGHIJ,中序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树。

^^答案如下:

图片.png

160假定用于通讯的电文仅有8个字母C1,C2,…,C8组成,各个字母在电文中出现的频率分别为5,25,3,6,10,11,36,4,试为这8个字母设计哈夫曼编码树。 

图片.png

161用一维数组存放的一棵完全二叉树如下图所示:图片.png

写出后序遍历该二叉树时访问结点的顺序。

HIDJKEBLFGCA

162已知二叉树左、右子树均含有3个结点,试构造满足下面条件的所有二叉树:

(1)左、右子树的先序序列与中序序列相同;

(2)左子树的中序序列与后序序列相同,右子树的先序序列与中序序列相同。

图片.png

163如果已知森林的前序序列和后序序列分别为ABCDEFIGJH和BDCAIFJGHE,请画出该森林

图片.png

而由上图的二叉树转化为的森林如下图所示。

图片.png

164请画出下图所示的树所对应的二叉树。

图片.png

165请对下图所示二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索。

图片.png

后序线索二叉树为

图片.png

0 条评论