发布时间 : 星期日 文章数据结构 第6章 树和二叉树更新完毕开始阅读981a91360b4c2e3f57276300
1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。【东北大学 2000 三、2 （10分）】
2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 【北京邮电大学 2001 五、3 （10分）】 3．（此题统考生做） 用PASCAL语言（或类PASCAL语言）完成下列各题： （1）设表达式a+b*(c-d)-e/f 可以表示成如下二叉树结构： t
- + / a * e f b -
c d
其中t为根结点指针，试运用后序遍历二叉树的规则，写出对表达式求值的算法：EXPVALUE
【北京科技大学 1998年 八、1 （10分）】
4．编程求以孩子—兄弟表示法存储的森林的叶子结点数。要求描述结构。【北京工业大学2000五(10分)】
5．假定用两个一维数组L[N]和R[N]作为有N个结点1，2,?， N的二元树的存储结构。L[i]和R[i]分别指示结点 i的左儿子和右儿子；L[i]=0（R[i]=0）表示i的左（右）儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。【哈尔滨工业大学 1999 七 (14分)】 类似本题的另外叙述有：
（1）假定用两个一维数组L[1..n]和R[1..n]作为有n个结点的二叉树的存储结构，L[i]和R[i]分别指示结点i的左孩子和右孩子，0表示空。写一算法，建立一维数组T[1..n]，使T中第i(i=1,2,...,n)个分量指示结点i的双亲，然后判别结点u是否为v的子孙的算法。【华南师范大学2000 六(17分)】
6．要求二叉树按二叉链表形式存储，
（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。
完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。【西北大学 2000 六 (12分)】 类似本题的另外叙述有：
（1）试写一算法判断某二叉树是否是完全二叉树。【青岛海洋大学 1999 六(15分)】 （2）编程，判断一棵二叉链表表示的二叉树是否是完全二叉树。【南京航空航天大学2001十(10分)】 （3）编写算法判断一棵二叉树BT是否是完全二叉树。【北方交通大学 1997 八 (20分)】 （4）假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树？
【哈尔滨工业大学 2000 十一 (14分)】
（5）设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为满二叉树的算法，用类pascal语言写为函数形式。【南开大学 1997 四 (16分)】
（6）试写一算法判别某二叉树是否是完全二叉树。【北京邮电大学 1994 九 (20分)】
7．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树 ，根由tree指向。 【南京理工大学 1998 七、1 （6分）】
8．设任意非空二叉树中结点按层次顺序依次编号为1,2,?,n(n>0),其存储结构采用下图所示形式，其中i表示结点的编号, L(i)的值是i的左儿子的编号，R(i)的值是i的右儿子的编号。若L(i),R(i)的值为0，表示结点i无左儿子或右儿子。试设计算法：
（1）求出二叉树的高度。 （2）求出每个结点的层号（根结点层号为1），并填入D(i)中。（可采用任何高级语言，但要注明你所采用的语言名称）。【山东大学 1992 三、 (13分)】
h
9．已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。【北京航空航天大学 1999 七、 (15分)】
10. 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild
下标 1 B D C A F G 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 和rchild的类型为bitre。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，下面左图所示的二叉树的静态二叉链表如右图所示。
编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。【合肥工业大学 2000 五、3 （8分）】
11．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）【清华大学 1994 七、 (15分)】
12．试编写算法求出二叉树的深度。二叉树的存储结构为如下说明的二叉链表: TYPE btre=↑bnode
bnode=RECORD data:datatype; lch,rch:btre END; 【北京轻工业学院1997一(15分)】【南京航空航天大学1997十(10)】【北京理工大学2000四3(4）】 13．二叉树采用二叉链表存储：
（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。
（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 【西北大学 2001 四】
14． 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学1999五(18分)】 类似本题的另外叙述有：
（1）设T是一棵n元树，Tb是T的孩子兄弟表示（二叉链表）的二叉树，试编程，由Tb计算T的高度（要求用非递归方法实现）。【南京航空航天大学 2000 九】
15．设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。【吉林大学 2000 二、3 （12分）】【中山大学 1994 六（15分）】
16．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。【武汉大学 2000 五 1】
17．设计这样的二叉树，用它可以表示父子、夫妻和兄弟三种关系，并编写一个查找任意父亲结点的所有儿子的过程。【燕山大学 2001 四、5 （8分）】
18．在二叉树中查找值为x的结点，试编写算法（用C语言）打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度（若不加分析，直接写出结果，按零分算）。
【上海交通大学 1998 五】 类似本题的另外叙述有：
（1）在二叉树中查找值为x的结点，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。注：采用非递归算法。【西安电子科技大学1996 六(10分)】
（2）设二叉树中结点的数据域的值互不相同，试设计一个算法将数据域值为x 的结点的所有祖先结点的数据域打印出来。【北方交通大学 1996 八(20分)】
（3）设二叉树根指针为t,且树中结点值各不相同，写出算法disp_f(t,x),查找树中值为t的结点，并显示出其所有祖先结点的值。【首都经贸大学 1998 三、4 （20分)】
A （4）若一棵二叉树中没有数据域值相同的结点，设计算法
B C 打印数据域值为x的所有祖先结点的数据域。如果根结点的
D E A 数据域值为x或不存在数据域值为x的结点，则什么也不打
X B C 印。例如右图所示的二叉树，则打印结点序列为A、C、E。 F G 【北京工业大学 1995 五、 (16分)】 D E F H I 19．利用栈的基本操作写出先序遍历二叉树的非递归算法 G H I 要求进栈的元素最少，并指出下列(最右图)二叉树中需进栈 18(4)题图
K 的元素。 【山东科技大学 2002 四、 (10分)】
20．设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写 19题图
出进行非递归的前序遍历算法。【西安电子科技大学1998 四(8分)】
21．若二叉树用以下存储结构表示，试给出求前序遍历的算法：
TYPE Tree:=ARRAY[1..max] OF RECORD data:char;parent:integer; END; A 下标 1 2 3 4 5 6 C 数据 D C A B B E F 父母 D -5 3 0 -3 F -2 2 E 【北京邮电大学2002 五、4 （15分）】
22．设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。 【合肥工业大学 1999 五、2 （8分）】
23．已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储： （1）编写用先根遍历树中每个结点的递归算法；
（2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学 1997 六(20分)】。
24．对于二叉树的链接实现,完成非递归的中序遍历过程。 【中山大学 1999 五、 (15分)】 类似本题的另外叙述有：
（1）写出中序遍历二叉树的非递归算法及递推算法。【大连海事大学1996 六、2 （10分)】。 （2）设计一个中序遍历算法，应用栈来存储树结点，要求结点仅能进栈和出栈一次。（本题指中序遍历二叉树）【西安电子科技大学1999计应用 四 (10分)】 （3）用非递归方式写出二叉树中序遍历算法。【山东科技大学 2002 六、2 (9分)】 25．已知二叉树用下面的顺序存储结构，写出中序遍历该二叉树的算法。 TYPE ARRAY [1..maxn] OF RECORD data:char; //存储结点值
Lc,Rc;integer; END; //存左孩子右孩子的下标，0表示无左、右孩子。 1 2 3 4 5 6 7 8 9 data A Lc Rc 2 3 B 4 5 C 0 6 D 0 0 E 0 7 F 8 9 G 0 0 H 0 0 I 0 0 如树 T=A（B（D，E,(#,G)），C（#，F（H，I）））存储如上图。【北京邮电大学 1999 九 (10分)】
26．试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学 2001 二 、2 （8分)】
27．在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。二叉链表的类型定义为：
TYPE bitreptr=^bnodetp;
bnodetp=RECORD data:char; lchild,rchild:bitreptr END;
【同济大学 2000 三、2 （12分）】 类似本题的另外叙述有：
（1）请设计算法按层次顺序遍历二叉树。【北方交通大学 2001 四、 (20分)】 （2）试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。【上海交通大学1999 三(12分)】 （3）已知一棵以二叉链表作存储结构的二叉树，编写按层次顺序（同一层自左至右）遍历二叉树的算法。
【燕山大学 1999 十、1 （8分)】
（4）设二叉树用二叉链表存储，试编写按层输出二叉树结点的算法。【北京理工大学2001九、2（8分)】 （5）写出按层次顺序打印任意二叉树T中结点的程序。二叉树采用双链结构，结点形式为（LSON，DATA，你熟识的算法语言，设T 指向二叉树的根结点。【山东大学1993 二 (12分)】
28．设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中子树相互交换。【福州大学 1998 四、2 (10分)】 类似本题的另外叙述有：
（1）设t为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位学 1996 五、 (14分)】
（2）写一个将二叉树中每个结点的左右孩子交换的算法。（统考生做）【南京航空航天大学1999九(10分)】29．设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 【东北大学 2001 三 (15分)】
30．已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。 【东北大学 1999 六、3 （12分）】
31．设二叉树采用二叉链表作为存储结构。试用类PASCAL语言实现按前序遍历顺序输出二叉树中结点的非义所用结构。设栈已经定义：inits(S)，empty（S） push（S，P），pop（S），top（S）分别为栈初始化，判栈看栈顶等操作。【北京工业大学1997二、1（10分）】
h
32．已知深度为h的二叉树以一维数组BT(1:2-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个天大学 1996】
33．设某二叉树结点结构为: