（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
下标 data lchild rchild 1 A B C E D F G 2 3 4 5 6 7 A B C D E F G 2 3 0 5 0 0 0 6 4 0 0 0 7 0 和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的所有祖先结点的数据域。如果根结点的 A D E 数据域值为x或不存在数据域值为x的结点，则什么也不打 C B 印。例如右图所示的二叉树，则打印结点序列为A、C、E。 F G X 【北京工业大学 1995 五、 (16分)】 F D E 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 父母 -5 3 0 2 E -3 -2 D F
【北京邮电大学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 B C D E F G H I Lc 2 4 0 0 0 8 0 0 0 Rc 3 5 6 0 7 9 0 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 语言编一过程，输出二叉树中各结点的数据及其所在的层数（已知一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，是否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点访问的次序，能否唯一确定这棵二叉树的结构？为什么？） A 【南开大学 1997 四(15分) 1998 三(12分)】 B E 43．写一非递归遍历算法，使右图树遍历输出顺序为字母顺序。 C H F K 【中国人民大学 2000 三、1 （10分）】 D J I N G M L Q 44．二叉树结点的平衡因子（bf）定义为该结点的左子树高度与 P O T S R U 右子树高度之差。设二叉树结点结构为：(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采用二叉链表结构存储，每个结点有三个字段： A data,Lchild和Rchild 。设计算法求出T的顺序存储结构A[1..n]， B C 并给出初始调用形式。要求：如某位置为空，将其置为null；如超
E G D F 出下标范围n，则报错；最后返回实际的最大下标.右图所示为n=15 I H 时一个二叉树及所对应的输出结果示例（空缺表示null）。 J 输出结果（表结构的值和最大下标）：=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，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。【上海交通大学 2000 十二(8分)】 类似本题的另外叙述有：
（1）编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都 为空或都只有一个结点，要么它们的左右子树都相似。【厦门大学 2000 四、1 （9分)】 （2）设计判断两棵二叉树是否相似的算法。【中国矿业大学 2000 四(10分)】
47．编写递归算法，依据树的双亲表示法及其根结点创建树的孩子－兄弟链表存储结构。要求写算法以前先写出这两种存储结构的类型说明。【清华大学 1995 六(20分)】
48．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。【北京轻工业学院 1998 二(14分)】 类似本题的另外叙述有： （1）设T是一棵给定的查找树,试编写一个在树中删除根结点为a的子树的程序,要求在删除的过程中释放该子树所有结点所占有的存储空间,这里假设树T中结点所占有的存储空间是通过动态存储分配取得的,其结点的形式为:（lchild,data,rchild） 【复旦大学 1999 七、 (15分)】
49．试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为： TYPE bitreptr=^nodetp;
nodetp=RECORD data:char; lchild,rchild,parent:bitreptr END;
VAR bt:bitreptr; 【同济大学 1998 四(14分)】
50．设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。【北京科技大学 1999 十、2（10分) 2000 十、2（10）】 51．试编写算法，对一棵以孩子—兄弟链表表示的树统计叶子的个数。【北京轻工业学院2000四(15分)】 52．设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。【南开大学 2000 三、1】
53．用类PASCAL语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存贮，左指针定义为lchild,右指针定义为rchild。【燕山大学 2000 七、2（8分）】
类似本题的另外叙述有：
（1）用递归方法求已知二叉树的叶结点个数。【天津大学 1999 七】
54．一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。
【上海大学 1999 三、1(18分)】
55．二叉树采用二叉链表方式存放，对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。
【西北大学 2001 六】
56．设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n ]和mid[1..n ]中，试遍写算法建立该二叉树的二叉链表。【南京航空航天大学 1999 十(10分)】
类似本题的另外叙述有：
（1）已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。【上海交通大学 1999 四(12分)】
（2）已知一棵二叉树的前序序列和中序序列分别存于两个一维数组PRE[1..n]和INO[1..n]中，请编写算法来建立该二叉树的二叉链表。【西安电子科技大学1999软件 三(8分)】
（3）已知一棵二叉树的前序序列和中序序列，可唯一地确定该二叉树。试编写据此思想构造二叉树的算法。【北方交通大学 1995 七(20分)】
57．已知二叉树的中序遍历序列为GFBEANHM，后序遍历的结点序列为GEBFHNMA。
（1）画出此二叉树的形态。（2）写出根据二叉树的中序和后序遍历的结点序列，建立它的二叉链表存储结构的递归算法。 【北京邮电大学 1992 四 (20分)】
58．假设二叉树采用链式存储结构进行存储，root^为根结点，p^为任一给定的结点，请写出求从根结点到p^之间路径的非递归算法。【西安电子科技大学2000软件 三(9分)】 59．设二叉树的结点具有如下的结构：（lchild,info,rchild），指针变量BT指向该树的根结点，试设计一个算法打印出由根结点出发到达叶结点的所有路径。
【北方交通大学 1994 八(16分)】【中国人民大学 2000 三、2（10分)】 60．设二叉树的结点结构是（Lc,data,Rc），其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据 。试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
【北京邮电大学1997八(20分)】
61．设t是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址