数据结构-实验四

实验四 二叉树的操作

（8学时）

1. 实验性质：

综合性实验

2．要求：

（1）掌握二叉树的二叉链表存储方式及二叉树的特征；

（2）验证二叉树在二叉链表存储结构下遍历操作的实现；

（3）掌握哈夫曼树的构造方法和哈夫曼编码的方法。

3.实验目的

通过该实验，可以熟练掌握二叉树的存储方式、遍历操作实现及构造赫夫曼树和哈夫曼编码的方法。

4.实验内容

（1）采用二叉链表结构建立二叉树；

（2）编程实现二叉树的先序、中序、后序和层序遍历；

（3）编程实现：求二叉树的高度和叶子结点个数；

（4）应用实现：哈夫曼编码。

5.验收/测试用例

• 构造二叉链表表示下列表达式(算法5.3)，红色十字为根节点

中序遍历 ：a-b*c/(d+e*f)+g*(h+i)

• 实现上述二叉链表的先序、中序、后序遍历，输入相应的先序序列、中序序列、后序序列。

例如： 输入

+-a##*b##/c##+d##*e##f##*g##+h##i##

输出

“先序序列： +-a*b/c+d*ef*g+hi”

• 编程实现，输出上述二叉树的高度和叶子结点个数；

• 设有正文AADBAACACCDACACAADBBCD，编程统计字符集A,B,C,D的出现,次数。设计一套Huffman编码，使得上述正文的编码最短，并且计算它的带权路径长度。

  A(9次）B（3次）C（6次）D（4次）

  二叉树结构

graph TD
    plus("+") --> minus("-")
    minus --> a("a")
    minus --> multiply("*")
    multiply --> b("b")
    multiply --> divide("/")
    divide --> c("c")
    plus --> multiply2("*")
    multiply2 --> g("g")
    multiply2 --> plus2("+")
    plus2 --> h("h")
    plus2 --> i("i")
    divide --> plus3("+")
    plus3 --> d("d")
    plus3 --> multiply3("*")
    multiply3 --> e("e")
    multiply3 --> f("f")

哈夫曼树结构

graph TD
  22(("22")) -->|0| A(("A"))
  22(("22")) --->|1| 13(("13"))

  13 -->|0| C(("C"))
  13 --->|1| 7(("7"))
  7 -->|0| B(("B"))
  7 --->|1| D(("D"))