数据结构课程.doc

数据结构课程设计报告题目：平衡二叉树的插入、查找、删除操作。 一、问题描述本设计综合运用课本第六章和第九章的平衡二叉树和静态、动态查找表知识，设计程序来实现对平衡二叉树的插入、查找、删除等操作。二、各模块设计概要1该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。2.（1）抽象数据类型静态查找表的定义为：ADT StaticSearchTable 数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。基本操作 P：Create(&ST, n); Destroy(&ST);Search(ST, key); Traverse(ST, Visit(); ADT StaticSearchTableCreate(&ST, n);操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy(&ST);初始条件：静态查找表ST存在；操作结果：销毁表ST。Search(ST, key);操作结果：若 ST 中存在其关键字等于key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST, Visit();操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。（2）抽象数据类型动态查找表的定义如下：ADT DynamicSearchTable 数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字， 可唯一标识数据元素。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT) DestroyDSTable(&DT)SearchDSTable(DT, key); InsertDSTable(&DT, e);DeleteDSTable(&T, key); TraverseDSTable(DT, Visit();ADT DynamicSearchTableInitDSTable(&DT);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初始条件：动态查找表DT存在；操作结果：销毁动态查找表DT。SearchDSTable(DT, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。InsertDSTable(&DT, e);初始条件：动态查找表DT存在，e 为待插入的数据元素；操作结果：若DT中不存在其关键字等于 e.key 的 数据元素，则插入 e 到DT。DeleteDSTable(&T, key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT, Visit();初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。3、主程序Void main() 初始化; 元素输入； 进行插入操作； 进行查找操作； 进行删除操作； 退出； 4.初始化模块：定义相关数据结构。typedef struct KeyType key; /关键字域ElemType;typedef struct BSTNode ElemType data; int bf; /设定结点的平衡因子 struct BSTNode *lchild,*rchild; /定义左右孩子指针BSTNode,*BSTree;5.左平衡模块：void LeftBalance(BSTree &T)/对以指针T所指节点为根的二叉树做左平衡旋转处理，此算法结束时，指针T指向新的根节点 BSTNode *lc,*rd; lc=T-lchild;/左子树指向根节点 switch(lc-bf)/检查*T的左子树的平衡度，并作相应平衡处理 case LH:/新节点插入在*T的左孩子的左子树上，要做单右旋处理 T-bf=lc-bf=EH; R_Rotate(T);/调用上面的R_Rotate()函数 break; case RH:/新节点插入在*T的左孩子的右子树上，要做双旋处理 rd=lc-rchild;/rd指向*T的左孩子的右子树根 switch(rd-bf)/修改*T及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=EH; lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild);/对*T的左子树作左旋平衡处理 R_Rotate(T);/对*T作右旋平衡处理 /switch(lc-bf)/LeftBalance/右平衡与左平衡过程刚好相反，执行代码不再演示6.插入数据元素模块：Status Insert BST(BiTree &T, ElemType e ) / 当二叉排序树中不存在关键字等于 e.key 的 / 数据元素时，插入元素值为 e 的结点，并返 / 回 TRUE; 否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BSTs = (BiTree) malloc (sizeof (BiTNode); / 为新结点分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 为新的根结点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子else p-rchild = s; / 插入 *s 为 *p 的右孩子return TRUE; / 插入成功7.元素查找模块：bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T)/查找不成功 p=f; coutSearch failed!data.key) )/查找成功 p=T; coutSearch Success.the key is: ; coutdata.keydata.key)/在左子树中继续查找 return SearchBST(T-lchild,key,T,p); else return SearchBST(T-rchild,key,T,p);/在右子树中继续查找8.元素删除模块：可分三种情况讨论（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树 T 中存在其关键字等于 key 的 / 数据元素，则删除该数据元素结点，并返回 / 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; / 不存在关键字等于key的数据元素 else / DeleteBSTif ( EQ (key, T-data.key) ) Delete (T); return TRUE; / 找到关键字等于key的数据元素else if ( LT (key, T-data.key) )DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找elseDeleteBST ( T-rchild, key ); / 继续在右子树中进行查找三、总程序功能实现代码/本程序演示平衡二叉树的插入，查找，删除等相关算法/*file：AVL* by：zhaopeng2010.6.22*/#include#include#include#include#define EQ(a,b) (a)=(b)/对两个数值型关键字比较约定为左边的宏定义#define LT(a,b) (a)(b)#define LH +1/左高#define EH 0/等高#define RH -1/右高typedef int KeyType;/定义关键字为整形/*定义相关数据结构*/typedef struct KeyType key; /关键字域ElemType;typedef struct BSTNode ElemType data; int bf; /设定结点的平衡因子 struct BSTNode *lchild,*rchild; /定义左右孩子指针BSTNode,*BSTree;/*/void InitBSTree(BSTree &T) T=NULL;/定义T为空树/*右旋转*/void R_Rotate(BSTree &p)/对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根节点，即旋转处理之前的左子树的根节点 BSTNode *lc; lc=p-lchild; /lc指向的*p的左子树根结点 p-lchild=lc-rchild; /lc的右子树挂接为*p的左子树 lc-rchild=p; p=lc; /p指新的根结点/R_Rotate/*/*左旋转*/void L_Rotate(BSTree &p)/对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根节点，即旋转处理之前的右子树的根节点 BSTNode *rc; rc=p-rchild; /rc指向的*p的右子树根结点 p-rchild=rc-lchild; /rc的左子树挂接为*p的右子树 rc-lchild=p; p=rc; /p指向新的根结点/L_Rotate/*/*左平衡*/void LeftBalance(BSTree &T)/对以指针T所指节点为根的二叉树做左平衡旋转处理，此算法结束时，指针T指向新的根节点 BSTNode *lc,*rd; lc=T-lchild;/左子树指向根节点 switch(lc-bf)/检查*T的左子树的平衡度，并作相应平衡处理 case LH:/新节点插入在*T的左孩子的左子树上，要做单右旋处理 T-bf=lc-bf=EH; R_Rotate(T);/调用上面的R_Rotate()函数 break; case RH:/新节点插入在*T的左孩子的右子树上，要做双旋处理 rd=lc-rchild;/rd指向*T的左孩子的右子树根 switch(rd-bf)/修改*T及其左孩子的平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=EH; lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild);/对*T的左子树作左旋平衡处理 R_Rotate(T);/对*T作右旋平衡处理 /switch(lc-bf)/LeftBalance/*/*右平衡*/void RightBalance(BSTree &T)/对以指针T所指节点为根的二叉树做右平衡旋转处理，此算法结束时，指针T指向新的根节点 BSTNode *lc,*ld; lc=T-rchild;/右子树指向根节点 switch(lc-bf)/检查*T的右子树的平衡度，并作相应平衡处理 case LH:/新节点插入在*T的左孩子的左子树上，要做单右旋处理 ld=lc-lchild; switch(ld-bf)/修改*T及其右孩子的平衡因子 case LH: T-bf=EH; lc-bf=RH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=LH; lc-bf=EH; break; /switch(rd-bf) ld-bf=EH; R_Rotate(T-rchild);/对*T的右子树作右旋平衡处理 L_Rotate(T);/对*T作左旋平衡处理 case RH: T-bf=lc-bf=EH; L_Rotate(T); break; /switch(lc-bf)/RightBalance/*/*插入操作*/int InsertAVL(BSTree &T,ElemType e,bool &taller) /若在平衡的二叉排序树中T中不存在和e有相同关键字的结点，则插入一个数据元素 /为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡 if(!T)/插入新结点，树长高，置taller为TURE /旋转处理，布尔变量taller反映T长高与否。 T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=true; else if(EQ(e.key,T-data.key)/树中已存在和e有相同关键字的结点 taller=false;/则不再进行插入 coutThe key e.key is existed.data.key)/应继续在*T的左子树中进行搜索 if(!InsertAVL(T-lchild,e,taller) / cout未插入。bf)/检查*T的平衡度 case LH:/原本左子树比右子树高，需要做左平衡处理 LeftBalance(T); taller=false; break; case EH:/原本左，右子树等高，现因左子树增高而使树增高 T-bf=LH; taller=true; break; case RH:/原本右子树比左子树高，现左右子树等高 T-bf=EH; taller=false; break; /switch(T-bf) /if else /应继续在*T的右子树中进行搜索 if(!InsertAVL(T-rchild,e,taller) / cout未插入。bf) /检查*T的平衡度 case LH:/原本左子树比右子树高，现左右子树等高 T-bf=EH; taller=false; break; case EH:/原本左，右子树等高，现因右子树增高而使树增高 T-bf=RH; taller=true; break; case RH:/原本右子树比左子树高，需要做右平衡处理 RightBalance(T); taller=false; break; /switch(T-bf) /else /else return 1;/InsertAVL/*/*搜索操作*/bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) if(!T)/查找不成功 p=f; coutSearch failed!data.key) )/查找成功 p=T; coutSearch Success.the key is: ; coutdata.keydata.key)/在左子树中继续查找 return SearchBST(T-lchild,key,T,p); else return SearchBST(T-rchild,key,T,p);/在右子树中继续查找/*/*删除结点时左平衡旋转处理*/void LeftBalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=LH) /p结点的左子树高，删除结点后p的bf减1,树变矮 p-bf=0; shorter=1; else if(p-bf=EH)/p结点左、右子树等高，删除结点后p的bf减1,树高不变 p-bf=RH; shorter=0; else /p结点的右子树高 p1=p-rchild;/p1指向p的右子树 if(p1-bf=EH)/p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 L_Rotate(p); p1-bf=LH; p-bf=RH; shorter=0; else if(p1-bf=RH)/p1的右子树高，左旋处理后，树变矮 L_Rotate(p); p1-bf=p-bf=EH; shorter=1; else /p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=EH) p-bf=EH; p1-bf=EH; else if(p2-bf=RH) p-bf=LH; p1-bf=EH; else p-bf=EH; p1-bf=RH; p2-bf=EH; p=p2; shorter=1; /*/*删除结点时右平衡旋转处理*/void RightBalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=RH) p-bf=EH; shorter=1; else if(p-bf=EH) p-bf=LH; shorter=0; else p1=p-lchild; if(p1-bf=EH) R_Rotate(p); p1-bf=RH; p-bf=LH; shorter=0; else if(p1-bf=LH) R_Rotate(p); p1-bf=p-bf=EH; shorter=1; else p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=EH) p-bf=EH; p1-bf=EH; else if(p2-bf=LH) p-bf=RH; p1-bf=EH; else p-bf=EH; p1-bf=LH; p2-bf=EH; p=p2; shorter=1; /*/*删除结点*/void Delete(BSTree q,BSTree &r,int &shorter) if(r-rchild=NULL) q-data=r-data; q=r; r=r-lchild; free(q); shorter=1; else Delete(q,r-rchild,shorter); if(shorter=1) RightBalance_div(r,shorter); /*/*平衡二叉树的删除操作*/ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter) ElemType k,a,b; a.key=1; b.key=0; BSTree q; if(p=NULL) coutNo exist key!data.key) )/在p的左子树中进行删除 k=DeleteAVL(p-lchild,key,shorter); if(shorter=1) LeftBalance_div(p,shorter); return k; else if(LQ(key.key,p-data.key) )/在p的右子树中进行删除 k=DeleteAVL(p-rchild,key,shorter); if(shorter=1) RightBalance_div(p,shorter); return k; else q=p; if(p-rchild=NULL) /右子树空则只需重接它的左子树 p=p-lchild; free(q); shorter=1; else if(p-lchild=NULL)/左子树空则只需重接它的右子树 p=p-rchild; free(q); shorter=1; else/左右子树均不空 Delete(q,q-lchild,shorter); if(shorter=1) LeftBalance_div(p,shorter); p=q; return a; /*/*打印函数*/void Print_BSTTree(BSTree T,int i)/i表示结点所在的层次，初始应该为0 if(T)/非空树 if(T-rchild) Print_BSTTree(T-rchild,i+1);/右子树递归调用显示 for(int j=1;j=i;j+) cout ; coutdata.keylchild) Print_BSTTree(T-lchild,i+1);/左子树递归调用显示 /*/*main函数*/int main()printf(nnnnnn);/*欢迎界面*/printf(*n;printf( * *n);printf( * *n);printf( * 平衡二叉树的插入，查找，删除等相关算法演示过程 *n)printf( * *n);printf( * *n);printf( * 姓 名:赵鹏 *n);printf( * *n)printf( * 班 级：电科07-1班 *n); printf( * *n);printf( * 学 号：200701050542 *n);printf( * *n)printf( * *n)printf( * *n);printf(*n); printf(nn); BSTree T; ElemType e; InitBSTree(T);/初试化树 bool tall=false; bool choice=true; char y; while(choice) coute.key;/输入数字，逐个插入到树T中 InsertAVL(T,e,tall);/执行插入操作 Print_BSTTree(T,0);/打印出树形结构图 couty;/输入信息 if(y=Y|y=y) choice=true;/y时则为真 else choice=false;/其他为假 BSTree f,p; choice=true; while(choice) coute.key;/输入数字 SearchBST( T,e,f