基于二叉链表的二叉树实现

Theevilspirit

发布日期: 2019-02-28 22:30:37 浏览量: 1530
评分：
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1 问题描述

采用二叉链表作为树的物理结构，通过C语言程序实现课本§3.2的基本运算。要求具有易于操作易于理解的简易菜单，可选择实现树的文件形式存储。源代码须有适当的注释，便于检查和后期的修改与理解。

2 系统设计

该线性表的实现包括一个.CPP文件。文件中定义了线性表的结构体、相关运算的函数定义及其实现、测试系统、多表管理、文件操作等函数。由于整个线性表比较简单，而且没有“#include”的需要，因此没有使用头文件。

2.1 总体系统

通过实验达到：

  • 加深对二叉树的概念、基本运算的理解；

  • 熟练掌握二叉树的逻辑结构与物理结构的关系；

  • 以二叉链表作为物理结构，熟练掌握二叉树基本运算的实现。

2.2 数据结构

数据结构的实现根据实验要求的ADT定义，定义了基于C语言结构体的ADT定义。由于之前的实验（线性表）要求给出的代码的Codebase是经典的C语言面向过程的写法，没有使用C++的类，对于此次实验按照该模式模仿。结构体如下：

  1. struct ElemType {
  2.   ValueType value;
  3.   size_t index;
  4.   bool null = true;
  5. };
  6. struct BiTreeNode {
  7.   ElemType data;
  8.   BiTreeNode* parent = NULL;
  9.   BiTreeNode* left = NULL;
  10.   BiTreeNode* right = NULL;
  11. };
  12. struct BiTree {
  13.   bool init = false;
  14.   BiTreeNode* root = NULL;
  15. };

2.3 ADT操作的设计

根据实验的要求以及二叉树ADT的定义，该二叉树ADT应包括如下的操作：

  • InitBiTree（初始化）

  • DestroyBiTree（销毁）

  • CreateBiTree（根据definition创建）

  • ClearBiTree（清空）

  • BiTreeEmpty（判断二叉树是否为空）

  • BiTreeDepth（求二叉树的深度）

  • Root（获取二叉树的根节点）

  • Value（根据index获取二叉树的节点值）

  • Assign（根据index获取某个节点并赋新值）

  • Parent（返回某节点的双亲节点）

  • LeftChild（返回某节点的左孩子）

  • RightChild（返回某节点的右孩子）

  • LeftSibling（返回某节点的左兄弟）

  • RightSibling（返回某节点的右兄弟）

  • InsertChild（将某非空无右子树的二叉树插入到某节点的左或右孩子处）

  • DeleteChild（删除某节点的左或右孩子）

  • PreOrderTraverse（先序遍历二叉树）

  • InOrderTraverse（中序遍历二叉树）

  • PostOrderTraverse（后序遍历二叉树）

  • LevelOrderTraverse（层级遍历二叉树）

为了便于错误处理，定义以下常量作为错误标识：

  1. enum Error {
  2.   INIT,
  3.   NOT_INIT,
  4.   WRONG_DEF,
  5.   NO_SUCH_NODE,
  6. };

其中，status是某个方法的返回类型，用于标志是否正确执行了相应的运算。Status的取值由上面的宏定义定义。当不为1时，认为发生了错误。然后可以根据status的值确定发生了何种错误。

ADT的运算有下面的函数定义，这些函数均返回status（如果不返回其他有用的值）、bool（判断是否为空）、size_t（求出长度或者位置）、BiTreeNode*（获取某个节点）。

  1. status InitBiTree(BiTree& T);
  2. status DestroyBiTree(BiTree& T);
  3. status CreateBiTree(BiTree& T, vector<ElemType> def);
  4. status ClearBiTree(BiTree& T);
  5. bool BiTreeEmpty(const BiTree& T);
  6. int BiTreeDepth(const BiTree& T);
  7. BiTreeNode* Root(const BiTree& T);
  8. status Value(const BiTree& T, size_t index, ElemType& value);
  9. status Assign(BiTree& T, size_t index, ElemType& value);
  10. BiTreeNode* Parent(const BiTree& T, size_t index);
  11. BiTreeNode* LeftChild(const BiTree& T, size_t index);
  12. BiTreeNode* RightChild(const BiTree& T, size_t index);
  13. BiTreeNode* LeftSibling(const BiTree& T, size_t index);
  14. BiTreeNode* RightSibling(const BiTree& T, size_t index);
  15. status InsertChild(BiTree& T, size_t index, bool LR, BiTree& c);
  16. status DeleteChild(BiTree& T, size_t index, bool LR);
  17. status PreOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
  18. status InOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
  19. status PostOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
  20. status LevelOrderTraverse(const BiTree& T);

2.4 多表系统的设计

使用C++ STL的Vector作为多二叉树的容器。使用容器可以简化相关的操作，同时具有很高的健壮性，也可以减少问题。

具体的思路为：在程序开始的时候创建一个空vector，同时设置一个索引变量，用于指示当前二叉树在vector中的位置。在运行的时候，每当用户选择新建一个线性表的时候，就将一个线性表添加到里面。

容器的定义如：

  1. vector<BiTree> trees = {};

2.5 文件存储系统设计

文件操作可以使二叉树的节点存放到硬盘上永久保存，更加贴近真实的使用场景。通过C语言标准库提供的文件读写API，可以很方便的操作文件。

通过fopen可以返回一个指针，该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式，例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作，最后使用fclose销毁该指针。

具体的实现为，写出到文件时，先将二叉树容器trees的size写出到文件，然后遍历多二叉树的容器trees，对于每一个BiTree，先将其节点数目写出，然后先序遍历该二叉树（由于需要可以复原该二叉树，该先序遍历允许空节点），将所有的节点依次写出到文件中，每次写出sizeof(ElemType)个字节。

读文件时将上述操作逆着执行一遍即可。

3 系统实现

3.1 开发环境

开发环境选用Windows 10上的VSCode作为编辑器，g++作为编译器，g++的版本为8.1.0。

3.2 ADT操作的实现

  • status InitBiTree(BiTree& T);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该操作执行的状态。该操作用于初始化相关的二叉树。首先，该操作检查二叉树是否已经被初始化了，如果已经被初始化了，则返回一个Error::INIT的错误。否则将该二叉树设为已初始化。
    • 该操作的时间复杂度为O(1)，空间复杂度为O(1)。

  • status DestroyBiTree(BiTree& T);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该操作执行的状态。该操作用于销毁相关的二叉树。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。否则将该二叉树设为未初始化，由于二叉树占用的内存需要被释放，因此会调用ClearBiTree方法。ClearBiTree方法会在后面说明。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • status CreateBiTree(BiTree& T, vector<ElemType> def);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该操作执行的状态。该操作用于初始化相关的二叉树。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。否则根据def来创建该二叉树。创建二叉树的方法为：def是一个ElemType的线性表，其中的每一个元素代表二叉树的一个节点。节点允许是空值，通过结构体中的null来指定。创建时，递归调用Create函数。Create函数根据当前指向ElemType线性表中元素位置的指针，进行如下操作：若该元素对应的是空节点，则直接返回，将指针后移一位；若不是空节点，将指针后移一位，并递归调用Create分别创建左右子树。直到指针指向列表尾停止。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • status ClearBiTree(BiTree& T);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该操作执行的状态。该操作用于清空相关的二叉树。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。否则清空该二叉树。清空二叉树的方法是：后序遍历该二叉树，将Visit函数指定为销毁相应的节点。由于后序遍历是按照左、右、根的顺序，该二叉树可以被正确销毁。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • bool BiTreeEmpty(const BiTree& T);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该二叉树是否为空。该操作用于判断相关的二叉树是否为空。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。判断二叉树是否为空的方法是：判断该二叉树的根节点是否为空节点。
    • 该操作的时间复杂度为O(1)，空间复杂度为O(1)。

  • int BiTreeDepth(const BiTree& T);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该二叉树的深度。该操作用于求取相关的二叉树的深度。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。求取二叉树的深度的方法是：递归执行Depth函数。该函数的作用是求取二叉树的深度。当该函数作用的子二叉树是叶子节点时，返回1，否则递归的调用Depth函数求取左右子树的深度，并取最大值。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • BiTreeNode* Root(const BiTree& T);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为参数，返回该操作执行的结果。该操作用于获取二叉树的根节点。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。获取二叉树根节点的方法是直接返回BiTree::root域。对于空的二叉树，返回一个NULL指针。
    • 该操作的时间复杂度为O(1)，空间复杂度为O(1)。

  • status Value(const BiTree& T, size_t index, ElemType& value);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、要获取Value的节点index为第二个参数、内容将要存放的位置为第三个引用参数，返回该操作执行的状态。该操作用于获取二叉树某个节点的值（ElemType）。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。获取二叉树某个节点值的方法是：遍历该二叉树，依次判断各个节点的index是否和参数提供的相等，如果相等则将value引用赋值为该节点。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • status Assign(BiTree& T, size_t index, ElemType& value);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、被赋值的节点index为第二个参数、要赋的值为第三个引用参数，返回该操作执行的状态。该操作用于为二叉树某个节点赋值。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。为二叉树某个节点赋值的方法是：遍历该二叉树，依次判断各个节点的index是否和参数提供的相等，如果相等则将value赋值给该节点。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。
  1. BiTreeNode* Parent(const BiTree& T, size_t index);
  2. BiTreeNode* LeftChild(const BiTree& T, size_t index);
  3. BiTreeNode* RightChild(const BiTree& T, size_t index);
  4. BiTreeNode* LeftSibling(const BiTree& T, size_t index);
  5. BiTreeNode* RightSibling(const BiTree& T, size_t index);

这五个操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、要获取Parent、左孩子、右孩子、左兄弟、右兄弟的节点的index为第二个参数，返回与该节点有相应关系的节点。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。获取二叉树某个节点的相应关系的节点的方法是：

  • 双亲结点：遍历该二叉树，依次判断各个节点的左右Child节点的index是否和参数提供的相等，如果相等则将该节点返回。

  • 左孩子结点：遍历该二叉树，依次判断各个节点的index是否和参数提供的相等，如果相等则将该节点的BiTreeNode::left域返回。

  • 右孩子结点：遍历该二叉树，依次判断各个节点的index是否和参数提供的相等，如果相等则将该节点的BiTreeNode::right域返回。

  • 左兄弟结点：遍历该二叉树，依次判断各个节点的index是否和参数提供的相等，如果相等则将该节点的父节点的左孩子节点返回，如果等于该节点本身，则返回NULL。

  • 右兄弟结点：遍历该二叉树，依次判断各个节点的index是否和参数提供的相等，如果相等则将该节点的父节点的右孩子节点返回，如果等于该节点本身，则返回NULL。

如果要寻找的节点不存在，这五个操作均会抛出（throw）一个Error::NO_SUCH_NODE错误。

这五个操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • status InsertChild(BiTree& T, size_t index, bool LR, BiTree& c);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、被插入的节点的index为第二个参数、插入位置左或右作为第三个参数、要插入的树作为第四个引用参数，返回该操作执行的状态。该操作用于将某个非空无右子树的树插入到某个节点中。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。插入的方法是：首先找到要删除左或右子树的节点T，根据LR为0或者1，插入c为T中p所指结点的左或右子树，p所指结点的原有左子树或右子树则为c的右子树。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • status DeleteChild(BiTree& T, size_t index, bool LR);

    • 该操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、被插入的节点的index为第二个参数、插入位置左或右作为第三个参数，返回该操作执行的状态。该操作用于将树的某节点的左或右子树删除。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。插入的方法是：首先找到要删除左或右子树的节点T，根据LR为0或者1，删除c为T中p所指结点的左或右子树。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。
  1. status PreOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
  2. status InOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
  3. status PostOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);

这三个操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、一个回调函数指针作为第二个参数，返回该操作执行的状态。该操作用于遍历该二叉树。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。遍历的方法是递归调用遍历函数。遍历函数根据先序、中序或者是后序，按照对应的顺序递归执行遍历函数：

  • 先序遍历：对当前节点执行Visit函数、对左孩子递归调用遍历函数、对右孩子递归调用遍历函数。

  • 中序遍历：对左孩子递归调用遍历函数、对当前节点执行Visit函数、对右孩子递归调用遍历函数。

  • 后序遍历：对左孩子递归调用遍历函数、对右孩子递归调用遍历函数、对当前节点执行Visit函数。

该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

  • status LevelOrderTraverse(const BiTree& T, function<void(BiTreeNode\*)>);
    • 这三个操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、一个回调函数指针作为第二个参数，返回该操作执行的状态。该操作用于遍历该二叉树。首先，该操作检查二叉树是否已经被初始化了，如果没有被初始化，则返回一个Error::NOT_INIT的错误。层级遍历的实现方法如下：将根节点放入队列中，然后对它执行Visit函数并将其出队。然后将其左右子树放入队列（如果非空），循环执行直到队列为空。
    • 该操作的时间复杂度为O(N)，空间复杂度为O(logN)。

3.3 多表系统的实现

多表系统实现了添加一张表、更改当前表两个操作（没有实现删除表）。

添加一张二叉树

添加一张二叉树就等价于在vector<BiTree>中添加了一个BiTree的实例,该BiTree的所有字段都是按照默认初始化进行初始化的。因此，该二叉树虽然有了内存空间但是却是一个空二叉树，其root等关键字段都是无效的值。

更改当前二叉树

更改当前表就等价于修改了指向vector<BiTree>的下标。该下标的取值为0至vector<BiTree>的长度。修改下标即可实现修改当前表所指向的值。从而达到修改当前表的目的。

容易可得，这两个操作的时间复杂度都为O(1)。

3.4 文件存储系统实现

通过fopen可以返回一个指针，该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式，例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作，最后使用fclose销毁该指针。在写文件的时候，可以将整个elems数组以2进制的方式存入文件。在读取的时候，连续读取每次读取sizeof(T)个字节，然后将这些字节拷贝到elems里面，直到读取到文件尾为止。同时，每次读取使线性表的长度增加1个长度。

文件操作可以使二叉树的节点存放到硬盘上永久保存，更加贴近真实的使用场景。通过C语言标准库提供的文件读写API，可以很方便的操作文件。

通过fopen可以返回一个指针，该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式，例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作，最后使用fclose销毁该指针。

具体的实现为，写出到文件时，先将二叉树容器trees的size写出到文件，然后遍历多二叉树的容器trees，对于每一个BiTree，先将其节点数目写出，然后先序遍历该二叉树（由于需要可以复原该二叉树，该先序遍历允许空节点），将所有的节点依次写出到文件中，每次写出sizeof(ElemType)个字节。

读文件时将上述操作逆着执行一遍即可。

4 系统测试

4.1 演示系统测试

演示系统测试如下图所示：

该演示系统操作简单，输入对应的数字并按下回车即可。输入0-22表明运行对应的功能，且相应操作的结果会被输出到屏幕上，输入0退出系统。输入-1进入debug界面。

上传的附件 cloud_download 基于二叉链表的二叉树实现.zip ( 282.80kb, 46次下载 )
error_outline 下载需要8点积分

keyboard_arrow_left上一篇 : C语言实现的基于查找表的单词检索软件 基于QT实现的学生信息管理系统 : 下一篇keyboard_arrow_right

comment 1
Theevilspirit
2019-02-28 22:28:01
基于二叉链表的二叉树实现
mode_comment 评论(0)

Theevilspirit

发送私信

不要靠提高嗓门获取自己的存在感，那样只是虚张声势

15
文章数
17
评论数
最近文章
highlight comment

Copyright @2020-WRITE-BUG.COM 技术支持 - YCY科技 - 备案/许可证编号：京ICP备16025663号-5

eject