二叉平衡排序树设计报告

中北大学数据结构

课程设计说明书学生姓名刘永强 学号：学院：软件学院专业：软件工程题目：二叉平衡排序树指导教师何志英2011年12月20日设计任务概述用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车（'\n'）为输入结束标志，输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均查找长度，输出结果；输入元素x,查找二叉排序树丁若存在含x的结点，则删除该结点,并作中序遍历；否则输出信息“无结点x”；判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。本设计所采用的数据结构输入功能：可以输入结点输出功能:可以输出结点插入功能:可以插入结点删除功能:可以删除结点查找功能:可以查找结点结束功能：可以终止输入功能模块详细设计3.1详细设计思想：从一颗空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基本要求：（1） 创建（插入、调整、改组）；（2） 输出。3.2核心代码：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<errno.h>#include<assert.h>typedefstructnodenode;structnode(node*parent;node*left;node*right;intbalance;intkey;};externvoidinterordertraverse(node*root);externvoidpreordertraverse(node*root);externvoidpostordertraverse(node*root);intsearchNode(intkey,node*root,node**parent)(node*temp;assert(root!=NULL);temp=root;*parent=root->parent;while(temp!=NULL)(if(temp->key==key)return1;else*parent=temp;if(temp->key>key)temp=temp->left;elsetemp=temp->right;}}return0;}node*minNode(node*root)(if(root==NULL)returnNULL;while(root->left!=NULL)root=root->left;returnroot;}node*maxNode(node*root)(if(root==NULL)returnNULL;while(root->right!=NULL)root=root->right;returnroot;}node*preNode(node*target)(if(target==NULL)returnNULL;if(target->left!=NULL)returnmaxNode(target->left);elsewhile((target->parent!二NULL)&&(target!二target->parent->right))target=target->parent;returntarget->parent;}node*nextNode(node*target)(if(target==NULL)returnNULL;if(target->right!=NULL)returnminNode(target->right);elsewhile((target->parent!二NULL)&&(target!二target->parent->left))target=target->parent;returntarget->parent;}node*adjustAVL(node*root,node*parent,node*child)(node*cur;assert((parent!=NULL)&&(child!=NULL));switch(parent->balance)(case2:if(child->balance==-1)(cur=child->right;cur->parent=parent->parent;child->right=cur->left;if(cur->left!=NULL)cur->left->parent=child;parent->left=cur->right;if(cur->right!=NULL)cur->right->parent=parent;cur->left=child;child->parent=cur;cur->right=parent;if(parent->parent!=NULL)if(parent->parent->left==parent)parent->parent->left=cur;elseparent->parent->right=cur;elseroot=cur;parent->parent=cur;if(cur->balance==0)(parent->balance=0;child->balance=0;}elseif(cur->balance==-1)(parent->balance=0;child->balance=1;}else(parent->balance=-1;child->balance=0;}cur->balance=0;}else(child->parent=parent->parent;parent->left=child->right;if(child->right!=NULL)child->right->parent=parent;child->right=parent;if(parent->parent!=NULL)if(parent->parent->left==parent)parent->parent->left=child;elseparent->parent->right=child;elseroot=child;parent->parent=child;if(child->balance==1)(child->balance=0;parent->balance=0;}else(child->balance=-1;parent->balance=1;}}break;case-2:if(child->balance==1)(cur=child->left;cur->parent=parent->parent;child->left=cur->right;if(cur->right!=NULL)cur->right->parent=child;parent->right=cur->left;if(cur->left!=NULL)cur->left->parent=parent;cur->left=parent;cur->right=child;child->parent=cur;if(parent->parent!=NULL)if(parent->parent->left==parent)parent->parent->left=cur;elseparent->parent->right=cur;elseroot=cur;parent->parent=cur;if(cur->balance==0)(parent->balance=0;child->balance=0;}elseif(cur->balance==1)(parent->balance=0;child->balance=-1;}else(parent->balance=1;child->balance=0;}cur->balance=0;}else\(child->parent=parent->parent;parent->right=child->left;if(child->left!=NULL)child->left->parent=parent;child->left=parent;if(parent->parent!=NULL)if(parent->parent->left==parent)parent->parent->left=child;elseparent->parent->right=child;elseroot=child;parent->parent=child;if(child->balance==-1)(child->balance=0;parent->balance=0;}else(child->balance=1;parent->balance=-1;}}break;}returnroot;}node*insertNode(intkey,node*root)(node*parent,*cur,*child;assert(root!=NULL);if(searchNode(key,root,&parent))returnroot;else(cur=(node*)malloc(sizeof(node));cur->parent=parent;cur->key=key;cur->left=NULL;cur->right=NULL;cur->balance=0;if(key<parent->key)(parent->left=cur;child=parent->left;}else(parent->right=cur;child=parent->right;}while((parent!=NULL))(if(child==parent->left)if(parent->balance==-1)(parent->balance=0;returnroot;}elseif(parent->balance==1)(parent->balance=2;break;}else(parent->balance=1;child=parent;parent=parent->parent;}elseif(parent->balance==1)(parent->balance=0;returnroot;}elseif(parent->balance==-1)(parent->balance=-2;break;}else(parent->balance=-1;child=parent;parent=parent->parent;}}if(parent==NULL)returnroot;returnadjustAVL(root,parent,child);}}node*deleteNode(intkey,node*root)(node*dNode,*parent,*child,*tp;inttemp,tc;assert(root!二NULL);if(!searchNode(key,root,&parent))returnroot;else(if(parent==NULL)dNode=root;elseif((parent->left!=NULL)&&(parent->left->key==key))dNode=parent->left;elsedNode=parent->right;child=dNode;while((child->left!二NULL)||(child->right!二NULL))(if(child->balance==1)child=preNode(dNode);elsechild=nextNode(dNode);temp=child->key;child->key=dNode->key;dNode->key=temp;dNode=child;}child=dNode;parent=dNode->parent;while((parent!=NULL))(if(child==parent->left)if(parent->balance==1)(parent->balance=0;child=parent;parent=parent->parent;}elseif(parent->balance==-1)(parent->balance=-2;child=parent->right;temp=parent->right->balance;tp=parent->parent;if(tp!=NULL)if(parent==tp->left)tc=1;elsetc=-1;elsetc=0;root=adjustAVL(root,parent,child);if(temp==0)break;else(if(tc==1)child=tp->left;elseif(tc==-1)child=tp->right;parent=tp;}}else(parent->balance=-1;break;}elseif(parent->balance==-1)(parent->balance=0;child=parent;parent=parent->parent;}elseif(parent->balance==1)(parent->balance=2;child=parent->left;temp=parent->left->balance;tp=parent->parent;if(tp!=NULL)if(parent==tp->left)tc=1;elsetc=-1;elsetc=0;root=adjustAVL(root,parent,child);if(temp==0)break;else(if(tc==1)child=tp->left;elseif(tc==-1)child=tp->right;parent=tp;}}else(parent->balance=1;break;}}if(dNode->parent!=NULL)if(dNode==dNode->parent->left)dNode->parent->left=NULL;elsedNode->parent->right=NULL;free(dNode);if(root==dNode)root=NULL;dNode=NULL;returnroot;}node*createAVL(int*data,intsize)(inti;node*root;if(size<1)returnNULL;root=(node*)malloc(sizeof(node));root->parent=NULL;root->left=NULL;root->right=NULL;root->key=data[0];root->balance=0;for(i=1;i<size;i++)root=insertNode(data[i],root);returnroot;}voiddestroyAVL(node*root)(if(root!=NULL)(destroyAVL(root->left);destroyAVL(root->right);free(root);root=NULL;}}voidinterordertraverse(node*root)(if(root!=NULL)(interordertraverse(root->left);printf("%d,%d\n",root->key,root->balance);interordertraverse(root->right);}}voidpreordertraverse(node*root)(if(root!=NULL)(printf("%d,%d\n",root->key,root->balance);preordertraverse(root->left);preordertraverse(root->right);}}voidpostordertraverse(node*root)(if(root!=NULL)(postordertraverse(root->left);postordertraverse(root->right);printf("%d,%d\n",root->key,root->balance);}voidmain()(intdata口=(1,13,7,4},flag=1,n=0;node*root;node*parent;root=createAVL(data,sizeof(data)/sizeof(data[0]));printf(〃++++++++++++++++++++++++++++\n〃)；interordertraverse(root);printf(〃\n〃)；preordertraverse(root);printf(〃\n〃)；postordertraverse(root);while(flag)(inta;printf("pleasechoose:\n\t1:insert\n\t2:delete\n\t3:search\n\t4:exit\n");scanf(〃%d〃,&n);switch(n)(case1:printf("thedadayouwillinsert:");scanf("%d",&a);insertNode(a,root);printf("++++++++++++++++++++++++++++\n");interordertraverse(root);printf(〃\n〃)；preordertraverse(root);printf(〃\n〃)；postordertraverse(root);break;case2:printf("thedatayouwilldelete:");scanf(〃%d〃,&a);deleteNode(a,root);printf("++++++++++++++++++++++++++++\n");interordertraverse(root);printf("\n");preordertraverse(root);printf("\n");postordertraverse(root);