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

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章+树和二叉树(习题)(5)在线全文阅读。