数据结构课后作业习题6.docx

习题61一棵度为2的树与一棵二叉树有什么区别？2为便于存储和处理一般树形结构的信息，常采用孩子兄弟表示法将其转换成二叉树(左子关系表示父子、右子关系表示兄弟)，请画出下图对应的二叉树。3二叉树的前序遍历、中序遍历和后序遍历相互之间是有关联的。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是什么？4若一棵完全二叉树有900个结点，求该二叉树中叶结点的个数。5. 假设有一个包含100万个字符的数据文件仅包含字符ae，每个字符出现的频率如下表所示：字符abcde频度（万字）64121185请构造哈夫曼树，并计算哈夫曼树的带权路径长度，求出每个字母的哈夫曼编码。使用二进制等长编码是另一种编码方案。比较两种方案的优缺点。6以二叉链表为存储结构，写出求二叉树深度的算法。7给定一棵已经构造好的二叉树，编写算法，根据给予的结点关键字进行搜索，输出该结点的所有祖先结点的关键字。8从二叉树的结点A出发，可以向上到父结点或者向下到左右孩子结点，但沿途的结点只经过一次，当到达结点B时，途经的结点数可以叫做结点A到结点B的距离。请设计程序计算二叉树结点间的最大距离。9对于有根树的两个结点p、q，最近公共祖先表示为一个结点x，满足x是p、q的祖先且x的深度尽可能大（一个结点也可以是它自己的祖先）。设计程序，寻找二叉树指定的两个结点的最近公共祖先。