数据结构与算法课程设计说明书-AVL树

课程设计说明书课程名称：数据结构与算法设计题目：AVL树院系：计算机科学与信息工程学院课程设计任务书设计题目AVL树学生姓名所在院系计算机科学与信息工程专业、年级、班13软工1设计要求：设计、实现一个AVL树程序，为用户提供三种便利：(1)查找最快；(2)删除方便；(3)完善树的平衡。学生应完成的工作：(1)根据课程设计要求，分析思路并完善其功能；(2)根据功能设计并编写程序段、连接各程序段使之形成一个整体；(3)调试、运行程序进而得到正确的结果；(4)根据实验设计运行过程，写出实验论文并总结实验教训。参考文献阅读：(1)C语言程序设计（潭浩强第二版，清华大学出版社）；(2)数据结构（吴伟民等C语言版，清华大学出版社）；(3)数据结构实验教程（高晓兵等，清华大学出版社）；(4）C++数据结构与算法（AdamDrozdek，清华大学出版社）；(5)算法分析与设计（郑宗汉、郑晓明，清华大学出版社）。工作计划：(1)第一周：小组布置设计题目；说明进度安排；小组审题，查阅资料，进行设计前的必要资料准备。(2)第二周：程序编写、上机调试并上机调试程序、结果分析、撰写设计报告。任务下达日期：2015年6月日任务完成日期：2015年6月日指导教师（签名）：学生（签名）：AVL树摘要：树形结构是一类重要的非线性结构。树由节点与弧组成。与自然界的树不同，这些树是倒过来的：根在顶部，叶子在底部。根是一个没有父节点只有子节点的节点。而叶节点没有子节点或者子节点是空结构。本程序研究了树形结构的基础知识，包括相关定义、操作以及树在数据结构中的简单应用问题。主要运用图示以及相关的算法来研究树以技术在数据结构中的如干应用问题。在计算机应用的各个领域中都会遇到各种各样的数据结构，而树在数据结构中又是一个相当重要的非线性结构，广泛应用于计算机领域中。在现实生活中存在很多可以用树形结构描述的实际问题，比如家谱等。关键词：树、二叉树、数据结构、树的应用目录1、设计背景51.1树结构的广泛应用51.2树结构的需求52、设计方案 52.1总体设计流程52.2部分模块设计流程63.方案实施73.1二叉树的实现73.2二叉树的遍历84．结果与结论84.1关键程序代码段详细描述84.2运行结果115.收获与致谢126.参考文献137.附件131.设计背景1.1树结构的广泛应用链表通常可以提供比数据更大的灵活性，但由于链表是线性结构，所以很难使用它们来组织对象的分层表示。虽然栈和队列反映了某些层次，但他们是一维的。为了避免这种限制，我们创建了一个新的数据类型，称为树，树由节点与弧组成。1.2树结构的需求AVL树是平衡的二元查找树。一株平衡的二元查找树就是指对其每一个节点，其左子树和右子树的高度只差不超过1。编写程序实现AVL树的判别；并实现AVL树的ADT，包括其上的基本操作；节点的加入和删除。BSt和AVL的差别就在平衡性上，所以AVL的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。编写AVL树的判别程序，并判别一个人元查找数是否为AVL树。二元查找树用其先序遍历结果表示，如：5,2,1,3,7,8。实现AVL树的ADT，包括其上的基本操作：节点的加入和删除，另外包括将一般二元查找树转变为AVL树的操作。2.设计方案2.1总体设计流程主函数流程图：开始开始选择功能选择功能删 除节 点构建AVL树删 除节 点构建AVL树1 2查 找节 点查 找节 点插 入节 点插 入节 点0结束结束2.2部分模块设计流程构建AVL树和插入结点流程图：开始开始判断根结点是否存在判断根结点是否存在否是是否相同是否相同创建结点是 否创建结点插入失败插入失败插入插入平衡旋转处理平衡旋转处理结束结束查找函数流程图：开始开始判断判断输出查询数据输出查询数据查找失败查找失败结束结束删除函数流程图：开始开始查找查找删除数据删除失败删除数据删除失败结束结束3.方案实施3.1二叉树的实现二叉树至少可以以如下两种方式实现：数组和链接结构。为了用数组实现树，节点应声明为某种结构，其中包含一个信息字段和两个“指针”字段。指针字段包含了数组单元的下标，数组单元则存储了该节点的左右子节点（如果有的话）但是，即使数组很灵活（也就是使用向量），这种实现方法也很不方便。要插入新节点，必须知道子节点的位置，而这些位置必须按顺序查找。在从树中删除一个节点后，必须去除数组中留下的空隙。为此，可以对未用单元使用特殊的标记，但这可能会导致数组中包含大量的未用单元，还可以将元素移动一个位置，但这也要求更新对移动元素的引用。有时数组实现方式比较方便，在讨论堆时就使用了这种方式，但通常应使用另一种方法。在新的实现方法，节点是一个类的实例，该类由一个信息成员和两个指针成员组成。该节点由另一个类（该类将树作为整体对待）的成员函数使用并操作。因此，BSTNode类的成员声明为public，因为它们只能由BST类型对象的非公有成员访问，这样，信息隐藏的原则依然得到了遵守。将BSTNode的成员设置为public很重要，否则，BST派生的类将无法访问这些对象。3.2二叉树的遍历树的遍历是当且仅当访问树中每个节点一次的过程。遍历可以解释为把所有的节点放在一条线上，或者将树线性化。遍历的定义只指定了一个条件：每个节点仅访问一次，没有指定这些节点的访问顺序。因此，节点有多少种排列方式，就有多少种遍历方法。本程序中使用的是深度优先遍历，则深度优先遍历包括前、中、后序树遍历。4.结果与结论4.1关键程序代码段详细描述左旋二叉树代码思想:只要AVL树中任一节点的平衡因子小于-1或大于1,树就需要平衡。而左旋二叉树的思想是，经历一轮左旋，需要把n的左孩子接到subl的右孩子上，然后再把调整后的subl接到n的左孩子上，这样就形成了一个以n为根节点的AVL树。（右旋二叉树的思想与左旋雷同，方法对称）voidavl::LeftSpinTree(LinkNode*n){ inttag=0,flag1=0; right=n; n=right->RightChild; if(right!=first) tag=1; right->RightChild=n->leftChild; if(right->RightChild!=0) { right->RightChild->perint=right; flag1=1; } n->leftChild=right; if(right->perint!=0) { if(right->perint->data>right->data) { right->perint->leftChild=n; } else { right->perint->RightChild=n; } n->perint=right->perint; } else { n->perint=0; } right->perint=n; Root=n; if(tag==1) { Root=first; tag=0; } else { first=Root; Root->perint=0; } if(flag1==1) { right->blanceFactor=1; n->blanceFactor=-1; flag1=0; } else { right->blanceFactor=0; n->blanceFactor=0; }}先右后左旋代码思想：有的时候为了使树重新平衡，要执行双重旋转。这就有了先右后左旋和先左后右旋。这里的先右后左旋的思想为，先经历一轮右旋，使n的右孩子接到subr的左孩子上，再把subr作为n的右孩子；然后再经历一轮左旋，让n的左孩子作为subl的右孩子，再把subl作为n的左孩子。这样经过一轮先右后左旋，一棵新的平衡树就建成了。（先左后右旋思想与其雷同，顺序颠倒一下）voidavl::RightSpinLeft(LinkNode*n){ inttag=0; right=n; left=right->RightChild; n=left->leftChild; if(right!=first) tag=1; left->leftChild=n->RightChild; if(left->leftChild!=0) left->leftChild->perint=left; n->RightChild=left; left->perint=n; if(n->blanceFactor>=0) left->blanceFactor=0; else left->blanceFactor=1; right->RightChild=n->leftChild; if(right->RightChild!=0) right->RightChild->perint=right; n->leftChild=right; if(right->perint!=0) { if(right->perint->data<right->data) { right->perint->RightChild=n; } else { right->perint->leftChild=n; } n->perint=right->perint; } if(n->blanceFactor==1) right->blanceFactor=-1; else right->blanceFactor=0; right->perint=n; Root=n; if(tag==1) { Root=first; tag=0; } else { first=Root; Root->perint=0; } n->blanceFactor=0;}4.2运行结果1.建立平衡二叉树2.插入结点3.删除结点4.查找结点5.显示当前树5.收获与致谢总的来说,在整个设计的过程中,对二叉树的知识有了相当程度的了解掌握,基本上学会了对二叉树的设计和对二叉树的操作等。在对二叉树的自学过程中也认识，在学习的过程中要灵活的把所学的知识运用到实践当中，并且还要巩固练习和运用，这样才可以牢牢的记住。试验也对数据结构的知识进行了复习，尤其是图及最短路径等知识点，在对程序不断的修改和逐步改进提升的过程中，积累了不少经验，为在以后的学习和实践应用奠定了一定的基础。这次课程设计受益非浅，学到了不少知识，同时也认识到自身的不足，需要加强自身训练，学以致用，学会自我总结，吸取教训，积累经验，在学习和实践中来不断的提升自己。同时也非常感谢老师对我们的指导，我们也受益匪浅，在其中也学到了很多以前从未领会到的知识，让我感觉到的程序与算法设计的博大精深。在这次课程设计中也增强了我们对数据结构与算法的喜爱与兴趣。6.参考文献[1]C语言程序设计（潭浩强第二版，清华大学出版社）；[2]数据结构（吴伟民等C语言版，清华大学出版社）；[3]数据结构实验教程（高晓兵等，清华大学出版社）；[4]C++数据结构与算法（AdamDrozdek，清华大学出版社）；[5]算法分析与设计（郑宗汉、郑晓明，清华大学出版社）。7.附件附源程序：//MainAVL.cpp#include"AVL.h"#include<iostream>usingnamespacestd;intmain(){ charselect[100],slt;avlmm; intnum[1000],m=0,n=0,n1=0,total=0,t=0,tag=0,ll=0,ll2=0,f=0; cout<<"AVL树操作菜单"<<endl; cout<<"***********************************"<<endl; cout<<"1.建立平衡二叉树"<<endl; cout<<"2.插入结点"<<endl; cout<<"3.删除结点"<<endl; cout<<"4.查找结点"<<endl; cout<<"5.显示当前树"<<endl; cout<<"6.退出"<<endl; cout<<"***********************************"<<endl; cout<<"提示：本系统只能对数字进行相应操作！！！"<<endl<<endl; cout<<"请输入要执行的功能代号："; while(cin>>select) { if(!strcmp(select,"1")) { if(f==1) { cout<<"已存在一棵非空树！！若重新建树会造成已有的数据丢失！确定要重新建立吗？(y/n)"<<endl; cin>>slt; if(slt=='y'||slt=='Y') f=0; } if(slt=='y'||slt=='Y'||f==0) { f=1; mm.Root=0; cout<<"请输入要建立平衡二叉树的结点个数："; cin>>n; n=ll+n; cout<<"请输入要建立平衡二叉树的结点"<<endl; for(inti=0;i<n;i++) cin>>num[i]; for(inti=0;i<n;i++) { if(mm.InsertNode(num[i])==-1) { cout<<"结点"<<num[i]<<"已存在！！！"<<endl;n--; continue; } } cout<<"前序遍历"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍历"<<endl; mm.Displaym(mm.Root); cout<<endl; tag=0; } } elseif(!strcmp(select,"2")) { cout<<"请输入要插入的结点个数："<<endl; cin>>n1; n1=ll2+n1; cout<<"请输入要插入的结点"<<endl; for(inti=0;i<n1;i++) { cin>>num[i]; } for(inti=0;i<n1;i++) { if(mm.InsertNode(num[i])==-1) { cout<<"结点"<<num[i]<<"已存在！！！"; n1--; continue; } } cout<<"前序遍历"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍历"<<endl; mm.Displaym(mm.Root); cout<<endl; tag=0; } elseif(!strcmp(select,"3")) { if(tag==0) { total=n+n1; tag=1; } if(total==0) { cout<<"此树为空树，请新建一棵树！！！"<<endl; } else { cout<<"请输入要删除的结点值:"; cin>>m; t=mm.DeleteNode(m); if(t==1) total--; else { cout<<"没有要删除的结点！！！"<<endl; } if(total!=0) { cout<<"前序遍历"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍历"<<endl; mm.Displaym(mm.Root); cout<<endl; } else { cout<<"此树已删空!!!!"<<endl; total=0; n=0; n1=0; f=0; } } } elseif(!strcmp(select,"4")) { cout<<"请输入要查找的结点："<<endl; cin>>m; if(mm.FindNode(m,mm.Root)==1) { cout<<"存在要查的结点"; } else { cout<<"结点"<<m<<"不存在!!"<<endl; } } elseif(!strcmp(select,"5")) { if(mm.Root!=0) { cout<<"前序遍历"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍历"<<endl; mm.Displaym(mm.Root); cout<<endl; } else { cout<<"此树为空树！！！"<<endl; f=0; } } elseif(!strcmp(select,"6")) { exit(1); } else { cout<<"输入的选项非法！请正确输入！"<<endl; } } system("PAUSE");return0;}//AVL.h#ifndefAVL_H#defineAVL_H#include<iostream>#include<iomanip>usingnamespacestd;classLinkNode;classavl{ friendclassLinkNode;public: avl(); intInsertNode(int);//插入结点函数 intDeleteNode(int);//删除结点函数 intFindNode(int,LinkNode*);//查找结点函数 voidPushStack(LinkNode*);//结点路径入栈 LinkNode*PopStack();//结点路径出栈 voidLeftSpinTree(LinkNode*);//spin旋转，左旋二叉树 voidRightSpin(LinkNode*);//先左后右旋转 voidRightSpinTree(LinkNode*);//右旋二叉数 voidRightSpinLeft(LinkNode*);//先右后左旋 voidDisplay(LinkNode*); voidDisplaym(LinkNode*); LinkNode*Root;//根结点指针 LinkNode*first;private: LinkNode*right;//右旋指针 LinkNode*left;//左旋指针 LinkNode*stack[100];//路径查找结点存储栈 inttop;//栈顶指针 intbottom;//栈低指针};classLinkNode{ friendclassavl;public: LinkNode();private: intblanceFactor;//平衡因子 intdata; LinkNode*leftChild; LinkNode*RightChild; LinkNode*perint;//AVL.cpp#include"AVL.h"avl::avl(){ right=0; left=0; Root=0; top=-1; bottom=-1; for(inti=0;i<100;i++) stack[i]=0;}LinkNode::LinkNode(){ perint=0; leftChild=0; RightChild=0; data=0; blanceFactor=0;}voidavl::Display(LinkNode*n){ if(n!=0) { cout<<n->data<<""; Display(n->leftChild); Display(n->RightChild); }}voidavl::Displaym(LinkNode*n){ if(n!=0) { Displaym(n->leftChild); cout<<n->data<<""; Displaym(n->RightChild); }}voidavl::PushStack(LinkNode*n){ bottom=-1; top++; stack[top]=n;}LinkNode*avl::PopStack(){ LinkNode*n; bottom=-1; n=stack[top]; top--; returnn;}intavl::DeleteNode(intn){ LinkNode*pr=0,*p=Root,*q,*ppr; intd,dd=0,tag=0,tag1=0; top=-1;//初始化栈顶指针 while(p!=0)//查找要删除的结点并记录查找路径 { if(n==p->data) break; pr=p; PushStack(pr); if(n<p->data) p=p->leftChild; else p=p->RightChild;}if(p==0)return-1;if(p->leftChild!=0&&p->RightChild!=0) { pr=p; PushStack(pr); q=p->leftChild; while(q->RightChild!=0) { pr=q; PushStack(pr); q=q->RightChild; } p->data=q->data; p=q;}if(p->leftChild!=0)q=p->leftChild;else{ q=p->RightChild;}if(pr==0)Root=q;else{ if(pr->leftChild==p) { pr->leftChild=q; if(pr->leftChild!=0) pr->leftChild->perint=pr; tag=1; } else { pr->RightChild=q; if(pr->RightChild!=0) pr->RightChild->perint=pr; tag1=1; } while(top!=bottom) { pr=PopStack(); if(pr->leftChild!=0||pr->RightChild!=0) { if(pr->RightChild==q) { pr->blanceFactor--; } if(pr->leftChild==q) { pr->blanceFactor++; } } else { if(tag==1) { pr->blanceFactor++; tag=0; } if(tag1==1) { pr->blanceFactor--; tag1=0; } } if(pr->blanceFactor==1||pr->blanceFactor==-1) break; if(pr->blanceFactor!=0) { if(pr->blanceFactor<0) { d=-1; q=pr->leftChild; } else { d=1; q=pr->RightChild; } if(q->blanceFactor==0) { if(d==-1) { RightSpinTree(pr); } else { LeftSpinTree(pr); } break; } if(q->blanceFactor==d) { if(d==-1) RightSpinTree(pr); else LeftSpinTree(pr); } else { if(d==-1) RightSpin(pr); else RightSpinLeft(pr); } } q=pr; } } deletep; return1;}intavl::FindNode(intn,LinkNode*t){ inttag=0; while(t!=0) { if(n<t->data) t=t->leftChild; else { if(n>t->data)t=t->RightChild; else if(n==t->data) { tag=1; break; } } } if(tag!=1) return0; else return1;}intavl::InsertNode(intn){ LinkNode*p=0; LinkNode*pr=0; LinkNode*r=0; intd; p=Root; while(p!=0) { if(n==p->data) { return-1; } pr=p; PushStack(pr);//存储查找路径 if(n<p->data)//根据插入至的大小判断插入位置 p=p->leftChild; else p=p->RightChild; } p=newLinkNode; p->data=n; p->blanceFactor=0; if(Root==0) { Root=p; first=p; p->perint=0; return1; } p->perint=pr; if(n<pr->data) pr->leftChild=p; else pr->RightChild=p; while(top!=bottom) { LinkNode*temp; temp=PopStack(); if(p==temp->leftChild) temp->blanceFactor--; else temp->blanceFactor++; if(temp->blanceFactor==0) { top=-1; break; } if(temp->blanceFactor==1||temp->blanceFactor==-1) { p=temp; } if(temp->blanceFactor==2||temp->blanceFactor==-2) { top=-1;//初始化栈顶指针 d=(temp->blanceFactor<0)?-1:1; if(p->blanceFactor==d) { if(d==-1) { RightSpinTree(temp); } else { LeftSpinTree(temp); } } else { if(d==-1) { RightSpin(temp); } else RightSpinLeft(temp); } break; } }}voidavl::LeftSpinTree(LinkNode*n){ inttag=0,flag1=0; right=n; n=right->RightChild; if(right!=first) tag=1; right->RightChild=n->leftChild; if(right->RightChild!=0) { right->RightChild->perint=right; flag1=1; } n->leftChild=right; if(right->perint!=0) { if(right->perint->data>right->data) { right->perint->leftChild=n; } else { right->perint->RightChild=n; } n->perint=right->perint; } else { n->perint=0; } right->perint=n; Root=n; if(tag==1) { Root=first; tag=0; } else { first=Root; Root->perint=0; } if(flag1==1) { right->blanceFactor=1; n->blanceFactor=-1; flag1=0; } else { right->blanceFactor=0; n->blanceFactor=0; }}voidavl::RightSpinTree(LinkNode*n){inttag=0,flag1=0;left=n;n=left->leftChild;if(left!=first)tag=1;left->leftChild=n->RightChild;if(left->leftChild!=0){ left->leftChild->perint=left; flag1=1;}n->RightChild=left;if(left->perint!=0){ if(left->perint->data>left->data) { left->perint->leftChild=n; } else { left->perint->RightChild=n; } n->perint=left->perint;}else{ n->perint=0;}left->perint=n;Root=n;if(tag==1){ Root=first; tag=0;}else{ first=Root; Root->perint=0;}if(flag1==1){ left->blanceFactor=-1; n->blanceFactor=1; flag1=0;}else{ n->blanceFactor=0; left->blanceFactor=0;}}voidavl::RightSpin(LinkNode*n){ inttag=0; left=n; right=left->leftChild; n=right->RightChild; if(left!=first) tag=1; right->RightChild=n->leftChild; if(right->RightChild!=0) right->RightChild->perint=right; n->leftChild=right; right->perint=n; if(n->blanceFactor<=0) right->blanceFactor=0; else right->blanceFactor=-1; left->leftChild=n->RightChild; if(left->leftChild!=0) left->leftChild->perint=left; n->RightChild=left; if(left->perint!=0) { if(left->perint->data<left->data) { left->perint->RightChild=n; } else {