《数据结构》课程实验报告（基于二叉链表的二叉树的实现））.doc

,实现二叉链表的二叉树的对数据进行各种必要的操作。,分别是: : : InitTree功能初始二叉链表,传入的是头结点地址。申请一个存储空间,并用头结点中的首结点指针指向该空间首地址,相应的时间复杂度为1。具体实现如下: DestroyTree功能销毁头结点中首结点址针指向的线性存储空间,传入的是头结点地址。具体实现如下: CreateBiTree功能与DestroyBiTree类似但是又有不同,ClearBiTree并不销毁物理空间,而是修改逻辑关系值: ClearBiTree功能与DestroyBiTree类似但是又有不同,ClearBiTree并不销毁物理空间, BiTreeEmpty功能判空功能,判断表是否为空表。时间复杂度为1,因为只需判断一次就可以知道是否为空。实现如下: BiTreeDepth功能求二叉链表深度的功能,由于创建过程中已经把表长信息包含在头结点中, Root(BiTreeT)功能获取二叉链表的根节点的元素,通过遍历二叉链表中的元素,来逐个判断,时间复杂度为(n)。 Value(BiTreeT,TElemTypee)功能求指定元素的前一个元素的内容,传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是递归算法。时间复杂度为O(n)。具体实现如下: Assign功能求指定元素的后一个元素的内容,传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。找到后,把新的数据值赋给所找到的节点。时间复杂度为O(n)。具体实现如下: Parent功能找双亲节点, LeftChild功能查找左孩子,利用递归的算法,与遍历的时间复杂度为相同O(n),利用递归的算法,与遍历的时间复杂度为相同O(n)