计算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分)】
（4）若一棵二叉树中没有数据域值相同的结点，设计算法
打印数据域值为x的所有祖先结点的数据域。如果根结点的
数据域值为x或不存在数据域值为x的结点，则什么也不打 印。例如右图所示的二叉树，则打印结点序列为A、C、E。 【北京工业大学 1995 五、 (16分)】
19．利用栈的基本操作写出先序遍历二叉树的非递归算法
要求进栈的元素最少，并指出下列(最右图)二叉树中需进栈 18(4)题图
的元素。 【山东科技大学 2002 四、 (10分)】
20．设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写 19题图 出进行非递归的前序遍历算法。【西安电子科技大学1998 四(8分)】 21．若二叉树用以下存储结构表示，试给出求前序遍历的算法：
TYPE Tree:=ARRAY[1..max] OF RECORD data:char;parent:integer; END;
下标 1 2 3 4 5 6 D -5 C 3 A 0 F 2 B -3 E -2 数据 父母
【北京邮电大学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，RSON）可采用任何你熟识的算法语言，设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．设某二叉树结点结构为: TYPE bitreptr=^bnodetp;
bnodetp=RECORD data:integer;
lchild,rchild:bitreptr END;
试编写算法，计算每层中结点data域数值大于50的结点个数，并输出这些结点的data域的数值和序号。
【北京工业大学 1998 九(10分)】
34．编写递归程序将二叉树逆时针旋转90度打印出来。如右图：（要求用类PASCAL语言，并描述结构）。
【北京工业大学 1999 二 、 (6分)】 35．二叉树排序方法如下：
（1）将第一个数据放在树根。
（2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树；
（3）利用中序遍历打印排序结果。
试用PASCAL或C语言编写二叉树的排序程序，并分析其算法复杂性。【浙江大学 1995 九 (15分)】
36．已知一二叉树中结点的左右孩子为left和right，p指向二叉树的某一结点。请用C或PASCAL编一个非递归函数postfirst(p),求p所对应子树的第一个后序遍历结点。【浙江大学1998 六(10分)】
37．已知二叉树T的结点在先根次序下的排列为A[1]，A[2]，?，A[n]，在中根次序下的排列为B[1]，B[2]，?，B[n]，其中，A和B是一维数组，数组元素的值为T中相应的结点的INFO字段的值，并假定二叉树T中结点的INFO字段的值互不相同，n>=0。试解答： （1）证明由A[1：n]和B[1：n]能唯一的确定二叉树T的结构；
（2）给出建造二叉树T的算法，要求所建造的二叉树以LLINK/RLINK链接结构表示，且该算法是非递归算法；
(3) 分析你所给算法的时间复杂性，该过程包括如何确定基本运算如何推导出期望复杂性和最坏复杂性。【吉林大学 1997 四 (20分) 1998 二】
38．已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN[1：n]和POST[1：n]中，（设该二叉树各结点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild,data,rchild)，其中data为数据域，lchild与rhild分别为指向该结点左、右孩子的指针域（当孩子结点不存在时，相应指针域为空，用nil表示）。
【北京航空航天大学 1998 六 (15分)】 39．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。【山东大学 2000 二 (10分)】。 类似本题的另外叙述有：
（1）已知二叉树T,试写出复制该二叉树的算法(t→T) （1）（8分)递归算法（2）（12分)非递归算法【北方交通大学 1993 七(20分)】 （2）算法题（共20分，每题10分)
（1）试写出一递归函数，判别两棵树是否相等。 （2）试写出一递归函数，复制一棵二叉树。【山东工业大学 1997 八、 (20分)】
40．假设一维数组H[1：n]存放森林F的每个结点的地址，且序列H[1]，H[2]，?，H[n]正好是森林F在先根次序下结点地址的排列；E[1:n]是一维数组，且当1<=i<=n时，E[i]是H[i]所指结点的次数（即儿子结点的个数）。试给出一个算法，该算法计算森林F的树形个数，并计算森林F的最后一个树形的根结点地址。【吉林大学 1995 五(15分)】
41．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。【华南师范大学 1999 六、2 （13分）】
类似本题的另外叙述有：
（1）已知二叉树的链表存储结构定义如下：
TYPE bitreptr=^bitrenode;
bitrenode=RECORD data:char; lchild,rchild:bitreptr END;
编写一个递归算法，利用叶结点中空的右链指针域rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址（链头）。 【清华大学 1997 三、 (10分)】
42．设二叉树以二叉链表示。使用类PASCAL 语言编一过程，
输出二叉树中各结点的数据及其所在的层数（已知一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被 访问的次序，是否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点访问的次序，能否唯 一确定这棵二叉树的结构？为什么？） 【南开大学 1997 四(15分) 1998 三(12分)】
43．写一非递归遍历算法，使右图树遍历输出顺序为字母顺序。 【中国人民大学 2000 三、1 （10分）】
44．二叉树结点的平衡因子（bf）定义为该结点的左子树高度与 右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild),
lchild,rchild 是左右儿子指针；data是数据元素；bf是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。【石油大学 1998 四、 (18分)】 类似本题的另外叙述有：
(1)设二叉树结点结构为(left,data,bf,right)。定义二叉树结点T的平衡因子bf(T)=hl-hr,写一递归算法确定二叉树tree中各结点的平衡因子bf,同时返回二叉树中非叶结点个数。【东南大学1996四(15分)】
45．已知二叉树T采用二叉链表结构存储，每个结点有三个字
段：
data,Lchild和Rchild 。设计算法求出T的顺序存储结构A[1..n]， 并给出初始调用形式。要求：如某位置为空，将其置为null；如超 出下标范围n，则报错；最后返回实际的最大下标.右图所示为n=15 时一个二叉树及所对应的输出结果示例（空缺表示null）。 输出结果（表结构的值和最大下标）：=12（最大下标为12）【合肥工业大学 2001 五、5 （8分）】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J 46．设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有