第6章+树和二叉树(习题)

2008信息与计算科学专业数据结构习题

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++

3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）

A．5 B．6 C．7 D．8 4. 在下述结论中，正确的是（ ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④

5. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）

A．9 B．11 C．15 D．不确定

7．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个

A．4 B．5 C．6 D．7

8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A．M1 B．M1+M2 C．M3 D．M2+M3 9．具有10个叶结点的二叉树中有（ ）个度为2的结点。 A．8 B．9 C．10 D．ll

10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）

56

2008信息与计算科学专业数据结构习题

A． 250 B． 500 C．254 D．505 E．以上答案都不对 11. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 12. 有n个叶子的哈夫曼树的结点总数为（ ）。

A．不确定 B．2n C．2n+1 D．2n-1 13. 有关二叉树下列说法正确的是（ ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 14. 一个具有1025个结点的二叉树的高h为（ ）

A．11 B．10 C．11至1025之间 D．10至1024之间 15．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点

A．2h B．2h-1 C．2h+1 D．h+1

16. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 17．在一棵高度为k的满二叉树中，结点总数为（ ） A．2k-1 B．2k C．2k-1 D．?log2k?+1 18．高度为 K的二叉树最大的结点数为（ ）。 A．2k

B．2k-1 C．2k -1

D．2k-1-1

19. 一棵树高为K的完全二叉树至少有（ ）个结点 A．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k

20．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 21．树的后根遍历序列等同于该树对应的二叉树的( ).

A. 先序序列 B. 中序序列 C. 后序序列

22．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

57

2008信息与计算科学专业数据结构习题

23．在下列存储形式中，哪一个不是树的存储形式？（ ）

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 24．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定

25. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是： A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对

26. 上题的二叉树对应的森林包括多少棵树（ ） A．l B．2 C．3 D．概念上是错误的

27．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：

A、 E B、 F C、 G D、 H

28．将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h 的（ ） A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 29．下面的说法中正确的是（ ）.

（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)(2) B．(1) C．(2) D．(1)、(2)都错 30．对于前序遍历与中序遍历结果相同的二叉树为（1）; 对于前序遍历和后序遍历结果相同的二叉树为（2）。

A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树

31．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树

32．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ） A．都不相同 B．完全相同

58

2008信息与计算科学专业数据结构习题

C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 33．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树

34. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( ) A．不确定 B. 0 C. 1 D. 2

35. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定

36. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A. X的双亲 B. X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 37. 引入二叉线索树的目的是（ ）

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 38．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n

39. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A． n-1 B．n C． n+1 D． n+2 40．由3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 41．下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）

42. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（ ）

A．A[2i](2i=

二、判断题

1. 二叉树是度为2的有序树。

59

2008信息与计算科学专业数据结构习题

2. 完全二叉树一定存在度为1的结点。 3. 对于有N个结点的二叉树，其高度为log2n。 4．深度为K的二叉树中结点总数≤2k-1。

5. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。

6. 二叉树的遍历结果不是唯一的.

7. 二叉树的遍历只是为了在应用中找到一种线性次序。

8. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。 9. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。

10. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。

11．对一棵二叉树进行层次遍历时，应借助于一个栈。 12．用树的前序遍历和中序遍历可以导出树的后序遍历。

13．采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。

14. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

15． 中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使用堆栈。

16．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 17. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。 18．任何二叉树的后序线索树进行后序遍历时都必须用栈。 19．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。 20．由一棵二叉树的前序序列和后序序列可以唯一确定它。 21．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 22. 二叉树只能用二叉链表表示。

23. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1

24. 给定一棵树，可以找到唯一的一棵二叉树与之对应。 25. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

60

2008信息与计算科学专业数据结构习题

26. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。

27. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.

28．树形结构中元素之间存在一个对多个的关系。 29．在二叉树的第i层上至少有2i-1个结点(i>=1)。 30．必须把一般树转换成二叉树后才能进行存储。 31．完全二叉树的存储结构通常采用顺序存储结构。 32．将一棵树转成二叉树，根结点没有左子树；

33．在二叉树中插入结点，则此二叉树便不再是二叉树了。 34．二叉树是一般树的特殊情形。 35．树与二叉树是两种不同的树型结构。

36. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 37．度为二的树就是二叉树。

38．深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2k-2?+1。 39.下面二叉树的定义只有一个是正确的，请在正确的地方画―√‖。

（1）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。 （2）（a）在一株二叉树的级i上，最大结点数是2i-1（i≥1）

（b）在一棵深度为k的二叉树中，最大结点数是2k-1+1（k≥1）。 （3）二叉树是结点的集合，满足如下条件： （a）它或者是空集；

（b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。 40. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。 41. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。 42. 二叉树中序线索化后，不存在空指针域。 43．霍夫曼树的结点个数不能是偶数。

44. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。 45. 哈夫曼树无左右子树之分。

46．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。

61

2008信息与计算科学专业数据结构习题

47．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 48. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。( )

三、填空题

1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。 3．在二叉树中，指针p所指结点为叶子结点的条件是______。

4．中缀式a+b*3+4*（c-d）对应的前缀式为__(1)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2)__。

5．具有256个结点的完全二叉树的深度为______。

6．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。

7．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。 8．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支 （非 终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。

9．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。

10．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______

11．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。

12．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为______。

13．高度为K的完全二叉树至少有______个叶子结点。

14．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。

15．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__(1)_；编号是i的结点所在的层次号是_(2)__（根所在的层次号规定为1层）。

16．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数

62

2008信息与计算科学专业数据结构习题

为______。

17．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。 18．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。

19．设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。 20．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。

21．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。

22．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。 23．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。

24． n（n大于1）个结点的树中，其深度最小的那棵树的深度是_(1)__，它共有_(2)__个叶子结点和_(3)__个非叶子结点；其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。

25．二叉树的先序序列和中序序列相同的条件是______。

26．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__， 右子树中有_(3)__。

27．现有按中序遍历二叉树的结果为abc，问有_ __种不同的二叉树可以得到这一遍历结果。

28．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。

29．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。 30．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 31．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。

32．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。

33．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。

34．将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。

63

2008信息与计算科学专业数据结构习题

typedef struct node

{int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q; if (bt){ADDQ(Q,bt); while(!EMPTY(Q))

{p=DELQ(Q); q=(1)___; p->rchild=__(2) _; __(3) _=q; if(p->lchild) (4)___; if(p->rchild) (5)___; }

} }

35．设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node

{int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t)

{if (t->lchild!=NULL) if __(1) _ N2++; else NL++; else if __(2)_ NR++; else _(3)_ ; if(t->lchild!=NULL) __(4)__; if (t->rchild!=NULL) __(5)__; } /*call form :if(t!=NULL) count(t);*/

36．下面是求二叉树高度的写的递归算法，试补充完整。二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。

height(p) {if (__(1)_) {if(p->lchild==null) lh=___(2)____; else lh=___(3)____; if(p->rchild==null) rh=___(4)____; else rh=___(5)____; if (lh>rh) hi=_(6)_；else hi=___(7)____; }

64

2008信息与计算科学专业数据结构习题

else hi=___(8)____; return hi; }

37 阅读下列程序说明和程序，填充程序。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：

（1）把根结点放入堆栈。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

（3）重复（2）直到堆栈为空时为止。 typedef struct node *tree; struct node{int data; tree lchild,rchild;} exchange(tree t)

{tree r,p; tree stack [500]; int tp=0; ___(1)____ while (tp>=0) {___(2)____ if(____(3)___) {r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[___(4)____]=p->lchild; stack[++tp]=p->rchild; } }}

38．设一棵二叉树的结点定义为 struct BinTreeNode{

ElemType data; BinTreeNode *leftchild,*rightchild; } 现采用输入广义表表示建立二叉树。具体规定如下： （1）树的根结点作为由子树构成的表的表名放在表的最前面；

（2）每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 （3）在整个广义表输入的结尾加上一个特殊的符号（例如―#‖）表示输入结束。

65

2008信息与计算科学专业数据结构习题

例如，对于如右图所示的二叉树，其广义表表示为A（B（D，E（G）），C（，F））。 此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母（假设以字母作为结点的值），则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女（当k=1）或右子女（当k=2）链接到其双亲结点上。若遇到的是左括号―（‖，则表明子表的开始，将k置为1；若遇到的是右括号―）‖，则表明子表结束。若遇到的是逗号―，‖，则表示以左子女为根的子树处理完毕，接着处理以右子女为根的子树，将K置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下：

MakeEmpty(s) 置空栈 Push(s,p) 元素p入栈 Pop(s) 退栈 Top(s) 存取栈顶元素的函数 下面给出了建立二叉树的算法，其中有5个语句缺失，请阅读此算法并把缺失的语句补上。

void CreatBinTree(BinTreeNode *&BT,char ls){

Stacks; MakeEmpty(s); BT=NULL; //置空二叉树 BinTreeNode *p;

int k; istream ins(ls)； //把串ls定义为输入字符串流对象ins ; char ch; ins>>ch; //从ins顺序读入一个字符 while (ch != ?#‘){ //逐个字符处理，直到遇到?#‘为止 switch(ch){

case ?(‘: __(1) _；k=1; break; case ?)‘: pop(s); break; case‘,‘ : _(2)__； break;

default :p=new BinTreeNode; _(3)_;p->leftChild=NULL;p->rightChild=NULL; if(BT==NULL) __(4) _；else if (k==1) top(s)->leftChild=p; else top(s)->rightChild=p;

}

__(5)__; } }

39．下列是先序遍历二叉树的非递归子程序，请阅读子程序填充空格，使其成为完整的算法。

void example(b) btree *b;

66

2008信息与计算科学专业数据结构习题

{ btree *stack[20], *p； int top; if (b!=null)

{ top=1; stack[top]=b; while (top>0) { p=stack[top]; top--; printf(―%d‖,p->data); if (p->rchild!=null) {__(1)_; (2)___; }

if (p->lchild!=null) __(3)_; _(4)_; }}}}

40．以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：

typedef struct node /*C语言/

{char data; struct node *lchild,*rchild;}*bitree;

void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/

while(p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p); __(1)_; } /*P入栈*/

else { p=pop(s); printf(―%c‖,p->data); __(2)__; } /*栈顶元素出栈*/ }

41．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;

if (bt==NULL) return(__(1) _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(_(2)__) ___(3)__； return(hr+1);

67

2008信息与计算科学专业数据结构习题

}

42．由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100 typedef struct Node

{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv)

{ TNODE *root; if(argc<3) exit 0;

strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }

TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=___(1)____; for(____(2)___ ; rposllink=restore(ppos+1, ___(4)____,k ); ptr->rlink=restore (___(5)____+k,rpos+1,n-1-k); return ptr; }

postorder(TNODE*ptr) { if(ptr=NULL) return;

postorder(ptr->llink); postorder(ptr->rlink); printf(―%c‖,ptr->info); }

43．下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，

68

2008信息与计算科学专业数据结构习题

分别为数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。 inordethread(thr) {p=thr->lchild; while (___(1)___) { while(__(2)___) p= _(3)__;

printf(p->data);

while(_____(4)____) { p=__(5) _；printf(p->data);} p= _(6) ;}

}

44．线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，此处也不考虑c语言的具体语法与约定，线索化前所有的标志tag都是0）。

/* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null)

{ thread_inorder(__(1)__); if(tree->lchild==___(2)___) { tree->ltag=1; tree->lchild=pre; } if((3)___ == null){ ___(4)____; __(5)_____;} pre=p; thread-inorder(___(6)____); } }

45．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(lflag,left,data,right,rflag)，其中： lflag= 0，left 指向其左孩子，lflag= 1，left 指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

prior(node,x) { if (node !=null)

if (__(1)___ ) *x=node->right; else *x=node->left;

69

2008信息与计算科学专业数据结构习题

}

next(bt, node, x) /*bt是二叉树的树根*/ {___(2)__; if (node!=bt && node!=null) if (node->rflag) ___(3)____ ；

else {do t=*x; ___(4)___;while (*x==node); *x=t; } }

四、应用题

1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

2．树和二叉树之间有什么样的区别与联系？

3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。 4．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。

5. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么?

6. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。

7．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：

1）各层的结点的数目是多少？

2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？

4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。

8．证明任一结点个数为n 的二叉树的高度至少为O(logn). 9．有n个结点并且其高度为n的二叉树的数目是多少?

10．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 11．高度为10的二叉树，其结点最多可能为多少？

12．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）

70

2008信息与计算科学专业数据结构习题

其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:

（l）画出二叉树BT的逻辑结构;

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。

58．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 59．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句。结点结构为(ltag,lc,data,rtag,rc)。

60．对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱？

61. 已知一棵二叉树的前序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。

62．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。

63．给定集合{15,3,14,2,6,9,16,17}

(1) 用□表示外部结点，用○表示内部结点，构造相应的huffman树： (2) 计算它的带权路径长度： (3) 写出它的huffman编码：

(4) huffman编码常用来译码，请用语言叙述写出其译码的过程。

64．什么是前缀编码？举例说明如何利用二叉树来设计二进制的前缀编码。 65．如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点，要求给出求解过程。

五、算法设计题

1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。

2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 3．编程求以孩子—兄弟表示法存储的森林的叶子结点数。要求描述结构。

4．假定用两个一维数组L[N]和R[N]作为有N个结点1，2,…， N的二元树的存储结

76

2008信息与计算科学专业数据结构习题

构。L[i]和R[i]分别指示结点 i的左儿子和右儿子；L[i]=0（R[i]=0）表示i的左（右）儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。

5．要求二叉树按二叉链表形式存储

（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。

完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。

6．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树 ，根由tree指向。

7．设任意非空二叉树中结点按层次顺序依次编号为1,2,…,n (n>0),其存储结构采用下图所示形式，其中i表示结点的编号, L(i)的值是i的左儿子的编号，R(i)的值是i的右儿子的编号。若L(i),R(i)的值为0，表示结点i无左儿子或右儿子。试设计算法：

（1）求出二叉树的高度。

（2）求出每个结点的层号（根结点层号为1），并填入D(i)中。

8．已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。

9. 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild 和rchild的类型为bitre。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，下面左图所示的二叉树的静态二叉链表如右图所示。

编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形

77

2008信息与计算科学专业数据结构习题

式和有关的类型描述。其中n为一个确定的整数。

A F G 下标 1 2 3 4 5 6 7 data A B C D E F G lchild 2 3 0 5 0 0 0 rchild 6 4 0 0 0 7 0 E

B D C 10．假设以双亲表示法作树的存储结构，

写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）

11．试编写算法求出二叉树的深度。二叉树的存储结构为如下说明的二叉链表: typedef struct node {ElemType data; struct node *lch, *rch; } * btre;

12．二叉树采用二叉链表存储，编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

13． 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。

14．设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。

15．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。

16．在二叉树中查找值为x的结点，试编写算法，打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度。

17．利用栈的基本操作写出先序遍历二叉树的非递归算法要求进栈的元素最少，并指出下列(最右图)二叉树中需进栈的元素。 18．设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写 出

A B D G H C E F K

I 19题图

78

2008信息与计算科学专业数据结构习题

进行非递归的前序遍历算法。

19．设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。

20．已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储： （1）编写用先根遍历树中每个结点的递归算法；

（2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。 21．用非递归方式写出二叉树中序遍历算法。

22．设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。

23．设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。

24．已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。

25．已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。

26．已知一二叉树中结点的左右孩子为left和right，p指向二叉树的某一结点。 编一个非递归函数postfirst(p),求p所对应子树的第一个后序遍历结点。

27．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。

28．假设一维数组H[1：n]存放森林F的每个结点的地址，且序列H[1]，H[2]，…，H[n]正好是森林F在先根次序下结点地址的排列；E[1:n]是一维数组，且当1<=i<=n时，E[i]是H[i]所指结点的次数（即儿子结点的个数）。试给出一个算法，该算法计算森林F的树形个数，并计算森林F的最后一个树形的根结点地址。

29．已知二叉树T采用二叉链表结构存储，每个结点有三个字段： data,Lchild和Rchild 。设计算法求出T的顺序存储结构A[1..n]， 并给出初始调用形式。要求：如某位置为空，将其置为null；如超 出下标范围n，则报错；最后返回实际的最大下标.右图所示为n=15 时一个二叉树及所对应的输出结果示例（空缺表示null）。 输出结果（表结构的值和最大下标）：=12（最大下标为12）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

A H E D B I J F G C 79

2008信息与计算科学专业数据结构习题

A B C D E F G H I J 30．设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。

31．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

32．设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。

33．试编写算法，对一棵以孩子—兄弟链表表示的树统计叶子的个数。 34．设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。

35．编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存贮，左指针定义为lchild,右指针定义为rchild。

36．一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。 37．二叉树采用二叉链表方式存放，对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。

38．假设二叉树采用链式存储结构进行存储，root 为根结点，p 为任一给定的结点，请写出求从根结点到p 之间路径的非递归算法。

39．设二叉树的结点具有如下的结构：（lchild,info,rchild），指针变量BT指向该树的根结点，试设计一个算法打印出由根结点出发到达叶结点的所有路径。

40．设二叉树的结点结构是（Lc,data,Rc），其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据。试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

41．设t是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为x的新结点插到t树中，插在地址为y的结点右侧作为结点y的右孩子，并使插入后的二叉树仍为后序线索二叉树。

42．请编写在中序全线索二叉树T中的结点P下插入一棵根为X的中序全线索二叉树的算法。如果P左右孩子都存在，则插入失败并返回FALSE；如果P没有左孩子，则X作为P的左孩子插入；否则X作为P的右孩子插入。插入完成后要求二叉树保持中序全线索

80

2008信息与计算科学专业数据结构习题

并返回TRUE。

43．有中序线索树Ｔ，结点形式为：（LL,LT,D,RT,RL），试编写非递归算法找到数据域为Ａ的结点，并在其左子树中插入已知新结点X：插入方式如下：

没插入前： 插入后：

注意：可能Ａ有左孩子或无左孩子，插入后考虑穿索的状态应作何修改。

44．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。

45．编写程序段，利用中序全线索树求其中任意结点p的前序后继结点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空。

46．设有二叉树BT，每个结点包括ltag、lchild、data、rchild、rtag五个字段，依次为左标志、左儿子、数据、右儿子、右标志。给出将二叉树BT建成前序（即先序）线索二叉树的递归算法。

47．写出中序线索二叉树的线索化过程（已知二叉树T）。 48．已知一中序线索二叉树,写一算法完成对它的中序扫描。

49．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。（1）给出构造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）编写构造huffman 编码的程序.

序号 项 权

1 A 15 2 B 6 3 C 7 4 D 12 5 E 25 6 F 4 7 G 6 8 H 1 9 I 15 81

2008信息与计算科学专业数据结构习题

并返回TRUE。

43．有中序线索树Ｔ，结点形式为：（LL,LT,D,RT,RL），试编写非递归算法找到数据域为Ａ的结点，并在其左子树中插入已知新结点X：插入方式如下：

没插入前： 插入后：

注意：可能Ａ有左孩子或无左孩子，插入后考虑穿索的状态应作何修改。

44．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。

45．编写程序段，利用中序全线索树求其中任意结点p的前序后继结点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空。

46．设有二叉树BT，每个结点包括ltag、lchild、data、rchild、rtag五个字段，依次为左标志、左儿子、数据、右儿子、右标志。给出将二叉树BT建成前序（即先序）线索二叉树的递归算法。

47．写出中序线索二叉树的线索化过程（已知二叉树T）。 48．已知一中序线索二叉树,写一算法完成对它的中序扫描。

49．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。（1）给出构造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）编写构造huffman 编码的程序.

序号 项 权

1 A 15 2 B 6 3 C 7 4 D 12 5 E 25 6 F 4 7 G 6 8 H 1 9 I 15 81

本文来源：https://www.bwwdw.com/article/0s56.html