二叉平衡排序樹設(shè)計報告

中北大學數(shù)據(jù)結(jié)構(gòu)

課程設(shè)計說明書學生姓名劉永強 學號：學院：軟件學院專業(yè)：軟件工程題目：二叉平衡排序樹指導(dǎo)教師何志英2011年12月20日設(shè)計任務(wù)概述用二叉鏈表作存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)二叉排序樹上的基本操作：以回車（'\n'）為輸入結(jié)束標志，輸入數(shù)列L,生成二叉排序樹T；對二叉排序樹T作中序遍歷；計算二叉排序樹T的平均查找長度，輸出結(jié)果；輸入元素x,查找二叉排序樹丁若存在含x的結(jié)點，則刪除該結(jié)點,并作中序遍歷；否則輸出信息“無結(jié)點x”；判斷二叉排序樹T是否為平衡二叉樹；再用數(shù)列L,生成平衡二叉排序樹BT:當插入新元素之后，發(fā)現(xiàn)當前的二叉排序樹BT不是平衡二叉排序樹，則立即將它轉(zhuǎn)換成新的平衡二叉排序樹BT；計算平衡的二叉排序樹BT的平均查找長度，輸出結(jié)果。本設(shè)計所采用的數(shù)據(jù)結(jié)構(gòu)輸入功能：可以輸入結(jié)點輸出功能:可以輸出結(jié)點插入功能:可以插入結(jié)點刪除功能:可以刪除結(jié)點查找功能:可以查找結(jié)點結(jié)束功能：可以終止輸入功能模塊詳細設(shè)計3.1詳細設(shè)計思想：從一顆空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調(diào)整。最終要把創(chuàng)建好的二叉排序樹轉(zhuǎn)換為二叉平衡排序樹。基本要求：（1） 創(chuàng)建（插入、調(diào)整、改組）；（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);