精选文档二叉排序树与平衡二叉树的实现

攀枝花学院学生课程设计（论文）题目：二叉排序树与平衡二叉树的实现学生姓名：学号：所在院(系)：计算机学院专业：班级：指导教师：职称：年月日攀枝花学院教务处制攀枝花学院本科学生课程设计任务书题目二叉排序树与平衡二叉树的实现1、课程设计的目的使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。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］严蔚敏等，《数据结构》（C语言版），清华大学出版社［3］WilliamFord，WilliamTopp，《DataStructurewithC++》清华大学出版社［4］苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分析和结果第5天课程设计报告和总结指导教师（签字）日期年月日教研室意见：年月日学生（签字）：接受任务时间：年月日注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称二叉排序树与平衡二叉树的实现评分项目分值得分评价内涵工作表现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,结点,二叉排序树,平衡二叉树目录TOC\o"1-3"\h\u14588对二叉排序树T作中序遍历，输出结果； 221712摘要： 419149第一章分析 677241.1功能描述 632300第二章系统设计 6257322.1基本概念介绍 68292树的概念 6230972.3插入结点 8301542.4删除结点 921402第一章编码 10178113.1总体编码 10139823.2总流程图 1179103.3以指针T所指结点为根的二叉树作右平衡旋转处理 1226442bf=RH 1211628其他旋转类推 1221829第二章测试 12245404.1创建平衡二叉树测试 12161034.2插入结点测试 14219544.3删除结点测试 1491984.4中序遍历二叉树 1513604第五章体会 1712927参考文献： 17 第一章分析1.1描述平衡二叉树（BalancedBinaryTree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。最小二叉平衡树的节点的公式如下F(n)=F(n-1)+F(n-2)+1这个类似于一个递归的数列，可以参考Fibonacci数列1是根节点F(n-1)是左子树的节点数量F(n-2)是右子数的节点数量。通过本程序的设计编写所要求达到的目的是：充分理解和掌握二叉树、平衡二叉树的相关概念和知识。掌握平衡二叉树的生成、结点删除、插入等操作过程。并实现从键盘上输入一系列数据（整型），建立一棵平衡二叉树。任意插入或删除一个结点后仍然要求构成平衡二叉树。按先序和中序遍历输出这棵平衡二叉树。第二章系统设计2.1基本概念介绍树的概念树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：有且仅有一个特定的称为根的结点；当n>1时，其余结点可分为m（m>0）A个互不相交的有限集T1，T2Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。ABCBCEDEDFFGGHH图1是有8个结点的树，其中A是根，其余结点分成2个子集：T1={B，D}，T2={C，E，F，G，H}；T1和T2都是根A的子树，且本身也是一棵树。平衡二叉树的概念形态匀称的二叉树称为平衡二叉树(Balancedbinarytree)：若T是一棵非空二叉树，其左、右子树分别为TL和TR，令hl和hr分别为左、右子树的深度。当且仅当①TL、TR都是平衡二叉树；②｜hl－hr｜≤1；时，则T是平衡二叉树。【例】如图1-2所示：AAAAAACBCBCBCBCBCBEFDDEFDDHGHG（a）平衡二叉树（b）非平衡二叉树图1-2平衡二叉树与非平衡二叉树图2-7平衡二叉树的生成过程2.3插入结点在平衡二叉排序树BBST上插入一个新数据元素e的递规算法可以描述如下：若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增加1；若e的关键字和BBST的根结点的关键字相等，则不进行插入；若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况处理之：BBST的根结点的平衡因子为－1（右子树深度大于左子树深度）：则将根结点的平衡因子更改为0，BBST的深度不变；BBST的根结点的平衡因子为0（左，右子树深度相等）：则将根结点的平衡因子更改为1，BBST的深度增加1；BBST的根结点的平衡因子为1（左子树深度大于右子树深度）：若BBST的左子树根结点的平衡因子为1，则需要进行单向右旋平衡处理，并且在右旋处理之后将根结点和右子树根结点的平衡因子更改为0，树的深度不变；若BBST的左子树根结点的平衡因子为－1，这需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变；若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加1时，分别就不同情况处理。2.4删除结点删除结点过程与插入结点的操作类似，基本过程是：平衡二叉树--找到要删除的结点--删除一个结点--变成二叉树--旋转--变回平衡二叉树。具体过程将详细设计中的代码。2.5中序遍历右遍历的定义可知，中序遍历二叉树的递规算法可以定义为：若二叉树为空，则空操作；否则中序遍历左子树访问根结点中序遍历右子树如中序遍历图2-8的二叉树，结点的访问顺序为：a→b→c→d→e→f→g图2-8编码3.1总体编码#include"stdio.h"#include"string.h"#include<stdlib.h>#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//读入#，返回空指针else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成结点T->data=ch;T->lchild=CreatBinTree();//构造左子树T->rchild=CreatBinTree();//构造右子树return(T);}}//========NLR先序遍历=============voidPreorder(BinTreeT){if(T){printf("%c",T->data);//访问结点Preorder(T->lchild);//先序遍历左子树Preorder(T->rchild);//先序遍历右子树}}//========LNR中序遍历===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}//==========LRN后序遍历============voidPostorder(BinTreeT){if(T){Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);}}//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========inthl,hr,max;TreeDepth(BinTreeT){if(T){hl=TreeDepth(T->lchild);//求左深度hr=TreeDepth(T->rchild);//求右深度max=hl>hr?hl:hr;//取左右深度的最大值NodeNum=NodeNum+1;//求结点数if(hl==0&&hr==0)leaf=leaf+1;//若左右深度为0，即为叶子。return(max+1);}elsereturn(0);}//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p;//定义结点的指针数组cqcq[1]=T;//根入队while(front!=rear){front=(front+1)%NodeNum;p=cq[front];//出队printf("%c",p->data);//出队，输出结点的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;//左子树入队}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;//右子树入队}}}//==========主函数=================voidmain(){BinTreeroot;inti,depth;printf("\n");printf("CreatBin_Tree；Inputpreorder:");//输入完全二叉树的先序序列，//用#代表虚结点，如ABD###CE##F##root=CreatBinTree();//创建二叉树，返回根结点do{//从菜单中选择遍历方式，输入序号。printf("\t**********select************\n");printf("\t1:PreorderTraversal\n");printf("\t2:IorderTraversal\n");printf("\t3:Postordertraversal\n");printf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n");printf("\t5:LevelDepth\n");//按层次遍历之前，先选择4，求出该树的结点数。printf("\t0:Exit\n");printf("\t*******************************\n");scanf("%d",&i);//输入菜单序号（0-5）switch(i){case1:printf("PrintBin_treePreorder:");Preorder(root);//先序遍历break;case2:printf("PrintBin_TreeInorder:");Inorder(root);//中序遍历break;case3:printf("PrintBin_TreePostorder:");Postorder(root);//后序遍历break;case4:depth=TreeDepth(root);//求树的深度及叶子数printf("BinTreeDepth=%dBinTreeNoden