指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

prior(node,x)

{ if (node !=null)

if ((1)_____ ) *x=node->right; else *x=node->left; }

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; } } 【南京航空航天大学 1996 十、 (8分)】

四、应用题

1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【西安电子科技大学2001软件 二、1（5分）】

2．树和二叉树之间有什么样的区别与联系？ 【西北工业大学1998一、3(4分)】【厦门大学2000五、2(14%/3分)】【燕山大学2001三、1(5分)】

3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。

【大连海事大学2001三(10分)】

4. 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？ 【中国人民大学2001二、3(4分）】 5．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。【东北大学 2000 三、1 （4分）】

6. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么? 【长沙铁道学院 1998 四、1 (6分)】

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

【南京理工大学 1998 六、 (3分)】 类似本题的另外叙述有：

（1）若二叉树中度为1的结点数为0，则该二叉树的总分支数为2（n0-1），其中n0为叶结点数。

【西北工业大学 1998 三、1（5分）】

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

1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？

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

4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。【西北工业大学1999五(10分)】【中科院自动化所1996二、1(10分)】

类似本题的另外叙述有： （1）一棵高度为h的满k叉树有如下性质：根据结点所在层次为0；第h层上的结点

都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右,顺序从1开始对全部结点进行编号，试问：

1)各层的结点个数是多少?(3分) 2)编号为i的结点的双亲结点（若存在）的编号是多少?(3分)

3)编号为i的结点的第m个孩子结点（若存在）的编号是多少？（3分）

4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？（3分) 【清华大学 1999 八 (12分)】

9．证明任一结点个数为n 的二叉树的高度至少为O(logn).【浙江大学 2000 四、 (5分)】

10．有n个结点并且其高度为n的二叉树的数目是多少? 【西安电子科技大学2000计应用一、3(5分)】

11．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 【西安电子科技大学2000计应用 一、4 （5分）】 12．高度为10的二叉树，其结点最多可能为多少？【首都经贸大学 1998 一、1 （4分）】

13．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。【西安电子科技大学2001计应用 二、3 （5分）】

14. 已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？

【中国人民大学 2001 二、5 （4分）】

15．给定K(K>=1),对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最小高度。

【大连海事大学 2001 五、 (８分)】 16．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？

【东北大学 1999 一、1 （3分）】 17．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。 【东北大学 2000 一、3 （4分）】

18． 如在内存中存放一个完全二叉树，在树上只进行下面两个操作： （1）寻找某个结点双亲 （2）寻找某个结点的儿子；

请问应该用何种结构来存储该二叉树？【东北大学 2001 一、3 （3分）】 19．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【北京工业大学 2000 二、3 （ 5分）】

20．设二叉树T中有n个顶点，其编号为1，2，3，?,n,若编号满足如下性质： （1）T中任一顶点v的编号等于左子树中最小编号减1；

（2）对T中任一顶点v,其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则（按何种顺序编号）。【山东大学 1992 一、1 （3分）】

21．若一棵树中有度数为1至m的各种结点数为n1,n2,?,nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。【北京邮电大学1993二1(6分)】【西安交通大学1996四、1(5分)】【南京航空航天大学1998五(10分)】【东南大学1999一 4（8分)】【山东大学1993一2(4分)】

【山东师范大学2001 二3(12分) 2001二2(15分)】

22．若一棵完全二叉树中叶子结点的个数为n,且最底层结点数≧2，则此二叉树的深度H=？

【北京科技大学 2001 一、6 （2分）】

23．已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？ 【山东师范大学1996五、3(2分)】

24．在一棵表示有序集S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合Sl；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈Sl,b∈S2，c∈S3是否总有a≤b≤c?为什么?【清华大学 2000 四(10分)】【武汉大学 2000 三、3】

25．试证明,在具有n(n>=1)个结点的m次树中,有n(m-1)+1个指针是空的。【复旦大学1998四(8分)】

26．对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2的结点个数为n2,请给出n0和n2之间所满足的关系式n0=f(n2).要求给出推导过程。【复旦大学 1998 五 (8分)】

27．对于任意一棵非空的二叉树T，我们用n0表示T中叶子结点的个数，用n2表示T中有两棵非空子树的结点的个数。（1）给出n0和n2所满足的关系式。（2）证明你在（1）中给出的关系式成立。

【复旦大学 1997 三 (10分)】 28．试求有n个叶结点的非满的完全二叉树的高度;【中科院计算所 2000 五、 (5分)】 29．对于具有n个叶子结点，且所有非叶子结点都有左右孩子的二叉树， (1)试问这种二叉树的结点总数是多少？（5分）

(2)试证明

?2i?1n?(li?1)=1。其中:li表示第i个叶子结点所在的层号(设根结点所在层号为

1)。(10分)

【北方交通大学 1995 三、 (15分)】 30．假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？【北京邮电大学 1996 一、1 （4分）】

31．一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标的u的结点的第i个孩子的下标以及结点下标为v的结点的父母结点的下标。【北京邮电大学 2001 四、4(5分）】

32．二叉树有n个顶点，编号为1，2，3，? ，n，设： * T中任一顶点V的编号等于左子树中最小编号减1；

* T中任一顶点V的右子树中的最小编号等于其左子树中的最大编号加1； 试描绘该二叉树。【东南大学 1999 一、2 （7分）】

33．设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。 （1）试利用归纳法证明E=I+2n, n>=0.（5分)

（2）利用（1）的结果试说明：成功查找的平均比较次数s与不成功查找的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1。 【清华大学 1998 四、 (10分)】 34．一棵非空的有向树中恰有一个顶点入度为0, 其它顶点入度为1,但一个恰有一个顶点入度为0,其它顶点入度为1的有向图却不一定是一棵有向树,请举例说明。【中科院计算所 1999 三、1 （5分）】

35．试给出下列有关并查集（mfsets）的操作序列的运算结果：

union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9), union(1,8),union(3,10),union(3,11),union(3,12),union(3,13), union(14,15),union(16,0),union(14,16),union(1,3),union(1,14).

(union是合并运算，在以前的书中命名为merge)

要求

（1）对于union(i,j),以i作为j的双亲； （5分)

（2）按i和j为根的树的高度实现union(i,j),高度大者为高度小者的双亲； （5分)

（3）按i和j为根的树的结点个数实现union(i,j),结点个数大者为结点个数小者的双亲。（5分)

【清华大学 2001 一、 (15分)】

36．证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1

【天津大学 1999 四 】

37. 对于一个堆栈，若其入栈序列为1，2，3，?，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入（固定为1，2，3??n）/输出序列对应一种二叉树形态的方法，并以入栈序列1，2，3（即n=3）为例加以说明。【浙江大学 1998年 五、1 (7分)】

38. 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。【北京大学 1998 二、2 （5分)】 类似本题的另外叙述有： （1） 二叉树的中序与后序序列能唯一地定义一棵二叉树吗? 这里所指序列中的符号代表树结点中的标识符吗？二叉树的前序与后序序列能唯一地定义一棵二叉树吗?为什么?【东南大学1993一、4（8分）】

39．试证明:同一棵二叉树的所有叶子结点，在前序序列。对称序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc,后序bca对称序bac。【山东工业大学 1997 七、 (10分)】

40. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。

【南京理工大学 1998 四、 (3分)】 41. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。【浙江大学 1996 六、 (8分)】

类似本题的另外叙述有：

(1) 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。

【长沙铁道学院1997五、2(10分)】

（2）证明：由二叉树的中序遍历序列和后序遍历序列可唯一地确定出该二叉树。

【华南理工大学 2001 一、3 （4分)】

（3）二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树,并举例说明. 【山东大学 2001软件与理论 二 、1 （4分）】

42．试证明：仅仅已知一棵二叉树的后序遍历序列和先序遍历序列，不能唯一地确定这棵二叉树。

【大连海事大学 2001 九、 (８分)】 类似本题的另外叙述有：