20202307 实验八《树》实验报告

20202307 2021-2022-1 《数据结构与面向对象程序设计》实验八报告

课程：《程序设计与数据结构》
班级： 2023
姓名： 范宇涵
学号：20202307
实验教师：王志强
实验日期：2021年11月25日
必修/选修： 必修

1.实验内容

  • 参考教材PP16.1,完成链树LinkedBinaryTree的实现（getRight,contains,toString,preorder,postorder）
    用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息
    课下把代码推送到代码托管平台

  • 基于LinkedBinaryTree，实现基于（中序，先序）序列构造唯一一棵二?树的功能，比如给出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,构造出附图中的树
    用JUnit或自己编写驱动类对自己实现的功能进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息
    课下把代码推送到代码托管平台

  • 自己设计并实现一颗决策树
    提交测试代码运行截图，要全屏，包含自己的学号信息
    课下把代码推送到代码托管平台

  • 输入中缀表达式，使用树将中缀表达式转换为后缀表达式，并输出后缀表达式和计算结果（如果没有用树，正常评分。如果用到了树，即使有小的问题，也酌情给满分）
    提交测试代码运行截图，要全屏，包含自己的学号信息

2.实验过程及结果

LinkedBinaryTree

  • 链树的实现：

https://gitee.com/besti2023javads/fan-yuhan-20202307/blob/master/src/Exp8/LinkedBinaryTree.java
https://gitee.com/besti2023javads/fan-yuhan-20202307/blob/master/src/Exp8/Test.java

  • 基于中序、先序序列构造树：
    构造思路：明确不同遍历的特征，确定边界
    二叉树前序遍历：先根节点，后左子树，再右子树
    二叉树中序遍历：先左子树，后根节点，再右子树

    先序表达式的第一位是根节点，在中序表达式中找到根节点，表达式左边即为左子树，右边即为右子树。把表达式左边当成一个新的中序表达式，重复上述操作，可根据递归思想构造完成。

https://gitee.com/besti2023javads/fan-yuhan-20202307/blob/master/src/Exp8/Test2.java

  • 设计决策树：基于链树实现，将决策信息填入结点中，定义一个访问方法，设置判定条件为输入n即访问左子树，输入y即访问右子树。

https://gitee.com/besti2023javads/fan-yuhan-20202307/blob/master/src/Exp8/DecisionTree.java
https://gitee.com/besti2023javads/fan-yuhan-20202307/blob/master/src/Exp8/Test3.java

  • 中缀转后缀并计算：当遇到数字时，直接存入后缀表达式；当遇到符号时，若栈顶元素优先级高于等于这个符号，栈顶元素出栈存入表达式，符号入栈，若栈顶元素优先级低于它直接入栈。当遇到“（”时直接存入，遇到“）”匹配上一个“（”，“（）”中间所有元素全部出栈。

https://gitee.com/besti2023javads/fan-yuhan-20202307/blob/master/src/Exp8/Test4.java

3.实验过程中遇到的问题及解决过程

  • 问题1：总结一下现在学会的造树方法&tips：
  • 问题1解决方案：
  1. 递归造树时，使用数组自增a[i++]。
  2. 非递归造树时，根据需求定义多个add方法，填充空树。
  3. 树的实现具体靠链式结构还是数组结构视情况而定。有些时候通过数组下标访问会更快。比如数组下标为n的左右子树下标分别为2n及2n+1.
  4. 有些树需要借助其他数据类型构造。比如根据前序、中序、后序表达式构造一棵树，需要用到栈。
  5. 大多数情况下还是用递归造树，造了这么多树，虚空结点的树我觉得比较典型，造树代码如下：
    public Tree(String str) {
        StringTokenizer stringTokenizer = new StringTokenizer(str);
        String[] a=new String[20];
        int j=0;
        while (stringTokenizer.hasMoreTokens()) {
            a[j++]= stringTokenizer.nextToken();
        }
        //一定要把root换成create后的root
        root=CreateTree(root,a);
    }
//建立虚空结点的树
    public Node CreateTree(Node x,String[] data) {
        String temp=data[i++];
        if (temp.equals("#"))
            return null;
        else{
            x=new Node(temp);
            x.setLeft(CreateTree(x.getLeft(),data));
            x.setRight(CreateTree(x.getRight(),data));
        }
        return x;
    }
  • 问题2：前序遍历的递归和非递归算法总结
  • 问题2解决方案：
    1.递归算法
void PreOrder(const TreeNode *root)
{
    if (root == NULL)                 //若结点为空
    {
        printf("# ");
        return;
    }
    printf("%c ", root->data);        //输出根节点的值
    PreOrder(root->left);             //前序访问左子树
    PreOrder(root->right);            //前序访问右子树
}

2.非递归方法

void PreOrderLoop(TreeNode *root)
{
    std::stack s;
    TreeNode *cur, *top;
    cur = root;
    while (cur != NULL || !s.empty())
    {
        while (cur != NULL)
        {
            printf("%c ", cur->data);
            s.push(cur);
            cur = cur->left;
        }
        top = s.top();
        s.pop();
        cur = top->right;
    }
}

其他（感悟、思考等）

树的结构在算法中使用非常普遍，也非常实用。它既可以用于日常生活中的分类讨论，也可以用于机器学习，通过决策树构建预测模型，推测可能的结果，帮助人们更好的决策。关于树的奥秘和用法，我将在今后的学习中不断探索。我一定会继续努力学习的！

参考资料

  • https://viewer.mosoteach.cn/viewer?token=84b17eb7d75f8f1899513aa4ca9b0528&screenx=false&app_id=MTWEB&app_version=5.3.3&location=

相关

标签