本文共 2061 字，大约阅读时间需要 6 分钟。

实验二：数

课程信息

课程：程序设计与数据结构

实验基本信息

实验密级：非密级

实验内容

一、实现二叉树

参考教材p375，完成链树LinkedBinaryTree的实现（getRight, contains, toString, preorder, postorder）

• 方法实现：

  • getRight()：获取右子树
  • contains(T target)：查找某元素是否存在
  • isEmpty()：判断树是否为空
  • toString()：树的打印方法
  • preorder()：树的先序遍历方法
  • postorder()：树的后序遍历方法

• 测试与提交：

  使用JUnit或自行编写驱动类对实现的LinkedBinaryTree进行测试，提交测试代码运行截图，包含学号信息。将代码托管平台上推送至代码托管平台。

二、中序先序序列构造二叉树

基于LinkedBinaryTree，实现基于（中序、先序）序列构造唯一一棵二叉树的功能。

• 实现思路：

  根据中序和先序序列，通过递归的方式构造二叉树。先序序列的第一个元素为根结点，中序序列按根结点分割左右子树，递归处理左右子树。

• 代码实现：

  public BTNode reConstructBinaryTree(T[] pre, T[] in) {    BTNode root = new BTNode(pre[0]);    int len = pre.length;    if (len == 1) {        root.left = null;        root.right = null;        return root;    }    // 查找中序序列中的根节点    int i;    for (i = 0; i < len; i++) {        if (root.getElement().equals(in[i])) break;    }    // 创建左子树    if (i > 0) {        T[] preLeft = new Object[i];        T[] inLeft = new Object[i];        for (int j = 0; j < i; j++) {            preLeft[j] = pre[j + 1];            inLeft[j] = in[j];        }        root.left = new LinkedBinaryTree(preLeft, inLeft);    }    // 创建右子树    if (len - i - 1 > 0) {        T[] preRight = new Object[len - i - 1];        T[] inRight = new Object[len - i - 1];        for (int j = i + 1; j < len; j++) {            preRight[j - i - 1] = pre[j];            inRight[j - i - 1] = in[j];        }        root.right = new LinkedBinaryTree(preRight, inRight);    }    return root;}

• 测试截图：

  提交测试代码运行截图，包含学号信息。

三、决策树

完成PP16.6，提交测试代码运行截图，包含学号信息。

• 实现思路：
  以二叉树的形式构建一个决策树，每个结点代表一个问题，用户通过回答选择路径，最终到达结论结点。

四、表达式树

完成PP16.8，提交测试代码运行截图，包含学号信息。

• 实现思路：
  将中缀表达式转换为后缀表达式，再构建表达式树。中缀表达式中的运算符优先级高的先处理，优先处理括号，其余按顺序处理。

五、实现二叉查找树

完成PP17.1，提交测试代码运行截图，包含学号信息。

• 实现思路：
  基于二叉树实现查找最小值和最大值的方法，与第一个实验类似，书上已定义接口和部分方法，需补充缺失方法。

六、红黑树源码分析

分析红黑树和HashMap的实现，重点比较两者的结构、性能和适用场景。

实验要求

实验成果

通过本次实验，熟悉了二叉树、二叉查找树、红黑树的实现原理和应用场景，掌握了中序、先序序列构造二叉树的方法，并对决策树和表达式树的实现有了初步理解。