数据结构习题6树(数据机构c语言版)

《数据结构习题6树(数据机构c语言版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.设二叉树bt的存储结构如下，其中bt为树根结点指针，left，right分别为结点的左、右孩子指针，dada为结点的数据域。请完成下列各题：1）画出二叉树bt的逻辑结构2）写出按先序、中序、后序遍历二叉树所得到的结点序列3）画出二叉树bt的后序线索化树1234567891000237580101jhfdbacegi00094000002.二叉树结点数值采用顺序存储结构，如图所示，1）画出二叉树表示2）写出前序遍历，中序遍历和后序遍历的结果3）写出结点值c的父结点，其左、右孩子。4）画出将此二叉树还原成森林的图eafdgcjhib3.已知一棵二叉树的中序序列为cbedahgijk

2、，后序序列为cedbhjifa，画出该二叉树的先序线索二叉树。4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），求出每个字符的Huffman编码。5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的结点。编写一个求出从根结点到p所指结点之间路径的函数。8.在二叉树

3、中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假设值为x的结点不多于1个。9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有结点数。10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩子结点数。