二叉排序树与平衡二叉树的实现

1、攀枝花学院学生课程设计（论文）题 目： 二叉排序树与平衡二叉树的实现 学生姓名： 学 号： 所在院(系)： 计算机学院 专 业： 班 级： 指 导 教 师： 职称： 年 月 日攀枝花学院教务处制攀枝花学院本科学生课程设计任务书题目二叉排序树与平衡二叉树的实现1、课程设计的目的1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据

2、、技术要求、工作要求等）(1) (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严蔚敏等，数据

3、结构（C语言版），清华大学出版社3William Ford，William Topp，Data Structure with C+清华大学出版社4苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划第1天 完成方案设计与程序框图 第2、3天 编写程序代码第4天 程序调试分析和结果第5天 课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）： 接受任务时间： 年 月 日注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称二叉排序树与平衡二叉树的实现评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的

4、科学工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能力水平35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。06设计（实验）能力，方案的设计能力5能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。07计算及计算机应用能力5具有较强的数据

5、运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析能力（综合分析能力、技术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成果质量45%09插图（或图纸）质量、篇幅、设计（论文）规范化程度5符合本专业相关规范或规定要求；规范化符合本文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名： 年月日摘要：二叉排序树：(1)若左子树不空，则左子树上所有节点的值均小于它的根结点的值；(2)若右子树不

6、空，则右子树上所有节点均大于它的根结点的值；(3)它的左右子树分别为二叉排序树。二叉平衡树：若不是空树，则(1)左右子树都是平衡二叉树；(2)左右子树的深度之差的绝对值不超过1。本次实验是利用二叉排序树和平衡二叉树达到以下目的：(1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输出结果；(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；(5)用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平

7、衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT； (6)计算平衡的二叉排序树BT的平均查找长度，输出结果。关键字：数列L,结点,二叉排序树,平衡二叉树目录对二叉排序树T作中序遍历，输出结果；2摘要：4第一章 分析61.1功能描述6第二章 系统设计62.1 基本概念介绍6树的概念62.3 插入结点82.4 删除结点9第一章 编码103.1 总体编码103.2 总流程图113.3 以指针T所指结点为根的二叉树作右平衡旋转处理12bf=RH12其他旋转类推12第二章 测试124.1 创建平衡二叉树测试124.2 插入结点测试144.3 删除结点测试144.4 中序遍历二叉树15第五章 体会

8、17参考文献：17第一章 分析1.1描述平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列 1是根节点 F(n-1)是左子树的节点数量 F(n-2)是右子数的节点数量。通过本程序的设计编写所要求达到的目的是：1. 充分理解和掌握二叉树、平衡

9、二叉树的相关概念和知识。2. 掌握平衡二叉树的生成、结点删除、插入等操作过程。3. 并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。4. 任意插入或删除一个结点后仍然要求构成平衡二叉树。5. 按先序和中序遍历输出这棵平衡二叉树。第二章 系统设计2.1 基本概念介绍树的概念树（Tree）是n（n=0）个结点的有限集。在任意一棵非空树中：1) 有且仅有一个特定的称为根的结点；2) 当n1时，其余结点可分为m（m0）A个互不相交的有限集T1，T2.Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。BCEDFGH图1是有8个结点的树，其中A是根，其余结点分成2个子集：T1=

10、B，D，T2=C，E，F，G，H；T1和T2都是根A的子树，且本身也是一棵树。平衡二叉树的概念形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ：若 T 是一棵非空二叉树，其左、右子树分别为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当TL 、 TR 都是平衡二叉树； hl hr 1；时，则 T 是平衡二叉树。【例】如图1-2 所示：AAACBCBCBEFDDHG（a）平衡二叉树 （b）非平衡二叉树图1-2 平衡二叉树与非平衡二叉树图2-7 平衡二叉树的生成过程2.3 插入结点在平衡二叉排序树BBST上插入一个新数据元素e的递规算法可以描述

11、如下：(1) 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增加1；(2) 若e的关键字和BBST的根结点的关键字相等，则不进行插入；(3) 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况处理之：1. BBST的根结点的平衡因子为1（右子树深度大于左子树深度）：则将根结点的平衡因子更改为0，BBST的深度不变；2. BBST的根结点的平衡因子为0（左，右子树深度相等）：则将根结点的平衡因子更改为1，BBST的深度增加1；3. BBS

12、T的根结点的平衡因子为1（左子树深度大于右子树深度）：若BBST的左子树根结点的平衡因子为1，则需要进行单向右旋平衡处理，并且在右旋处理之后将根结点和右子树根结点的平衡因子更改为0，树的深度不变；若BBST的左子树根结点的平衡因子为1，这需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变；(4) 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加1时，分别就不同情况处理。2.4 删除结点删除结点过程与插入结点的操作类似，基本过程

13、是：平衡二叉树-找到要删除的结点-删除一个结点-变成二叉树-旋转-变回平衡二叉树。具体过程将详细设计中的代码。2.5 中序遍历右遍历的定义可知，中序遍历二叉树的递规算法可以定义为：若二叉树为空，则空操作；否则1) 中序遍历左子树2) 访问根结点3) 中序遍历右子树如中序遍历图2-8的二叉树，结点的访问顺序为：abcdefg图2-8第一章 编码3.1 总体编码#includestdio.h#includestring.h#include#define Max 20 /结点的最大个数typedef struct node char data; struct node *lchild,*rchild

14、;BinTNode; /自定义二叉树的结点类型typedef BinTNode *BinTree; /定义二叉树的指针int NodeNum,leaf; /NodeNum为结点数，leaf为叶子数/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点#以示空指针的位置=BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar()=#) return(NULL); /读入#，返回空指针 else T=(BinTNode *)malloc(sizeof(BinTNode); /生成结点 T-data=ch; T-lchi

15、ld=CreatBinTree(); /构造左子树 T-rchild=CreatBinTree(); /构造右子树 return(T); /=NLR 先序遍历=void Preorder(BinTree T) if(T) printf(%c,T-data); /访问结点 Preorder(T-lchild); /先序遍历左子树 Preorder(T-rchild); /先序遍历右子树 /=LNR 中序遍历=void Inorder(BinTree T) if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /=LRN 后序

16、遍历=void Postorder(BinTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法= int hl,hr,max;TreeDepth(BinTree T) if(T) hl=TreeDepth(T-lchild); /求左深度 hr=TreeDepth(T-rchild); /求右深度 max=hlhr? hl:hr; /取左右深度的最大值 NodeNum=NodeNum+1; /求结点数 if(hl=0&hr=0) leaf=l

17、eaf+1; /若左右深度为0，即为叶子。 return(max+1); else return(0);/=利用先进先出（FIFO）队列，按层次遍历二叉树=void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum; p=cqfront; /出队 printf(%c,p-data); /出队，输出结点的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum;

18、 cqrear=p-lchild; /左子树入队 if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild; /右子树入队 /=主函数=void main() BinTree root; int i,depth; printf(n);printf(Creat Bin_Tree； Input preorder:); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=CreatBinTree(); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。 printf(t* select *n);

19、printf(t1: Preorder Traversaln); printf(t2: Iorder Traversaln); printf(t3: Postorder traversaln); printf(t4: PostTreeDepth,Node number,Leaf numbern); printf(t5: Level Depthn); /按层次遍历之前，先选择4，求出该树的结点数。 printf(t0: Exitn); printf(t*n); scanf(%d,&i); /输入菜单序号（0-5） switch (i) case 1: printf(Print Bin_tree

20、Preorder: ); Preorder(root); /先序遍历 break; case 2: printf(Print Bin_Tree Inorder: ); Inorder(root); /中序遍历 break; case 3: printf(Print Bin_Tree Postorder: ); Postorder(root); /后序遍历 break; case 4: depth=TreeDepth(root); /求树的深度及叶子数 printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum); printf( BinTree Leaf number=%d,leaf