目录
一、选择填空判断题题1题2题3题4题5题6题7题8题9
二、应用题题10 二叉树的遍历序列题11 12 二叉树的存储结构题13 14 二叉树/树、森林之间的转换题15 线索二叉树题16 17 哈夫曼编码和哈夫曼树题18 19 20树型查找——二叉排序树（二叉查找树）题21 树型查找——平衡二叉树
一、选择填空判断题
题1
1、设高度为h的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为（），最多为（）。 A、h ；2h-1 B、2h-1 ； 2h-1 C、2h+1； 2h-1-1 D、h+1；2h-1
解析：（B） 最少的情况下，除了根结点该层为1个结点以外，其余h-1层都有2个结点，得2(h-1)，即2(h-1)+1=2h-1。 最多的情况下，除了最后一层度为0，其余结点都是度为2的结点，即 2h-1个。
题2
2、一棵有124个叶结点的完全二叉树，最多有（ ）个结点。 A、247 B、248 C、249 D、250
解析：（B） 由于n0=n2+1，且N=n0+n1+n2，度为0和度为1的结点相差为1，所以完全二叉树中度为1的结点n1只可能是0或1，即当总结点数为偶数时n1=1，为奇数时n0=0。 本题中，n0=124，可得n2=123，由于是考虑最多结点数，即n1=1，所以N=124+123+1=248。
题3
3、若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有（）个结点。 A、32 B、64 C、63 D、不存在第7层
解析：（C） 考虑第1层到第6层结点都是满的情况，即第1层到第6层结点的结点数量为1+2+4+8+16+32=63个。第7层最多可有64个结点，由于二叉树有126个结点，即第7层还有126-63=63个结点。
题4
4 、一棵有n个结点的二叉树采用二次链表存储结点，其中非空指针数为（），空指针数为（）。 A、n+1；n-1 B、n；n-1 C、n-1；n+1 D、2n；2n-1
解析：（A） n个结点的数有n-1条分支，每个分支对应一个指针，所以非空指针数为n-1；另外，由于每个结点中包含2个指针域（左指针域lchild、右指针域rchild），总指针域数量减去非空指针数即为空指针数，2n-(n-1)=n+1。
题5
5、在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序是（）。 A、都不相同 B、完全相同 C、前序序列和中序序列相同，与后序序列不同 D、中序序列和后序序列相同，与前序序列不同
解析：（B） 三种遍历方式中，访问左右子树的顺序是相同的，只是访问根结点的先后顺序不同，故所有叶子结点的先后顺序是相同的。
题6
6、线索二叉树是一种（）结构。 A、逻辑 B、逻辑和存储 C、物理 D、线性
解析：（C） 二叉树是一种逻辑结构，而线索二叉树是加上线索的链表结构，是一种物理结构。
题7
7、在有n个叶子结点的哈夫曼树中，非叶子结点的总数是（）；若该哈夫曼树有215个结点，对其进行哈夫曼编码，可以得到（）个不同的码字。 A、n-1；108 B、n；107 C、2n-1；214 D、2n；215
解析：（A） 哈夫曼树中只有度为0和2的结点，由n0=n2+1，可得：非叶子结点的总数为n-1。 结点总数N=n0+n2，且n0=n2+1，N=215代入可得，n0=108。
题8
8、找出下列条件的二叉树： A、先序遍历序列与后序遍历序列相同，为（） B、中序遍历序列与后序遍历序列相同，为（） C、先序遍历序列与中序遍历序列相同，为（） D、中序遍历序列与层次遍历序列相同，为（）
解析： A、空树或只有根结点的二叉树； B、空树或任一结点至多只有左子树； C、空树或任一结点至多只有右子树； D、空树或任一结点至多只有右子树。
题9
9、（判断）哈夫曼编码树中，两个频率相同的字符具有相同的哈夫曼编码。
解析：（×） 不会有相同的哈夫曼编码，除非它们的字符相同，从而得到的哈夫曼编码也相同。
二、应用题
题10 二叉树的遍历序列
题型：通过已知树的遍历序列，求其他遍历序列
10、某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，求其先序遍历序列。
解：可知，二叉树的先、中、后序遍历序列以及层次遍历序列的遍历顺序如下：
遍历名称遍历规则先序遍历序列根 > 左 > 右中序遍历序列左 > 根 > 右后序遍历序列左 > 右 > 根层次遍历序列左 > 右
首先，通过所给的两个序列恢复二叉树，后序遍历序列为BDCAFGE，所以该序列的最后一个元素“E”为二叉树的根结点，从而可得到： 继续对左子树和右子树的中序遍历和后序遍历进行拆分，先看E的左子树，由后序序列可知左子树中A为根结点，且由后序序列可知A无左子树，右子树为BCD；同理，E的右子树中，右子树中G为根结点，但是无法判断F为其左子树还是右子树，所以看中序遍历序列中，G的左边是F，由中序遍历规则，所以F为G的左子树，同时G无右子树，如下： 同上，可得C为根结点A的右子树，C的左子树为B，右子树为D，如下既是一棵完整的二叉树： 故可得其先序遍历序列：EACBDGF。
题11 12 二叉树的存储结构
题型：根据树的存储结构，画出二叉树
11、下图是一个二叉树的顺序存储结构，其中空白表示该结点不存在，画出该二叉树，并求出该二叉树的中序序列和后序序列。
解：按完全二叉树存储，其中空白的为空，如下： 注：其中黑色标注只是为了更清楚展示该二叉树，二叉树只留蓝色部分即可。 中序序列：BADCFE；后序序列：BDFECA。
12、已知二叉树的静态二叉链表存储结构的定义以及二叉树T的静态二叉链表存储结构图如下，求 （1）二叉树T的树形结构图； （2）二叉树T的前序、中序和后序遍历序列。
#define Maxsize 20
typedef struct{
char data;
int lchild,rchild;
}node;
typedef struct{
node tree[Maxsize];
int root,nodenum;
}Sblinklist;
tree[ ]12345678910lchild0013050609dataDGBAHEICJFrchild20080701000
T.rootT.nodenum410
解：（1）首先由第二个表可知，T.root 为4，T.nodenum 为10，分别对应该二叉树的根结点为tree[4]的结点和二叉树一共有10个结点，即根结点为tree[4]=A。 然后，通过第一个表可查到结点A的左孩子lchild和右孩子rchild为3和8：
tree[ ]12345678910lchild0013050609dataDGBAHEICJFrchild20080701000
即结点B和结点C。 以结点B继续查下去，可查到结点B的左孩子lchild和右孩子rchild为1和0（0即为空）：
tree[ ]12345678910lchild0013050609dataDGBAHEICJFrchild20080701000
即结点B的左孩子为D，右孩子为空。 同样，查到结点C的左孩子为E，右孩子为F：
tree[ ]12345678910lchild0013050609dataDGBAHEICJFrchild20080701000
……，按照上面的方法依次查下去，可得以下二叉树： （2）二叉树T的前序、中序和后序遍历序列分别为： ABDGCEHIFJ、DGBAHEICJF、GDBHIEJFCA。
题13 14 二叉树/树、森林之间的转换
题型一：根据所给二叉树，将其转换为树
13、将以下这棵二叉树转换为树。
解：第一步，旋转。将该二叉树中除了根结点左右子树的所有结点向右旋转45°，如下： 第二步，连线。若某结点的左孩子有右子树，则右子树与该结点相连，A结点的左孩子B有右子树D，所以将A与D相连；C结点的左孩子E有右子树H，所以将C与H相连，如下： 第三步，断线。删除除根结点外各结点右子树的右分支与其父结点连线，如下： 即可得到二叉树转换而来的树： 题型二：根据所给森林，将其转换为二叉树
14、已知下面由三棵树组成的森林，将其转换为二叉树。
解：第一步，连线。首先将所有结点的兄弟结点相连，另外各树的根结点也相连，如下： 第二步，断线。只保留所有结点的最左边子女，而其他结点断开，如下： 断开后： 第三步，旋转。以第一棵树的根结点为轴心，顺时针旋转45°，如下：
题15 线索二叉树
题型：根据所给二叉树，画出该二叉树的线索二叉树
15、设一棵二叉树的先序、中序遍历序列分别为ABDFCEGH和BFDAGEHC，求这棵二叉树的后序线索树。
解：首先，求出该二叉树，可以得到： 第一步，求出要画的相应线索二叉树的先/中后序遍历序列。可得到其后序遍历序列是FDBGHECA。 第二步，画线索（针对二叉树中缺少左、右孩子的结点）。若该结点无左孩子，则线索指向相应线索二叉树的先/中/后序遍历序列的前驱，若无前驱则指向NULL；若该结点无右孩子，则线索指向相应线索二叉树的先/中/后序遍历序列的后继，若无后继则指向NULL。 例如，结点D无右孩子，在后序遍历序列中结点D的后继是B，所以指向B；结点F无左孩子，在后序遍历序列中结点F无前驱结点，所以指向NULL；结点H无左孩子和右孩子，在后序遍历序列中结点H的前驱是G，后驱是E，所以分别指向G和E，如下：
题16 17 哈夫曼编码和哈夫曼树
题型一：求哈夫曼树的带权路径长度
16、已知4个字符A、B、C、D的哈夫曼编码分别是1、01、000、001，下列串是由字符组成的一段文本的哈夫曼编码：1001000011011010011010011，将该串还原成编码前的文本，以字符在文本中出现的次数为权值，求出这棵树的带权路径长度。
解：由哈夫曼编码可得到如下：
1001000011011010011010011ADCBABABDABDA
所以还原成编码前的文本为ADCBABABDABDA， 可得到：字符A出现5次，B出现4次，C出现1次，D出现3次， WPL=1×5+2×4+3×(1+3)=25。 题型二：已知字符的概率，设计哈夫曼编码，并画出相应的哈夫曼树
16、若通信系统中只可能出现5种字符A、B、C、D和E，其概率分别是0.12、0.15、0.19、0.21和0.33。 （1）画出哈夫曼树； （2）设计哈夫曼编码。
解：（1）将频率扩大100倍，分别对应12、15、19、21、33， 首先选取两棵根结点权值最小的树作为左、右子树，新的二叉树的根结点权值为其权值之和，新的结点添加进去。 12+15=27，将27添加，如下图： 继续并入： 27和33并入，27+33=60： 40+60=100，100并入： （2）进行哈夫曼编码，从根结点到叶子结点，左分支为0，右分支为1，如下： 可得到：
ABCDE100101000111
题18 19 20树型查找——二叉排序树（二叉查找树）
题型一：根据所给序列，构造二叉排序树
18、输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），求： （1）按次序构造一棵二叉排序树； （2）按照二叉排序树，怎么得到一个从小到大的有序序列？ （3）画出二叉排序树中删除“66”后的树结构。
解：（1）二叉排序树的定义中，左子树、右子树和根结点的规定如下： 左子树<根结点<右子树。 首先，按照次序开始构造，17<53，根据定义17应该放在53的左子树，如下： 因为12<17，所以12放在17的左子树，如下： 接下来的66，由于66>53，所以应该放在53的右子树；又因为58<66，所以58放在66的左子树，如下： 70>66，所以应该放在66的右子树；87>70，所以应该放在70的右子树，如下： 由于25>17，所以应该放在17的右子树，如下： 56<58，放在58的左子树；60>58，放在58的右子树，如下： （2）由于中序遍历一棵二叉树时可以得到一个结点值递增的有序序列，所以有两种方法可以实现得到一个从小到大的有序序列： ①可以将二叉排序树的中序遍历序列依次压入一个栈中，然后再依次出栈； ②定义一个一维数组，从后往前依次放入中序遍历序列，然后再输出数组中的元素。 （3）在二叉排序树中，当删除某个结点元素时，应该用该树的中序遍历序列中该结点的前驱/后继结点来替代，从而才能保证经过调整的树仍然保持二叉排序树的性质。 中序遍历序列为：12，17，25，53，56，58，60，66，70，87。 替代前后的树结构如下： 题型二：根据二叉排序树，求查找成功和查找不成功的平均查找长度
19、如图所示，求出该二叉排序树查找成功和查找不成功的平均查找长（只将与关键字的比较次数计算在内）。
解：查找成功时，平均查找长度=（1+2+3+4）/6=15/6； 查找失败时，如下，方框中的 平均查找长度=（2×2+3×3+4×2）/7=21/7。
20、假定对有序表：{13，17，21，28，34，36，42，49，53，62，77，85}进行二分查找，求： （1）画出二分查找树； （2）若查找元素81，需要依次与哪些元素进行比较？ （3）假定每个元素的查找概率相等，求查找成功与查找不成功时的平均查找长度。
解：（1）按照次序构造，如下可得该二分查找树： （2）根据二叉查找树，可知需要依次与36，53，77，85进行比较。 （3）查找成功时，ASL=（1×1+2×2+3×4+4×5）/12=37/12； 查找不成功时，ASL=（3×3+4×10）/13=49/13。
题21 树型查找——平衡二叉树
题型：根据所给序列，构造平衡二叉树，且画出删除相应结点后的平衡二叉树
21、以关键字序列{16，3，7，11，9，26，18，14，15}构造一棵AVL树（平衡二叉树），构造完成后依次删除结点16，15，11。（同时需要用虚线标出需要进行平衡调整的3个结点）
解：首先，插入结点16，此时树为空，可直接插入， 然后插入结点3，由于3<16，应该放在结点16的左子树，此时无不平衡现象发生： 继续插入结点7，由于7>3，按照规则应该放在结点3的右子树上，此时不平衡【平衡二叉树可定义为一棵空树或一棵其左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1】，应进行调整，如下： 插入11，无不平衡现象发生： 插入9，此时不平衡现象： 经过调整后的二叉树： 插入26，此时不平衡现象： 经过调整后，仍然满足左子树<根结点<右子树的规则： 插入18，此时不平衡现象： 经过调整后，如下： 插入14，此时无不平衡现象，正常插入： 插入15，此时出现不平衡现象，需调整： 调整后： 若删除结点16，由于结点16是个叶子结点，可以直接删除【删除叶子结点的情况】，并不会影响平衡二叉树的性质，如下即是删除后的树形： 若删除结点15，由于结点15只有左子树而无右子树，只需将该结点删掉，子树接上即可【删除只有单个子树的结点情况】，如下： 删除后： 若删除结点11，由于结点11既有左子树也有右子树，需要将这种情况转换为第一种或者第二种情况，可以沿着左(右)子树根结点的树根一直向下到最右(左)边的结点，用该结点代替要删除的结点可，这里由于代替的是叶子结点9，转换为第一种情况，直接将其删除即可，然后原结点11用该结点9代替。【删除左右子树都有的结点】
相关链接
您阅读本篇文章共花了：
发表评论