数据结构期末复习题四 一、填空题 1、在二叉树的第 5 层上最多有 个结点。 2、深度为 6 的二叉树最多有 个结点。 3、一棵二叉树中共有 20 个结点，其中度为 1 的结点有 5 个，则度为 0 的结点有 个， 度为 2 的结点有 个。 4、深度为 4 的满二叉树总共有 个结点。 5、满二叉树的叶子结点都分布在 层，完全二叉树中的叶子结点分布在 层。 6、完全二叉树中编号为 9 的二叉树，其双亲的编号为 ，其左孩子的编号为 ，其右孩子的编号为 （假设其有左右孩子） 。 7、有 34 个结点的完全二叉树的深度为 。 二、应用题 1、 具有三个结点的树和二叉树各有哪几种形态？ 2、 请写出下图所示二叉树的顺序存储结构和二叉链表存储结构。 3、 请写出下图所示二叉树的层次遍历、先根、中根及后根遍历序列 4、请将下列二叉树转化为树或者森林。 5、请将下列森林转化为相应的二叉树。 A B C D E F A B C E F G D H A D C B E F H G I J K6、已知一份电报中仅有 6 种字符，A 、B 、C 、D、E 、F ，每种字符出现的频率分别为 5、3、6、10、2、4 ，请对这六种字符进行二进制编码，使得编码后电报的总长度最短。 7、. 已知二叉树的先序序列和中序序列分别为ABDEHCFI 和DBHEACIF， 1）画出该二叉树的二叉链表存储表示 2）写出该二叉树的后序序列。