第6章+树和二叉树(习题)(6)

2008信息与计算科学专业数据结构习题

并返回TRUE。

43．有中序线索树Ｔ，结点形式为：（LL,LT,D,RT,RL），试编写非递归算法找到数据域为Ａ的结点，并在其左子树中插入已知新结点X：插入方式如下：

没插入前： 插入后：

注意：可能Ａ有左孩子或无左孩子，插入后考虑穿索的状态应作何修改。

44．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。

45．编写程序段，利用中序全线索树求其中任意结点p的前序后继结点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空。

46．设有二叉树BT，每个结点包括ltag、lchild、data、rchild、rtag五个字段，依次为左标志、左儿子、数据、右儿子、右标志。给出将二叉树BT建成前序（即先序）线索二叉树的递归算法。

47．写出中序线索二叉树的线索化过程（已知二叉树T）。 48．已知一中序线索二叉树,写一算法完成对它的中序扫描。

49．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。（1）给出构造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）编写构造huffman 编码的程序.

序号 项 权

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 81

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章+树和二叉树(习题)(6)在线全文阅读。