第六章树和二叉树习题数据结构Word文件下载.docx

1、在二叉树结点的先序序列，中序序列和后序序列中， A.都不相同 BC.先序和中序相同，而与后序不同 D15在完全二叉树中，若一个结点是叶结点，则它没（A 左子结点 BC 左子结点和右子结点 D16在下列情况中，可称为二叉树的是（11.14右子结点左子结点，D 2I -1则这棵二叉树最少有 （ ） h+1）。C 空 D 非空所有叶子结点的先后顺序（完全相同中序和后序相同，而与先序不同右子结点和兄弟结点结点A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E.以上答案都不对17.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是： （）

2、21 .下面几个符号串编码集合中，不是前缀编码的是（ ）。A. 0,10,110,1111 B . 11,10,001,101,0001C. 00,010,0110,1000 D . b,c,aa,ac,aba,abb,abc22.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A1.n中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组 A中的位置是（ ）A. A2i（2i=n） B . A2i+1 （2i+1lchild=NULL）&（t-rchild=NULL） ;coun tleaf（t-lchild,&coun t）;请填空使之完善。二叉树链表

3、的结点类型的定义如下:为根结点的指针*/ 初始化栈s为空栈*/ 栈s不为空*/入栈*/13以下程序是二叉链表树中序遍历的非递归算法,typedef struct node /*C 语言 /char data; struct node *lchild,*rchild;*bitree;void vst（bitree bt） /*bt bitree p; p=bt; in itstack（s）; /*while（p | !empty（s） /*if（p） push （s,p）; （1）_ ; /*Pelse p=pop（s）; printf（ “%c ,p -data）;（2） 工 栈顶元素岀栈 *

4、/14 二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。int depth（bitree bt） /*bt 为根结点的指针 */int hl,hr;if （bt=NULL） retur n（1）_ ）;hl=depth（bt-lchild）; hr=depth（bt-rchild）;if（ ）_（3 ;return（h r+1）;15 将二叉树 bt中每一个结点的左右子树互换的 C语言算法如下，其中 ADDQ（Q,bt）,DELQ（Q）,EMPTY（Q）分别为进队，岀队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。typedef struct nodeint

5、 data ; struct node *lchild, *rchild; bt node; void EXCHANGE（bt node *bt）bt node *p, *q;if （bt）ADDQ（Q,bt）;while（!EMPTY（Q）p=DELQ（Q）; q=（1）_ _； p-rchild=（2）_ _; =q；if（p-lchild） （4）_ _; if（p-rchild） （5）_ _; 四、应用题1树和二叉树之间有什么样的区别与联系？2.分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。3分别给岀下图所示二叉树的先根、中根和后根序列。4一个深度为L的满K叉树有以下性质

6、：第 L层上的结点都是叶子结点，其余各层上每个结点都有 K棵非空子树，如果按层次顺序从 1开始对全部结点进行编号，求：1）各层的结点的数目是多少？2）编号为n的结点的双亲结点（若存在）的编号是多少？3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给岀计算和推导过程。5将下列由三棵树组成的森林转换为二叉树。（只要求给岀转换结果）（l ）画岀二叉树 BT的逻辑结构（3）画出二叉树的后序线索树。五、算法设计题1 要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算

7、法。完全二叉树定义为：深度为 K,具有N个结点的二叉树的每个结点都与深度为 K的满二叉树中编号从 1至N的结点一一对应。此题以此定义为准。2设一棵二叉树的结点结构为 （LLINK,INFO,RLINK）,ROOT 为指向该二叉树根结点的指针， p和q分别为指向 该二叉树中任意两个结点的指针，试编写一算法 ANCESTOR ROOT p,q,r ）,该算法找到p和q的最近共同祖先结点r。3有一二叉链表，试编写按层次顺序遍历二叉树的算法。4已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。5.对于二叉树的链接实现，完成非递归的中序遍历过程。6试写出复制一棵二叉树的算法。

8、二叉树采用标准链接结构。7 请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为 head。二叉树按二叉链表方式存储， 链接时用叶子结点的右指针域来存放单链表指针。 分析你的算法的时、空复杂度。8已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为 x的结点，删去以它为根的子树，并释放相应的空间。9.设一棵二叉树的根结点指针为 T, C为计数变量，初值为0，试写出对此二叉树中结点计数的算法： BTLC（T，C）。10分别写出算法，实现在中序线索二叉树 T 中查找给定结点 *p 在中序序列中的前驱与后继。在先序线索二叉树 T 中，查找给定结点 *p 在

9、先序序列中的后继。在后序线索二叉树 T 中，查找给定结点 *p 在后序 序列中的前驱。第六章 树和二叉树一、单项选择题1.A2.D3A4C5B6D7E8. D9C10B11.C12A13D14B15C16B17.B18.A19C20D21B22. D23C二、 判断题（在各题后填写“/或“ X”）X V4.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。5.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。 X6中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 V7完全二叉树中，若一个结点没有左孩子，则它必是树叶。8.二叉树只能用二叉链表表示。9.

10、给定一棵树，可以找到唯一的一棵二叉树与之对应。10.用链表 （llink-rlink） 存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n-1 个空指针。11树形结构中元素之间存在一个对多个的关系。12将一棵树转成二叉树，根结点没有左子树。13度为二的树就是二叉树。14. 二叉树中序线索化后，不存在空指针域。15霍夫曼树的结点个数不能是偶数。16哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。三、 填空题1 p-lchild=null &rchlid=null2.（1）2k-1 （2）2k-13.642n n-1 n+16. .（1）2k-2+1 （第k层1个结点，总

11、结点个数是 2H-1，其双亲是 2H-1/2=2k-2 ） （2） Iog2i +17.48任何结点至多只有右子女的二叉树。9.二叉排序树10前序11 . 6912.*cou nt+, cou ntleaf（l-rchile,cou nt）13. （1） p=p-lchild / 沿左子树向下 （2） p=p-rchild14.（1）0 （2） hlhr （3）hr=hl15.（1）p-rchild （2）p-lchild （3）p-lchild（4）ADDQ（Q,p-lchild） （5）ADDQ（Q,p-rchild）1树和二叉树逻辑上都是树形结构，树和二叉树的区别有三：一是二叉树的度至多

12、为 2,树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指岀是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。二叉树不是树的特例。2.【解答】具有3个结点的树 具有3个结点的二叉树3解答：先根序列： A B C D E F G H I J;中根序列：B C D A F E H J I G;后根序列：D C B F J I H G E A 。4. （1）k h-1（h 为层数）（2） 因为该树每层上均有 KT个结点，从根开始编号为 1,则结点i的从右向左数第2个孩子的结点编号为ki。设n为结点i的子女，则关系式（i-1）k+2=n

13、1）的前一结点编号为 n-1 （其最右边子女编号是 （n-1）*k+1 ），故结点n的第i个孩子的编号是（n-1）*k+1+i 。（4）根据以上分析，结点 n有右兄弟的条件是，它不是双亲的从右数的第一子女，即 （n-1）%k!=0 ，其右兄弟编号是n+1。5.6.（其哈夫曼编码如下 A:1，B:000，C:01，D:001五、.1. 芸建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中； 右子女”的原则进行判断。ElemType x ； BiTree bt; scanf（ “ %d，&x）; 1/ if （x=0） bt=null;else if （x0）sizeof （BiNode）;

14、bt=（BiNode *）malloc（bt-data=x; bt-lchild=creat（）;rchild=creat（）; else error（ “输入错误” ） ；return （bt）;/ 结束 BiTreeint JudgeComplete（BiTree bt） / 判断二叉树是否是完全二叉树 , 如是，返回 1，否则，返回 0if （p=null） return （1）; QueueInit（Q）; QueueIn（Q,p）; /while （!QueueEmpty（Q）p=QueueOut（Q）;if （p-lchild & !tag） QueueIn（Q,p-else if

15、 （p-lchild） return 0; / else tag=1;rchild &else if （p-rchild） return 0; else tag=1; / whilereturn 1; /JudgeComplete 算法讨论 完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树， 由此推出整棵二叉树必是完全二叉树的错误结论。2. 题目分析 后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放 二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找 p 和 q 的最近共同祖先 结点r ,不失一般性，设

16、 p在q的左边。后序遍历必然先遍历到结点 p,栈中元素均为 p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点 q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点 p 和 q 的最近公共祖先。typedef structBiTree t; int tag;/tag=0 表示结点的左子女已被访问， tag=1 表示结点的右子女已被访问stack;stack s,s1;/ 栈，容量够大BiTree Ancestor（BiTree ROOT,p,q,r）/ 求二叉树上结点 p 和 q 的最近的共同祖先结点 r。top=0; bt=ROOT;while （bt!=null

17、 |top while （bt!=null & bt!=p &=q） / 结点入栈s+top.t=bt; stop.tag=0; bt=bt-lchild; / 沿左分枝向下if （bt=p） / 不失一般性，假定 p 在 q 的左侧 , 遇结点 p 时，栈中元素均为 p 的祖先结点 for （i=1;i0;i-）/ ；将栈中元素的树结点到 s1 去匹配pp=si.t;for （j=top1;jj-）if （s1j.t=pp） printf（ “p 和 q 的最近共同的祖先已找到” ）； return （pp）;while （top!=0 & stop.tag=1） top-; / 退栈if

18、（top!=0） stop.tag=1;bt=stop.t-rchild; / 沿右分枝向下遍历/ 结束 while （bt!0） return （null）; q、p 无公共祖先退栈，访问，转右子树if （top0）p=stop-; printf（p- p=p- / 6 BiTree Copy（BiTree t）/ 复制二叉树 tBiTree bt;if （t=null） bt=null;else bt=（BiTree）malloc（ sizeof （BiNode）;data=t-data;lchild=Copy（t-rchild=Copy（t- / 结束 Copy7. 题目分析 叶子结点只

19、有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针 pre ，初始为空 第一个叶子结点由指针 head 指向，遍历到叶子结点时，就将它前驱的 rchild 指针指向它，最后叶子结点的 rchild 为空。LinkedList head,pre=null; / 全局变量LinkedList InOrder（BiTree bt）/ 中序遍历二叉树 bt ，将叶子结点从左到右链成一个单链表，表头指针为 head叶子结点 处理第一个叶子结点 将叶子结点链入链表 中序遍历左子树 设置链表尾 if （bt）InOrder（bt- / 中序遍历左子树if （bt-rchild=null） / if

20、（pre=null） head=bt; pre=bt; / else pre-rchild=bt; / InOrder（bt- / pre-rchild=null; return （head）; /InOrder 时间复杂度为 O（n）, 辅助变量使用 head 和 pre, 栈空间复杂度 O（n）8. 题目分析 删除以元素值 x 为根的子树，只要能删除其左右子树，就可以释放值为 x 的根结点，因此宜采 用后序遍历。删除值为 x 结点，意味着应将其父结点的左 （ 右）子女指针置空， 用层次遍历易于找到某结点的父 结点。本题要求删除树中每一个元素值为 x 的结点的子树，因此要遍历完整棵二叉树。v

21、oid DeleteXTree（BiTree bt） / 删除以 bt 为根的子树删除 bt 的左子树、右子树释放被删结点所占的存储空间DeleteXTree（bt- DeleteXTree（bt-/ free（bt）; / DeleteXTree /void Search（B:Tree bt,ElemType x）/ 在二叉树上查找所有以 x 为元素值的结点，并删除以其为根的子树 BiTree Q;/Q 是存放二叉树结点指针的队列，容量足够大if （bt） if （bt-data=x） DeleteXTree（bt）; exit（0）;/ QueueInit（Q）; QueueIn（Q,bt

22、）;QueueEmpty（Q） p=QueueOut（Q）;lchild） /lchild-data=x） /若根结点的值为 x，则删除整棵树若左子女非空左子女结点值为DeleteXTree（p-lchild=null; / else Enqueue （Q,p-/ if （p-rchild） / if （p-rchild-data=x） / DeleteXTree（p-x, 应删除当前结点的左子树父结点的左子女置空左子女入队列若右子女非空右子女结点值为x, 应删除当前结点的右子树 父结点的右子女置空else Enqueue （Q,p-/ 右子女入队列/ while/ if （bt） /search9. int BTLC（BiTree T, int *c） 对二叉树 T 的结点计数 if （T）*c+;BT