实验（训）项目名称

二叉树的基本操作

实验（训）地点

明远楼C110

实验（训）日期

5.19

小组成员

无

小组成员

分工情况

个人

实验（训）所用设备、材料、软件等：

Win10操作系统计算机

VC++ 2010学习版软件

实验（训）目的：

掌握栈和队列的类型定义方法；掌握栈和队列的基本操作；掌握栈和队列的应用场合，能够根据具体问题选择合适的数据结构。

实验（训）内容、步骤、结果、心得体会：

一、实验内容

（一）用递归的方法实现以下算法

1.以二叉链表表示二叉树，建立一棵二叉树；

2.输出二叉树的先序、中序和后序遍历结果；

3.统计二叉树的叶结点个数；

（二）二叉树的应用

1.赫夫曼树和赫夫曼编码的存储表示；

2.求赫夫曼编码的算法；

二、实验步骤

代码1：

#include <iostream>

using namespace std;

struct Node {

  char data;

  Node *left;

  Node *right;

};

void build(Node *&t) {

  char ch;

  cin >> ch;

  if (ch == '#') {

    t = NULL;

  } else {

    t = new Node;

    t->data = ch;

    build(t->left);

    build(t->right);

  }

}

void pre(Node *t) {

  if (t) {

    cout << t->data << " ";

    pre(t->left);

    pre(t->right);

  }

}

void mid(Node *t) {

  if (t) {

    mid(t->left);

    cout << t->data << " ";

    mid(t->right);

  }

}

void post(Node *t) {

  if (t) {

    post(t->left);

    post(t->right);

    cout << t->data << " ";

  }

}

int leaf(Node *t) {

  if (t == NULL)

    return 0;

  if (t->left == NULL && t->right == NULL)

    return 1;

  return leaf(t->left) + leaf(t->right);

}

void del(Node *&t) {

  if (t) {

    del(t->left);

    del(t->right);

    delete t;

    t = NULL;

  }

}

int main() {

  Node *root = NULL;

  cout << "按先序输入二叉树，#表示空：";

  build(root);

  cout << "先序：";

  pre(root);

  cout << endl;

  cout << "中序：";

  mid(root);

  cout << endl;

  cout << "后序：";

  post(root);

  cout << endl;

  cout << "叶子数：" << leaf(root) << endl;

  del(root);

  return 0;

}

结果：

代码2：

#include <cstring>

#include <iostream>

using namespace std;

#define N 50

struct Node {

  int w;

  int parent;

  int left;

  int right;

};

void select(Node ht[], int n, int &s1, int &s2) {

  s1 = s2 = 0;

  for (int i = 1; i <= n; i++) {

    if (ht[i].parent == 0) {

      if (s1 == 0 || ht[i].w < ht[s1].w)

        s1 = i;

    }

  }

  for (int i = 1; i <= n; i++) {

    if (ht[i].parent == 0 && i != s1) {

      if (s2 == 0 || ht[i].w < ht[s2].w)

        s2 = i;

    }

  }

  if (ht[s1].w > ht[s2].w) {

    int t = s1;

    s1 = s2;

    s2 = t;

  }

}

void create(Node *&ht, int n, int w[]) {

  int m = 2 * n - 1;

  ht = new Node[m + 1];

  for (int i = 1; i <= m; i++) {

    ht[i].w = 0;

    ht[i].parent = 0;

    ht[i].left = 0;

    ht[i].right = 0;

  }

  for (int i = 1; i <= n; i++)

    ht[i].w = w[i - 1];

  for (int i = n + 1; i <= m; i++) {

    int s1, s2;

    select(ht, i - 1, s1, s2);

    ht[s1].parent = i;

    ht[s2].parent = i;

    ht[i].left = s1;

    ht[i].right = s2;

    ht[i].w = ht[s1].w + ht[s2].w;

  }

}

void getCode(Node ht[], char **code, int n) {

  char *tmp = new char[n];

  tmp[n - 1] = '\0';

  for (int i = 1; i <= n; i++) {

    int start = n - 1;

    int c = i;

    int f = ht[i].parent;

    while (f != 0) {

      start--;

      if (ht[f].left == c)

        tmp[start] = '0';

      else

        tmp[start] = '1';

      c = f;

      f = ht[f].parent;

    }

    code[i] = new char[n - start];

    strcpy(code[i], &tmp[start]);

  }

  delete[] tmp;

}

int main() {

  int n;

  cout << "叶子个数：";

  cin >> n;

  int *w = new int[n];

  cout << "输入" << n << "个权值：" << endl;

  for (int i = 0; i < n; i++)

    cin >> w[i];

  Node *ht;

  char **code = new char *[n + 1];

  create(ht, n, w);

  getCode(ht, code, n);

  cout << "\n赫夫曼编码：" << endl;

  for (int i = 1; i <= n; i++) {

    cout << "权值" << ht[i].w << "：" << code[i] << endl;

  }

  for (int i = 1; i <= n; i++)

    delete[] code[i];

  delete[] code;

  delete[] ht;

  delete[] w;

  return 0;

}

结果：

心得体会：

本次实验让我体会到递归在二叉树操作中的简洁性，三种遍历只是访问根结点的时机不同。赫夫曼树则让我理解了如何用静态数组模拟树结构，以及贪心选择最小权值合并的思路。通过手写代码，对指针操作和内存管理也有了更深的认识。

教师评语：

成绩评定

教师签名