邢彬 /* XingBin.net */
XING Bin, a Coder, Geek, Railfan, and Outdoors Fan
face

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

发布 / 2006-03-11 18:26   于 / 邢彬作品   文 / XingBin   浏览 / 2700  

数据结构及存储结构设计:
    题目要求的两部分内容同时集成在了一个程序中,因此一共同时存在有三个树:使用链表结构存放的二叉排序树、使用链表结构存放的二叉平衡树、使用数组结构存放的二叉排序树。用户输入的数据使用数组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月版

LOGIN
FOLLOW ME
COPYRIGHT
Creative Commons License
除特殊声明的页面外,本站作品采用 知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议 进行许可。