深入研究树的结构 数据结构课程设计作品

数据结构及存储结构设计：
    题目要求的两部分内容同时集成在了一个程序中，因此一共同时存在有三个树：使用链表结构存放的二叉排序树、使用链表结构存放的二叉平衡树、使用数组结构存放的二叉排序树。用户输入的数据使用数组L存放。各函数通过传递其指针对数据的读取或修改操作。

算法设计思想：

链表结构的二叉排序树：
    建立、插入：首先指向根结点。结点若不存在则将其建立，否则和其比较：值较小则转至其左儿子，较大则转至右儿子。并按此递归。
删除：如果左右儿子都为空，直接删除；如果只有左儿子或右儿子，将其父结点指向其儿子，并删除本结点；否则，将其中序遍历的前驱覆盖本结点，并删除该前驱。

链表结构的二叉平衡树：
    建立、插入：如果树为空，直接插入，树深增1；否则，若小，转至左子树，若大，转至右子树，否则不插入；当转至左子树时，如果树是右深或等深，直接插入，并修改相关平衡因子；如果是左深，则找出其最小不平衡子树进行旋转直至平衡为止；右子树操作类似。并由此递归。

数组结构的二叉平衡树：
    建立、插入：首先n=1；如果第n元素是-1（初始化时的数值），说明其为空，直接插入；否则和其比较，若大，转至其右儿子（n=2n）；若小，转至其左儿子（n=2n-1）；否则不插入。并由此递归。
删除：首先找到该结点位置n；若左右儿子位置均为-1，则直接将其删除（值变为-1）；若右儿子为空左儿子不为空，则逐层将左儿子及其后代的值向上覆盖；否则找到其中序遍历的直接后继，将其覆盖掉自己，并转而删除该后继。并由此递归。

对比查找效率：

链表结构的树查找时和关键字比较的次数不超过树的深度。进行查找时的平均查找长度和二叉树的形态有关。对于各个结点的查找概率相同时，最坏情况就是得到了一棵深度为n的单支树，它的平均查找长度是(n+1)/2，时间复杂度O(n)；最好情况就是形态比较匀称，是一棵形态与折半查找的判定树相似的二叉排序树，此时它的平均查找长度约为log2n，时间复杂度O(logn)。
对于二叉平衡树，最好情况是类似于判定树，平均查找长度log2n，时间复杂度O(logn)，对于最糟糕的情况，其时间复杂度亦为O(logn)。

程序演示：

集成界面

输入数据

查看数据

内存显示

遍历结果及树的查看

参考资料：

《数据结构（C语言版）》
颜蔚敏 吴伟民 编著
清华大学出版社 1997年4月版

《Turbo C/Borland C++ 用户界面程序设计》
周升锋、李立新、孙传俊编著
西安交通大学出版社 1994年12月版