1、4 实验一 基于二叉链表的二叉树的实现4.1 问题描述基于二叉链表和队列及其堆栈存储结构,实现二叉链表的二叉树的对数据进行各种必要的操作。4.2 系统设计1.2.1 提供 20 个功能,分别是:1.2.2 二叉链表的结构试一堆栈和队列的形式进行储存的分别是:1.2.3 在程序中所定义的数据结构有:2.3 系统实现1.3.1 InitTree 功能初始二叉链表,传入的是头结点地址。申请一个存储空间,并用头结点中的首结点指针指向该空间首地址,相应的 时间复杂度为 1。具体实现如下:1.3.2 DestroyTree 功能销毁头结点中首结点址针指向的线性存储空间,传入的是头结点地址。具体实现如下:1
2、.3.3 CreateBiTree 功能与 DestroyBiTree 类似但是又有不同, ClearBiTree 并不销毁物理空间,而是修改逻辑关系值:1.3.4 ClearBiTree 功能与 DestroyBiTree 类似但是又有不同, ClearBiTree 并不销毁物理空间,而是修改逻辑关系值1.3.5 BiTreeEmpty 功能判空功能,判断表是否为空表。时间复杂度为 1,因为只需判断一次就可以知道是否为空。实现如下:1.3.6 BiTreeDepth 功能求二叉链表深度的功能,由于创建过程中已经把表长信息包含在头结点中,所以直接调用并显示即可1.3.7 Root(BiTree
3、 T)功能获取二叉链表的根节点的元素,通过遍历二叉链表中的元素,来逐个判断,时间复杂度为(n) 。1.3.8 Value(BiTree T,TElemType e)功能求指定元素的前一个元素的内容,传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是递归算法。时间复杂度为 O(n)。具体实现如下:1.3.9 Assign 功能求指定元素的后一个元素的内容,传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。找到后,把新的数据值赋给所找到的节点。时间复杂度为 O(n)。具体实现如下:1.3.10 Parent 功能找双亲节点,找到后输出1.3.11 LeftChild 功能查找左孩子,利用递归的算法,与遍历的时间复杂度为相同 O(n)1.3.12RightChild 功能查找右孩子,利用递归的算法,与遍历的时间复杂度为相同 O(n)