数据结构实验(3)-二叉树的应用

实验报告

二叉树运算器

1.问题的描述

二叉树是一种重要的数据结构，在实际的计算机中有许多重要的用途。本实验需要采用二叉链表的方式对二叉树进行存储，并且提供二叉树的创建、遍历、计算以及处理的功能。

2.算法的描述

(1)数据结构的描述

本实验主要使用到了BiTNode结构体，其定义如下：

typedef struct Node{

    TElemntType data;

    struct Node *lchild, *rchild;

}BiTNode, *BiTree;

其中，data是每个节点的数据，lchild是左孩子，rchild是右孩子。为

另外，在主函数中，本文主要使用到了结构体指针数组BiTree，其定义如下：

BiTree bts[BITREENUM + 1] = {nullptr};

因此，本程序可以存储BITREENUM颗二叉树。

在使用的时候，主要使用该数组的指针，传入给对应的函数进行操作。

(2)程序结构的描述

        函数原型、功能和接口的描述。

本实验主要定义如下函数，其原型为：

• void intro();
• void menu(int &func, int &num);
• status create(BiTree &bt);
• status traverseTreePreOrder(BiTree bt);
• status traverseTreeInOrder(BiTree bt);
• status traverseTreePostOrder(BiTree bt);
• status traverseTreeLevelOrder(BiTree bt);
• int nodeCount(BiTree bt);
• int leafCount(BiTree bt);
• int heightCount(BiTree bt);
• int widthCount(BiTree bt);
• status copy(BiTree &oldTree, BiTree &newTree);
• status destroy(BiTree &bt);
• status initQueue(LinkQueue &Q);
• status enQueue(LinkQueue &Q, QElemType e);
• status deQueue(LinkQueue &Q, QElemType &e);

下面将分别介绍各个函数的功能和接口

• void intro();

该函数用于展示程序一开始的页面，以及使用说明，保证程序对使用人友好

• void menu(int &func, int &num);

该函数用于获取用户想要的功能，以及想选择对应的树的编号。

• status create(BiTree &bt);

该函数用于创建二叉树，传入参数的为根节点指针，返回的参数为创建的status，如果创建成功则返回OK；

在本函数中，将接受用户的输入，分配空间并展示创建结果。

• status traverseTreePreOrder(BiTree bt);

前序遍历二叉树，输入为二叉树的根节点。

• status traverseTreeInOrder (BiTree bt);

中序遍历二叉树，输入为二叉树的根节点。

• status traverseTreePostOrder (BiTree bt);

后序遍历二叉树，输入为二叉树的根节点。

• status traverseTreeLevelOrder (BiTree bt);

层序遍历二叉树，输入为二叉树的根节点。

• int nodeCount(BiTree bt);

统计二叉树的结点个数。

• int leafCount (BiTree bt);

统计二叉树的叶子个数。

• int heightCount (BiTree bt);

统计二叉树的高度。

• int widthCount (BiTree bt);

统计二叉树的宽度。

• status copy(BiTree &oldTree, BiTree &newTree);

复制二叉树，参数分别为老树和新树。

• status destroy(BiTree &bt);

销毁多项式。

• status initQueue(LinkQueue &Q);

初始化队列

• status enQueue (LinkQueue &Q , QElemType e);

将元素e入队

• status deQueue (LinkQueue &Q , QElemType &e);

元素出队列，用引用参数e带出。

3.调试分析

        测试数据的选择，程序调试中遇到的问题及解决方法。

本实验采用题中给定的例子数据进行测试，在测试过程中遇到了各种各样的问题，问题描述与解决办法如下：

• Q:当输入的二叉树不完整的时候，如何处理？
  • A:想了一下，非常不好处理，并且题目也没有做要求，因此就不处理了，就要求用户输入必须正确就行。
• Q:当销毁二叉树之后，遍历之会产生bug，如何处理？
  • A:在定义数组的时候，先把数组全部初始化为空指针。在销毁完成后，把对饮的指针也复制为空指针，这样子就不会bug了。

4.算法的时空分析

• 时间复杂度
  • 创建：由于本实验使用的是递归创建操作，因此时间复杂度为O(N)，N为节点个数。
  • 遍历：由于本实验使用的是递归遍历操作，因此时间复杂度为O(N)，N为节点个数。其中，层序遍历由于使用了队列，因此时间是其他遍历的两倍，不过由于O()可以消除常数，故仍是O(N)。
  • 计算：由于本实验使用的是递归计算操作，因此时间复杂度为O(N)，N为节点个数。
  • 操作：由于本实验使用的是递归复制和销毁操作，因此时间复杂度为O(N)，N为节点个数。
• 空间复杂度
  • 创建：由于本实验使用的是递归创建操作，因此所需要的辅助栈空间复杂度为O(d)，d为树的深度。
  • 遍历：由于本实验使用的是递归遍历操作，因此所需要的辅助栈空间复杂度为O(d)，d为树的深度。其中，层序遍历由于使用了队列，因此所占用空间是其他遍历的两倍，不过由于O()可以消除常数，故仍是O(d)。
  • 计算：由于本实验使用的是递归计算操作，所需要的辅助栈空间复杂度为O(d)，d为树的深度。
  • 操作：由于本实验使用的是递归复制和销毁操作，所需要的辅助栈空间复杂度为O(d)，d为树的深度。

5.测试结果及分析

        列出测试数据和测试结果，给出分析和说明。

(1)创建

这里使用题目中给出的例子进行创建：

6 4 2 3 -1 -1 -1 -1 5 1 -1 -1 7 -1 -1

(2)遍历

采用题中所给的例子，获取三种遍历的结果

可以看出，三种遍历的结果都对

(3)计算

采用题中例子，计算树的各种参数

可以看出，计算结果正确

(4)复制

采用题中例子，将二叉树从1复制到2

可以看出，复制后可以正常遍历。

(5)销毁

我们选择销毁刚刚复制的2号树。

可以看出，销毁完了之后再遍历就显示是空树。

再次遍历1：

可以看出，1号树没有被销毁，说明我们的复制是有效的。

6.实验体会和收获

经过本次实验，我提高了对结构体指针的认识，在实践中实现了二叉树的各种运算，了解了类C语言和C语言的一些差别。