数据结构 第6章 树和二叉树 下载本文

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.已知一棵高度为K具有n个结点的二叉树,按顺序方式存储: (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.设某二叉树结点结构为: