二叉树的根结点地址为r。另外，请注意必须满足：（1）额外空间的使用只能为O(1)，(2)程序为非递归。【上海(20分)】

78．写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15分)】

79．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffma造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）用c语言树的程序. 【浙江大学 2000 七 (18分)】

序号 1 2 向 A B 15 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分)】