的结点。请编写程序，判断它们是否相似。【上海交通大学 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是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为x的新结点插到t树中，已知地址为y的结点右侧作为结点y的右孩子，并使插入后的二叉树仍为后序线索二叉树。【东北大学 1996 七 (15分)】
62．请用类C或用类PASCAL语言编写算法。请编写在中序全线索二叉树T中的结点P下插入一棵根为X的中序全线索二叉树的算法。如果P左右孩子都存在，则插入失败并返回FALSE；如果P没有左孩子，则X作为P的左孩子插入；否则X作为P的右孩子插入。插入完成后要求二叉树保持中序全线索并返回TRUE。【上海大学 2002 七、1 （10分）】 63．有中序穿索树Ｔ，结点形式为：（LL,LT,D,RT,RL），试编写非递归算法找到数据域为Ａ的结点，并在其左子树中插入已知新结点X：插入方式如下：
没插入前： 插入后：
第66题图
注意：可能Ａ有左孩子或无左孩子，插入后考虑穿索的状态应作何修改。【上海大学1998
六(17分)】 64．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。【东北大学 1999 四(13分)】
65．编写程序段，利用中序全线索树求其中任意结点p^的前序后继结点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空。【北京工业大学 2000 七(10分)】
66.已知一个二叉树如下图，修改结点（node）的连接方式，以致可以不借助辅助堆栈实现中序遍历的非递归方法。画出修改后的结点连接图并写出其实现中序遍历的非递归算法。【浙江大学2002五（10分）】
67．已知指针p指向带表头的中根次序穿线二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设穿线二叉树的结点结构、表头结点结构和空树结构分别为（LTAG,LLINK,INFO,RLINK,RTAG）,且规定穿线树的最左下结点的LLINK域和最右下结点的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的右子树中的一个叶子结点插入进去，并使之成为T的右子树的（中序序列）第一个结点（同时要修改相应的线索关系）。
【合肥工业大学 2001 五、2（8分)】
73．写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag,lc,data,rc,rtag）。其中，data存放结点的值；lc，rc为指向左、右孩子或该结点前驱或后继的指针；ltag，rtag为标志域，各值为：0，则lc，rc为指向左、右孩子的指针；值为1，则lc，rc为指向某前驱后继结点的指针。【北京邮电大学 1996 八(20分)】 74．设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值为0时,Lchild、Rchild 分别为儿子指针；否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。【武汉交通科技大学 1996 四、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的按后序遍历次序的后继结点的地址q，设该中序穿线二叉树的根结点地址为r。另外，请注意必须满足：（1）额外空间的使用只能为O(1)，(2)程序为非递归。【上海交通大学 2000 十(20分)】 78．写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15分)】
79．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。（1）给出构造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）用c语言编写构造huffman 树的程序. 【浙江大学 2000 七 (18分)】 序号 向 1 A 15 2 B 6 3 C 7 4 D 12 5 E 25 6 F 4 7 G 6 8 H 1 9 I 15 80、二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树（3分），并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法（5分）。 【烟台大学 2004 四、1(8分)】
第六章 树和二叉树
一、选择题
1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】
2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】
A．ab+cde/* B．abcde/+*+ C．abcde/*++
D．abcde*/++
3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】
A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G
4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A．5 B．6 C．7 D．8 【南京理工大学 2000 一、8 （1.5分）】 5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④
6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 【南京理工大学2000 一、17（1.5分）】
7. 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2， ?，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（(5)）。供选择的答案：
（1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序
（5） A. 丰满树 B.查找树 C.平衡树 D.完全树 【上海海运学院1999二、2(5分）】
8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 【北京工商大学2001一.7(3分)】
9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个
A．4 B．5 C．6 D．7 【哈尔滨工业大学 2001 二、2 （2分）】
10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。【北方交通大学 2001 一、16 （2分）】
A．M1 B．M1+M2 C．M3 D．M2+M3 11．具有10个叶结点的二叉树中有（ ）个度为2的结点，【北京航空航天大学2000 一、5（2分)】
A．8 B．9 C．10 D．ll
12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）【西安交通大学 1996 三、2 (3分)】
A． 250 B． 500 C．254 D．505 E．以上答案都不对
13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 【福州大学 1998 一、5 (2分)】
A．不确定 B．2n C．2n+1 D．2n-1 14. 有n个叶子的哈夫曼树的结点总数为（ ）。【青岛大学 2002 二、1 （2分）】 A．不确定 B．2n C．2n+1 D．2n-1
15．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。【中科院计算所1999一、2（2分）】
A．n-1 B．?n/m?-1 C．?(n-1)/(m-1)? D． ?n/(m-1)?-1 E．?(n+1)/(m+1)?-1
16. 有关二叉树下列说法正确的是（ ）【南京理工大学 2000 一、11 （1.5分）】
A．二叉树的度为2 B．一棵二叉树的度可以小于2