单元7练习参考答案

单元练习 7 一判断题（下列各题，正确的请在前面的括号内打；错误的打 ） （） （1 ） 树 结 构 中 每 个 结 点 最 多 只 有 一 个 直 接 前 驱 。 （） （2） 完 全 二 叉 树 一 定 是 满 二 查 树 。 （） （3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 （） （4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。 （） （5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 （） （6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （） （7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 二填空题 （1） 在树中，一个结点所拥有的子树数称为该结点的 度 。 （2） 度为零的结点称为 叶（或叶子，或终端） 结点。 （3） 树中结点的最大层次称为树的 深度（或高度） 。 （4） 对于二叉树来说，第 i 层上至多有 2i-1 个结点。 （5） 深度为 h 的二叉树至多有 2h-1 个结点。 （6） 由一棵二叉树的前序序列和 中序 序列可唯一确定这棵二叉树。 （7） 有 20 个结点的完全二叉树，编号为 10 的结点的父结点的编号是 5 。 （8） 由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。 （9） 某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为： DABEC 。 （10） 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则 二叉树中叶结点是： E、F、H 。 （11） 已知完全二叉树的第 8 层有 8 个结点，则其叶结点数是 68 。 （12） 采用二叉链表存储的 n 个结点的二叉树，一共有 2n 个指针域。 （13） 采用二叉链表存储的 n 个结点的二叉树，共有空指针 n+1 个。 （14） 前序为 A，B，C 且后序为 C，B，A 的二叉树共有 4 种。 （18）将一棵完全二叉树按层次编号，对于任意一个编号为 i 的结点，其左孩子结点的编号为： 2*i 。 （19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。 A C B A B C A B C A C B （20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。 三选择题 （1）树最适合用来表示（ D ） 。 A有序数据元素 B无序数据元素 C元素之间无联系的数据 D元素之间有分支的层次关系 （2）前序为 A，B，C 的二叉树共有（ D ）种。 A2 B3 C4 D5 （3）根据二叉树的定义，具有 3 个结点的二叉树有（ C ）种树型。 A3 B4 C5 D6 （4）在一棵具有五层的满二叉树中，结点的总数为（ B ） A16 B31 C32 D33 （5）具有 64 个结点的完全二叉树的深度为（ C ） A5 B6 C7 D8 （6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（ A ） 。 A不发生改变 B发生改变 C不能确定 D以上都不对 （7）A，B 为一棵二叉树上的两个结点，在中序遍历时，A 在 B 前的条件是（ C ） 。 AA 在 B 右方 BA 是 B 祖先 CA 在 B 左方 DA 是 B 子孙 （8）下列 4 棵树中， （ B ）不是完全二叉树。 A B C D （9）如右图所示的二叉树，后序遍历的序列是（ D ） A A、B、C、D、E、F、G 、H 、I B A、B 、D、H、I、E、C、F、G A B F G H D C E A B F G H D C E A B E GF D C D A B E F C D A B E C D A B C D A B A D E C F G H I C H、D、I、B、E、A、F、C、G D H、I 、D、E、B、F 、G、C、A （10）对于下边的二叉树，其中序序列为 （ A ） ADBEHAFCG BDBHEAFCG CABDEHCFG DABCDEFGH B D E H C F G A （11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则前序遍历序列为（ D ） 。 A ACBED BDECAB CDEABC DCEDBA （12）具有 n（n1）个结点的完全二叉树中，结点 i（2in）的左孩子结点是（ D ） 。 A2i B2i+1 C2i-1 D不存在 （若 2ilchild count(t-lchild); count(t-rchild); 2. 求二叉树中值为最大的元素。 int maxnode(BT t, int max) if (t) if (t-datamax) max=t-data; max=maxnode(t-lchild,max); max=maxnode(t-rchild,max); 3将二叉树各结点存储到一维数组中。 void create(BT t,int a ,int i) if (t) ai=t-data; create (t-lchild, a, 2*i); create (t-rchild, a, 2*i+1); 4前序输出二叉树中各结点及其结点所在的层号。 void preorderlevel (BT t,int h) / t 的层数为 h if (t!=NULL) printf (“%d,%d”,t-data, h); preorderlevel (t-lchild, h+1); preorderlevel (t-rchild, h+1); 5. 求二叉树的宽度 思想：按层遍历二叉树，采用一个队列 q，让根结点入队列，最后出队列，若有左右子树，则 左右子树根结点入队列，如此反复，直到队列为空。 int Width(BT *T) int front=-1,rear=-1; / 队列初始化 int flag=0,count=0,p; / p 用于指向树中层的最右边的结点，标志 flag 记录层中结点数的最大值 if (T!=NULL) rear+; qrear=T; flag=1; p=rear; while (frontlchild!=NULL) rear+; qrear=T-lchild; count+; if (T-rchild!=NULL) rear+; qrear=T-rchild; count+; if (front=p) / 当前层已遍历完毕 if (flag-1) T=stacktop; top-; if (T-child!=NULL|T-rchild!=NULL) / 交换结点的左右指针 temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; if (T-lchild!=NULL) top+; stacktop=T-lchild; if (T-rchild!=NULL) top+; stacktop=T-rchild; main() int I,j,k,l; printf(“n”); root=CreateBinTree(); Inorder (root); i=CountNode (root); j=CountLeafs (root); k=Depth (root); l=Width (root); printf(“nThe Node s Number:%d”,i); printf(“nThe Leafss Number:%d”,j); printf(“nThe Depth is:%d”,k); printf(“nThe width is:%d”,l); Swap(root); Printf(“nThe swapTree is:”); Inorder(root); 7解： int h=-1,lh=1,count=0;charx=c; / 赋初值 Level (BinTree T,int h,int lh) / 求 X 结点在树只的层树 if (T=Null) h=0; else if (T-data=x) h=lh; count=h; else h+; Level