数据结构课程设计报告 二叉树_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构课程设计报告 二叉树
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩14页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢1946人阅读
Java（48）
数据结构（33）
二叉排序树
二叉排序树又称为二叉查找树，它是一种特殊结构的二叉树，其定义为：二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：
（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
（3）它的左右子树也分别为二叉排序树。
这是一个递归定义。由定义可以得出二叉排序树的一个重要性质：中序遍历一个二叉排序树时可以得到一个递增有序序列。图1所示的二叉树就是一棵二叉排序树，若中序遍历图8.3（a）的二叉排序树，则可得到一个递增有序序列为：1，2，3，4，5，6，7，8，9。
&&&&&&&&&&&&&&&&&&&&&&&& (a) 二叉排序树示例1&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(b) 二叉排序树示例2(根据字符ASCII码的大小)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&图1二叉排序树
在下面讨论二叉排序树的操作中，使用二叉链表作为存储结构，其结点结构说明如下：
typedef struct node
{ KeyT /*关键字的值*/
struct node *lchild,*/*左右指针*/
}bstnode,*BST
1．二叉排序树的插入和生成
已知一个关键字值为key的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行：1）若二叉树序树是空树，则key成为二叉树序树的根；2）若二叉树序树非空，则将key与二叉树序树的根进行比较，如果key的值等于根结点的值，则停止插入，如果key的值小于根结点的值，则将key插入左子树，如果key的值大于根结点的值，则将key插入右子树。
例如，设关键字的输入顺序为：45，24 ，53，12，28，90，按上述算法生成的二叉排序树的过程如图2所示。
图2 二叉排序树的建立过程
对同样一些元素值，如果输入顺序不同，所创建的二叉树形态也不同。如上面的例子如果输入顺序为 24，53，90，12，28，45，则生成的二叉排序树如图3所示：
图3输入顺序不同所建立的不同二叉排序树
&2．二叉排序树的查找过程
　　由其定义可见，二叉排序树的查找过程为：
　　（1）若查找树为空，查找失败。
　　（2）查找树非空，将给定值key与查找树的根结点关键码比较。
　　（3）若相等，查找成功，结束查找过程，否则：
　　① 当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。
　　② 当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。
3．二叉排序树删除操作
　　从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。
　　设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。
　　（1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。
　　（2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。
　　（3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。
　　设删除*p结点前，中序遍历序列为：
　　① P为F的左子女时有：…，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。
　　② P为F的右子女时有：…，F，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…。
　　则删除*p结点后，中序遍历序列应为：
　　① P为F的左子女时有：…，Pi子树，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。
　　② P为F的右子女时有：…，F，Pi子树，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…。
　　有两种调整方法：
　　① 直接令Pi为*f相应的子树，以Pr为Pi中序遍历的最后一个结点Pk的右子树。
　　② 令*p结点的直接前驱Pr或直接后继（对Pi子树中序遍历的最后一个结点Pk）替换*p结点，再按（2）的方法删去Pr或Pk。
　　【算法分析】
　　对给定序列建立二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率和顺序查找一样。因此，对均匀的二叉排序树进行插入或删除结点后，应进行调整，使其依然保持均匀。
程序代码实现：
import java.util.ArrayD
import java.util.ArrayL
import java.util.L
import java.util.Q
public class BinarySortTree&T extends Comparable&T&& {
//二叉搜索树，二叉排序树
public class Node{
public Node(T data,Node parent,Node lchild,Node rchild){
this.data=
this.parent=
this.lchild=
this.rchild=
public boolean equals(Object obj){
if (this==obj) {
if (obj.getClass()==Node.class) {
Node target=(Node)
return data.equals(target.data)&&
lchild==target.lchild&&
rchild==target.rchild&&
parent==target.
public String toString() {
return &Node [data=&+data+&]&;
public BinarySortTree() {
public BinarySortTree(T t) {
this.root = new Node(t, null, null, null);
//添加节点
public void add(T element){
if (root==null) {
root=new Node(element, null, null, null);
Node current=
Node parent=
int cmp=0;
//搜索合适的叶子节点，以该叶子节点为父节点添加新节点
pareTo(current.data);
if (cmp&0) {
current=current.
current=current.
} while (current!=null);
//创建新节点
Node newNode=new Node(element, parent, null, null);
if (cmp&0) {
parent.rchild=newN
parent.lchild=newN
//删除节点
public void remove(T element){
//获取要删除的节点
Node target=getNode(element);
if (target==null) {
//左、右子树是否为空
if (target.lchild==null&&target.rchild==null) {
if (target==root) {
if (target==target.parent.lchild) {
target.parent.lchild=
target.parent.rchild=
target.parent=
} else if(target.lchild==null&&target.rchild!=null){
if (target==root) {
root=target.
if (target==target.parent.lchild) {
target.parent.lchild=target.
target.parent.rchild=target.
target.rchild.parent=target.
}else if(target.lchild!=null&&target.rchild==null){
if (target==root) {
root=target.
if (target==target.parent.lchild) {
target.parent.lchild=target.
target.parent.rchild=target.
target.lchild.parent=target.
Node lchildMaxNode=target.//存放左孩子最大的节点
while (lchildMaxNode.rchild!=null) {
lchildMaxNode=lchildMaxNode.
lchildMaxNode.parent.rchild=
lchildMaxNode.parent=target.
if (target==target.parent.lchild) {
target.parent.lchild=lchildMaxN
target.parent.rchild=lchildMaxN
lchildMaxNode.lchild=target.
lchildMaxNode.rchild=target.
target.parent=target.lchild=target.rchild=
//获取要指定的节点
public Node getNode(T element) {
while (p!=null) {
int pareTo(p.data);
if (cmp&0) {
} else if (cmp&0) {
//广度优先遍历
public List&Node& breadthFrist(){
Queue&Node& queue=new ArrayDeque&Node&();
List&Node& list=new ArrayList&Node&();
if (root!=null) {
queue.offer(root);
while (!queue.isEmpty()) {
list.add(queue.peek());
Node pNode=queue.poll();
if (pNode.lchild!=null) {
queue.offer(pNode.lchild);
if (pNode.rchild!=null) {
queue.offer(pNode.rchild);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：479511次
积分：5244
积分：5244
排名：第4893名
原创：92篇
转载：146篇
评论：46条
(1)(1)(1)(2)(1)(2)(9)(16)(19)(37)(19)(11)(1)(22)(5)(8)(1)(4)(6)(10)(1)(10)(3)(1)(4)(1)(8)(1)(2)(21)(12)404 - 找不到文件或目录。
404 - 找不到文件或目录。
您要查找的资源可能已被删除，已更改名称或者暂时不可用。&>&&>&&>&&>&二叉排序树与平衡二叉树的实现
二叉排序树与平衡二叉树的实现
上传大小：94KB
攀枝花学院本科学生课程设计任务书
题　目 二叉排序树与平衡二叉树的实现
1、课程设计的目的
使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。
使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。
3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。
2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）
(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历，输出结果；
(3)计算二叉排序树T查找成功的平均查找长度,输出结果；
(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；
(5)用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；
(6)计算平衡的二叉排序树BT的平均查找长度，输出结果。
3、主要参考文献
［1］刘大有等，《数据结构》（C语言版），高等教育出版社
［2］严蔚敏等，《数据结构》（C语言版），清华大学出版社
［3］William Ford，William Topp，《Data Structure with C++》清华大学出版社
［4］苏仕华等，数据结构课程设计，机械工业出版社
4、课程设计工作进度计划
完成方案设计与程序框图
编写程序代码
程序调试分析和结果
课程设计报告和总结
指导教师（签字）
教研室意见：
学生（签字）：
接受任务时间：
注：任务书由指导教师填写。
课程设计（论文）指导教师成绩评定表
题目名称 二叉排序树与平衡二叉树的实现
评分项目 分值 得分 评价内涵
20% 01 学习态度 6
遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。
02 科学实践、调研 7
通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。
03 课题工作量 7
按期圆满完成规定的任务，工作量饱满。
35% 04 综合运用知识的能力 10
能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。
05 应用文献的能力 5
能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。
06 设计（实验）能力，方案的设计能力 5
能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。
07 计算及计算机应用能力 5
具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。
08 对计算或实验结果的分析能力（综合分析能力、技术经济分析能力） 10
具有较强的数据收集、分析、处理、综合的能力。
45% 09 插图（或图纸）质量、篇幅、设计（论文）规范化程度 5
符合本专业相关规范或规定要求；规范化符合本文件第五条要求。
10 设计说明书（论文）质量 30
综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。
11 创新 10
对前人工作有改进或突破，或有独特见解。
指导教师评语
指导教师签名：
年　月　日
摘要及关键字
本程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”。
二叉排序树（又称二叉查找树）：(1)若左子树不空，则左子树上所有节点的值均小于它的根结点的值；(2)若右子树不空，则右子树上所有节点均大于它的根结点的值；(3)它的左右子树分别为二叉排序树。
二叉平衡树：若不是空树，则(1)左右子树都是平衡二叉树；(2)左右子树的深度之差的绝对值不超过1。
本次实验是利用二叉排序树和平衡二叉树达到以下目的：(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输出结果；
(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；(5)用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT； (6)计算平衡的二叉排序树BT的平均查找长度，输出结果。
关键字：数列L,结点,二叉排序树,平衡二叉树
摘要……………………………………………………………………………
1 绪论…………………………………………………………………………
1.1 课程设计的目的……………………………………………………………
1.2 相关知识的阐述……………………………………………………………
1.2.1一位数组的存储结构……………………………………………………
1.2.2建立二叉排序树………………………………………………………
1.2.3中序遍历二叉树…………………………………………………………
1.2.4平均查找长度……………………………………………………………
1.2.5平均二叉树（AVL树）……………………………………………………
1.2.6平衡因子…………………………………………………………………
1.2.7平衡二叉树的调整方法……………………………………………………
2 方案设计……………………………………………………………… 8
2.1 模块功能………………………………………………………………………8
3 算法设计…………………………………………………………………… 8
3.1 算法流程图…………………………………………………………………… 8
4 详细设计……………………………………………………………… 10
4.1 主程序………………………………………………………………… 10
4.2 定义二叉树结构……………………………………………………………… 11
4.3 建立二叉树…………………………………………………………………… 11
4.3.1二叉排序树的查找…………………………………………………………11
4.3.2二叉排序树的插入…………………………………………………………11
4.4 中序遍历…………………………………………………………………12
4.5 平均查找长度…………………………………………………………………12
4.6 删除节点…………………………………………………………………12
4.7 判断平衡二叉树……………………………………………………………… 13
5 调试分析………………………………………………………………………… 14
5.1 时间复杂度的分析………………………………………………………………14
5.2 运行结果………………………………………………………………… 14
5.3 结果分析………………………………………………………………… 15
6 课程设计总结…………………………………………………………………… 16
参考文献………………………………………………………………………… 17
1.1 课程设计的目的
(1)使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。
(2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。
(3)使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。
1.2 相关知识的阐述
1.2.1 一维数组的存储结构
建立二插排序树，首先用一个一维数组记录下读入的数据，然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0” 补齐。
1.2.2 建立二叉排序树
二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
插入算法：
首先执行查找算法，找出被插结点的父亲结点；
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入；
若二叉树为空，则首先单独生成根结点。
注意：新插入的结点总是叶子结点。
1.2.3 中序遍历二叉树
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；
否则(1)中序遍历左子树（L）；
(2)访问根结点（V）；
(3)中序遍历右子树（R）。
中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。
1.2.4 平均查找长度
计算二叉排序树的平均查找长度时，采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。
假设在含有n(n&=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下，其平均查找长度为：
ASL(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n
其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：
当n&=2时，ASL(n)&=2(1＋1/n)ln(n)
由此可见，在随机的情况下，二叉排序树的平均查找长度和log（n）是等数量级的。
另外，含有n个结点的二叉排序树其判定树不是惟一的。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。
而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：　　①在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。　　②在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。　　③插入、删除和查找算法的时间复杂度均为O(lgn)。
1.2.5 平衡二叉树( AVL树 )
①平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高度大致相同。
　②任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。
　③平衡的二叉排序树指满足BST性质的平衡二叉树。
　④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树高度约为lgn，AVL树是最接近最优的。
1.2.6 平衡因子
二叉树上任一结点的左子树深度减去右子树的深度称为该结点的平衡因子，易知平衡二叉树中所有结点的因子只可能为0，-1和1。
平衡二叉排序树的在平衡因子绝对值等于2时开始调整到绝对值为1或0，在平衡因子绝对值为2时，二叉排序树会出现四种不同的情况的树形，因此这时需要分别单独讨论来降低平衡因子。
1.2.7 平衡二叉树的调整方法
　　平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
(1)每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
(2)若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
(3)判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
(4)如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
(5)计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
2.1 模块功能
1.建立二叉树：要求以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T。
2.中序遍历并输出结果：要求将第一步建立的二叉树进行中序遍历，并将结果输出。
3.平均查找长度并输出：要求计算二叉排序树T查找成功的平均查找长度,输出结果。
4.删除节点：要求输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
5.生成平衡二叉树：要求用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；
6.平均查找长度：计算平衡的二叉排序树BT的平均查找长度，输出结果。
3.1 算法流程图
建立二叉树流程图：
主程序流程图：
中序遍历流程图：
删除节点流程图：
4.1 主程序
void main()
s=0,j=0,i=0;
printf(&请输入一组数字并输入0为结束符:&);
scanf(&%d&,&num);
if(!num) printf(&你成功完成了输入!\n&);
insertBST(&T,num);
}while(num);
printf(&\n\n---操作菜单---\n&);
printf(&\n
printf(&\n
中序遍历&);
printf(&\n
平均查找长度&);
printf(&\n
printf(&\n
判断是否是平衡二叉树&);
while(ch==ch)
printf(&\n
选择操作并继续:&);
scanf(&%d&,&ch);
switch(ch){
/*0－－退出*/
中序遍历结果是:\n
inorderTraverse(&T);
s=0;j=0;i=0;
calculateASL(&T,&s,&j,i);
ASL=%d/%d&,s,j);
请输入你想删除的数字:&);
scanf(&%d&,&num);
if(searchBST(T,num,NULL,&p))
T=Delete(T,num);
你已成功删除该数字!\n
inorderTraverse(&T);
没有你想要删除的节点 %d!&,num);
balanceBST(T,&i);
OK!这是平衡二叉树!&);
printf(&你的输入有误!请重新输入!\n&);
4.2 定义二叉树结构
#include&stdio.h&
typedef struct Tnode
}*node,BST
4.3 建立二叉树
4.3.1 二叉排序树的查找
searchBST(node t,int key,node f,node *p){
/*在根指针t所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素节点，并返回（1），否则指针p指向查找路径上访问的最后一个节点并返回（0），指针f指向t的双亲，其初始调用值为NULL*/
{*p=f;return (0);}
/*查找不成功*/
if(key==t-&data)
{*p=t;return (1);}
/*查找成功*/
if(key&t-&data)
searchBST(t-&lchild,key,t,p); /*在左子树中继续查找*/
searchBST(t-&rchild,key,t,p);
/*在右子树中继续查找*/
4.3.2 二叉排序树的插入
insertBST(node *t,int key){
/*当二叉排序树t中不存在关键字等于key的数据元素时，插入key并返回（1），否则返回（0）*/
node p=NULL,s=NULL;
if(!searchBST(*t,key,NULL,&p))
/*查找不成功 */
s=(node)malloc(sizeof(BSTnode));
s-&lchild=s-&rchild=NULL;
/*被插入节点*s为新的根节点*/
if(key&p-&data)
p-&lchild=s; /*被插节点*s为左孩子*/
p-&rchild=s;
/*被插节点*s为右孩子*/
return (1);
return (0); /*树中已有关键字相同的节点，不再插入*/
4.4 中序遍历
inorderTraverse(node *t) /*中序遍历*/
if(inorderTraverse(&(*t)-&lchild))
{ printf(&%d
&,(*t)-&data);
if(inorderTraverse(&(*t)-&rchild)); }
return(1);
4.5 平均查找长度
calculateASL(node *t,int *s,int *j,int i)
/*计算平均查找长度*/
{if(*t){ i++; *s=*s+i;
if(calculateASL(&(*t)-&lchild,s,j,i))
if(calculateASL(&(*t)-&rchild,s,j,i))
{i--; return(1);}
return(1);
4.6 删除节点
node Delete(node t,int
{ /*若二叉排序树t中存在关键字等于key的数据元素时，则删除该数据元素节点
p=t,q=NULL,s,f;
while(p!=NULL)
{ if(p-&data==key)
if(p-&data&key)
if(p==NULL)
if(p-&lchild==NULL)
{ if(q==NULL)
if(q-&lchild==p)
q-&lchild=p-&
q-&rchild=p-&
else{ f=p;
while(s-&rchild)
f-&lchild=s-&
f-&rchild=s-&
p-&data=s-&
4.7 判断平衡二叉树
int balanceBST(node t,int *i) /*判断平衡二叉树*/
dep1,dep2;
return(0);
{ dep1=balanceBST(t-&lchild,i);
dep2=balanceBST(t-&rchild,i);
if((dep1-dep2)&1||(dep1-dep2)&-1) *i=dep1-dep2;
if(dep1&dep2) return(dep1+1);
return(dep2+1); }
5.1 时间复杂度的分析
为了保证二叉排序树的高度为lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的时间复杂度为O(lgn)。
5.2 运行结果
图5.1.1 调试界面
在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资料和同学的帮助下，发现程序未对数组初始化。添加数组初始化代码：
s=(node)malloc(sizeof(BSTnode))
输入一组数列，以结0结束：
图5.2.2运行界面一
图5.2.3运行界面二
计算平均查找长度
图5.2.4运行界面三
删除已有结点:
图5.2.5运行界面四
删除失败：
图5.2.6运行界面五
判断是否是平衡二叉树:
图5.2.7运行界面六
5.3 结果分析
通过运行程序和严密的求证,运行结果无误,不过对于转换平衡二叉树和平衡二叉树平均查找长度未能实现，同时也无法实现图像显示。
课程设计总结
在这一周的课程设计中，其实对我来说还是收获颇多。这不光提高了我的程序设计能力，更为我的就业增加了筹码。对我们来说，独立完成这样课程设计是比较困难，其中包括模块的组成分析和模块功能的实现。最后我不得不从网上下载源程序，借助课本，困难地将几个模块串起来。最后终于完成了自己的课程设计。
这次实验中我也出现过一些比较严重的错误。在用一维数组顺序表结构编写程序时我错误的运用静态链表来实现函数功能。这是我对基本概念理解的模糊不清造成的。我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构，而实质上这根本是两个不相干的概念。后来在同学的指点下我意识到自己的错误。不过收获也很不少。至少我又练习了运用静态链表来实现同样的功能，同时我也发现两者在很多函数上是互通的，只需稍作修改即可移植。
另外程序的不足之处是不能实现对0这个数字的存储，可以通过改变数字的存储结构方式来实现，如使用二叉链表来作为数据的存储结构，即可实现该功能。还有就是可能自己学的还不够,对于最后两个要求未能完成,不得不说这是自己学艺不精。
现在觉得以前我对数据结构的认识是那么的肤浅，因此我下定决心寒假一定好好的把数据结构复习一遍。而且本次课程设计不光增强了我程序调试的能力，还有在面对一个较大的程序要冷静，不要浮躁，先分析模块要实现的功能，再把模块划分，最后到一个一个得模块实现，并且要不断地练习，这样，一个大的程序对我来说将不成问题。
［1］刘大有等，《数据结构》（C语言版），高等教育出版社
［2］严蔚敏等，《数据结构》（C语言版），清华大学出版社
［3］William Ford，William Topp，《Data Structure with C++》清华大学出版社
［4］苏仕华等，数据结构课程设计，机械工业出版社...展开收缩
综合评分：4.5（36位用户评分）
所需积分：5
下载次数：112
审核通过送C币
创建者：w_z_z_1991
创建者：nigelyq
创建者：weixin_
课程推荐相关知识库
上传者其他资源上传者专辑
开发技术热门标签
VIP会员动态
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
android服务器底层网络模块的设计方法
所需积分：0
剩余积分：720
您当前C币：63
可兑换下载积分：126
兑换下载分：
兑换失败，您当前C币不够，请先充值C币
消耗C币：0
你当前的下载分为234。
二叉排序树与平衡二叉树的实现
会员到期时间：
剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
lijuan123456woshifen
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：}