数据结构作业与二叉树.pdfVIP

作业要求：

独立完成，上机调试通过后上交

（提交至dlutdswork@163.com）

本次非编程作业提交截至日期：4月13日（第七周周三）上

编程作业提交截至日期：4月23日（第八周周六）前

作业3.树

非编程作业：

1.请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

2.已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是

ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。

3.将下图所示的森林转换成一棵二叉树。

4．将下图所示的二叉树还原成树或森林。

5.假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G}，字母在电文中出现的

频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字

母设计哈夫曼编码，并计算其带权路径长度WPL。

6.二叉树的后序遍历序列为：DCFEBHJKIGA，中序序列为：CDBEFAHGJIK，

请画出该二叉树。

7.二叉树的中序遍历序列为：DBHEIAFJKCG，层次遍历序列为：

ABCDEFGHIJK，请画出该二叉树。

编程作业：

二叉树采用二叉链表，试设计算法实现：

1.CreateBT(BiTreeT)：从键盘输入二叉树的先序遍历序列字符串（以”#”

代表空结点），建立其二叉链表；

如输入：AB#D##CE#F###则建立如下图所示二叉树的二叉链表

2.EBT(BiTreeT):设计递归算法实现二叉树中所有结点的左右孩

子交换；

3.CountLeaf(BiTreeT,TElemTypex,intcount):统计以值为x的结点为

根的子树中叶子结点的数目；

4.DispBiTree(BiTreeT,intlevel):按树状打印二叉树。

A

打印得到：#C

BC

###F

##E

DEA

##D

#B

F

提示：对于根为T，层次为level的子树：

①打印其下一层(level+1层)右子树；

②打印根结点；