线索二叉树。【东北大学 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：插入方式如下：
没插入前： 插入后： A B C D F E H G I
第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 2 3 4 5 6 7 8 9 向 A B C D E F G H I 15 6 7 12 25 4 6 1 15 80、二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树（3分），并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法（5分）。
【烟台大学 2004 四、1(8分)】