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．设某二叉树结点结构为:
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或PASCALpostfirst(p),求p所对应子树的第一个后序遍历结点。【浙江大学1998 六(10分)】
37．已知二叉树T的结点在先根次序下的排列为A[1]，A[2]，?，A[n]，在中根次序下的排列为B[1]，B[中，A和B是一维数组，数组元素的值为T中相应的结点的INFO字段的值，并假定二叉树T中结点的INFO字段的试解答：
（1）证明由A[1：n]和B[1：n]能唯一的确定二叉树T的结构；
（2）给出建造二叉树T的算法，要求所建造的二叉树以LLINK/RLINK链接结构表示，且该算法是非递归算(3) 分析你所给算法的时间复杂性，该过程包括如何确定基本运算如何推导出期望复杂性和最坏复杂性。【(20分) 1998 二】
38．已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN[1：n]和POST[1：n]中，点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchil其中data为数据域，lchild与rhild分别为指向该结点左、右孩子的指针域（当孩子结点不存在时，相应指针示）。
【北京航空航天大学 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。 方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。【华南师范大学分）】
类似本题的另外叙述有：
（1）已知二叉树的链表存储结构定义如下：
TYPE bitreptr=^bitrenode;
bitrenode=RECORD data:char; lchild,rchild:bitreptr END;
编写一个递归算法，利用叶结点中空的右链指针域rchild，将所有叶结点自左至右链接成一个单链表，算法返址（链头）。 【清华大学 1997 三、 (10分)】
42．设二叉树以二叉链表示。使用类PASCAL 语言编一过程，输出二叉树中各结点的数据及其所在的层数（已知历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，是否唯一确定这棵二叉树的结构？为叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点访问的次序，能否唯一确定这棵二叉树
【南开大学 1997 四(15分) 1998 三(12分)】 A 43．写一非递归遍历算法，使右图树遍历输出顺序为字母顺序。 B E 【中国人民大学 2000 三、1 （10分）】 C H F K 44．二叉树结点的平衡因子（bf）定义为该结点的左子树高度与 D J I N G M L Q 右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild), U P O T S R lchild,rchild 是左右儿子指针；data是数据元素；bf是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子 四、 (18分)】
类似本题的另外叙述有：
(1)设二叉树结点结构为(left,data,bf,right)。定义二叉树结点T的平衡因子bf(T)=hl-hr,写一递归算法确定点的平衡因子bf,同时返回二叉树中非叶结点个数。【东南大学1996四(15分)】 45．已知二叉树T采用二叉链表结构存储，每个结点有三个字段： A data,Lchild和Rchild 。设计算法求出T的顺序存储结构A[1..n]， B C 并给出初始调用形式。要求：如某位置为空，将其置为null；如超 E G D F 出下标范围n，则报错；最后返回实际的最大下标.右图所示为n=15
I J H 时一个二叉树及所对应的输出结果示例（空缺表示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，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序似。【上海交通大学 2000 十二(8分)】 类似本题的另外叙述有：
（1）编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都 为空或都只有一个结点，要么它们的左右子树都相似。【厦门大学 2000 四、1 （9分)】 （2）设计判断两棵二叉树是否相似的算法。【中国矿业大学 2000 四(10分)】
47．编写递归算法，依据树的双亲表示法及其根结点创建树的孩子－兄弟链表存储结构。要求写算法以前先写的类型说明。【清华大学 1995 六(20分)】
48．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并【北京轻工业学院 1998 二(14分)】 类似本题的另外叙述有：
（1）设T是一棵给定的查找树,试编写一个在树中删除根结点为a的子树的程序,要求在删除的过程中释放该子的存储空间,这里假设树T中结点所占有的存储空间是通过动态存储分配取得的,其结点的形式为:（lchild,da大学 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技大学 1999 十、2（10分) 2000 十、2（10）】
51．试编写算法，对一棵以孩子—兄弟链表表示的树统计叶子的个数。【北京轻工业学院2000四(15分)】 52．设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。【南开大学 2000 三、1】
53．用类PASCAL语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存贮，左指针定义为义为rchild。【燕山大学 2000 七、2（8分）】
类似本题的另外叙述有：
（1）用递归方法求已知二叉树的叶结点个数。【天津大学 1999 七】
54．一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。
【上海大学 1999 三、1(18分)】
55．二叉树采用二叉链表方式存放，对二叉树从1开始进行连续编号，要求每个结点的编号大于其左、右孩子点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号？并给出在据域部分填写实现如上要求编号的非递归算法。
【西北大学 2001 六】
56．设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n ]和mid[1法建立该二叉树的二叉链表。【南京航空航天大学 1999 十(10分)】
类似本题的另外叙述有：
（1）已知一棵二叉树的先序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的交通大学 1999 四(12分)】
（2）已知一棵二叉树的前序序列和中序序列分别存于两个一维数组PRE[1..n]和INO[1..n]中，请编写算法二叉链表。【西安电子科技大学1999软件 三(8分)】 （3）已知一棵二叉树的前序序列和中序序列，可唯一地确定该二叉树。试编写据此思想构造二叉树的算法。【北七(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是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为x中，已知地址为y的结点右侧作为结点y的右孩子，并使插入后的二叉树仍为后序线索二叉树。【东北大学 19962．请用类C或用类PASCAL语言编写算法。请编写在中序全线索二叉树T中的结点P下插入一棵根为X的中序法。如果P左右孩子都存在，则插入失败并返回FALSE；如果P没有左孩子，则X作为P的左孩子插入；否则X入。插入完成后要求二叉树保持中序全线索并返回TRUE。【上海大学 2002 七、1 （10分）】 63．有中序穿索树Ｔ，结点形式为：（LL,LT,D,RT,RL），试编写非递归算法找到数据域为Ａ的结点，并在其左子点X：插入方式如下：
没插入前： 插入后： A C B D G F E I H 第66题图
注意：可能Ａ有左孩子或无左孩子，插入后考虑穿索的状态应作何修改。【上海大学1998六(17分)】
64．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点学 1999 四(13分)】
65．编写程序段，利用中序全线索树求其中任意结点p^的前序后继结点，结果仍用p指出。要求先描述结构和树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空。【北京(10分)】
66.已知一个二叉树如下图，修改结点（node）的连接方式，以致可以不借助辅助堆栈实现中序遍历的非递归方结点连接图并写出其实现中序遍历的非递归算法。【浙江大学2002五（10分）】
67．已知指针p指向带表头的中根次序穿线二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的线二叉树的结点结构、表头结点结构和空树结构分别为（LTAG,LLINK,INFO,RLINK,RTAG）,且规定穿线树的最左和最右下结点的RLINK域指向表头。【吉林大学 1999 二 、1 （16分）】
68. 给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个。写一算法在情况下前序遍历一中序线索树，并分析其时间复杂性。
【东南大学 1993 三(20分) 1997 三(18分) 1998 六(14分)】
69．设有二叉树BT，每个结点包括ltag、lchild、data、rchild、rtag五个字段，依次为左标志、左儿子、数志。给出将二叉树BT建成前序（即先序）线索二叉树的递归算法。
【四川联合大学2000 三】【东南大学1999六(15分)】 70．写出中序线索二叉树的线索化过程（已知二叉树T）。
【山东大学 2000 五、2 (10分)】【长沙铁道学院 1997 五、6 (10分)】 71．已知一中序线索二叉树,写一算法完成对它的中序扫描。【山东大学2001软件与理论三(8分)】
72．已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的一个叶子结点插入进的右子树的（中序序列）第一个结点（同时要修改相应的线索关系）。
【合肥工业大学 2001 五、2（8分)】
73．写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索（ltag,lc,data,rc,rtag）。其中，data存放结点的值；lc，rc为指向左、右孩子或该结点前驱或后继的指针志域，各值为：0，则lc，rc为指向左、右孩子的指针；值为1，则lc，rc为指向某前驱后继结点的指针。【北京(20分)】
74．设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值为0时,Lchild、Rchild否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。【武汉交通科1（13分）】
75．用算法说明在对称序穿线树中，如何对任意给定的结点直接找出该结点的对称序后继。
【山东大学 1999 六、３(10分）】
76．写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。【河海大学1998七(10分）】
77．设中序穿线二叉树的结点由五个域构成：info:给出结点的数据场之值。LL：当LT 为1 时，则给出该结点当LT为0时，则给出按中序遍历的前驱结点的地址。LT:标志域，为1或为0。RL：当RT为1时，则给出该结点当RT为0时，则给出按中序遍历的后继结点地址。RT: 标志域为0或为1。
请编写程序，在具有上述结点结构的中序穿线二叉树上，求某一结点p的按后序遍历次序的后继结点的地址