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

Theevilspirit

发布日期: 2019-02-28 22:27:22 浏览量: 702
评分:
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, 1次下载 )
error_outline 下载需要6点积分

发送私信

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

15
文章数
17
评论数
最近文章
eject