數(shù)據(jù)結(jié)構(gòu)課設(shè)（五）二叉排序樹與平衡二叉樹的實(shí)現(xiàn) C代碼
一、問題描述
假定二叉排序樹與平題所處理數(shù)據(jù)均為整型。分別采用二叉鏈表和順序表作存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)對(duì)二叉衡二叉樹的操作。具體要求如下:
（1）用二叉鏈表作存儲(chǔ)結(jié)構(gòu):
①讀入一個(gè)整數(shù)序列L(要求該整數(shù)序列從磁盤文件讀取),生成一棵二叉排序樹②對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果。③計(jì)算二叉排序樹T查找成功的平均查找長度,輸出結(jié)果。④輸入元素x,查找二叉排序樹T。若存在含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作②);否則輸出信息“無x”。⑤用數(shù)列L,生成一棵平衡的二叉排序樹BT。如果當(dāng)插人新元素之后,發(fā)現(xiàn)當(dāng)前的二叉排序樹BT不是平衡的二叉排序樹，則將它轉(zhuǎn)換成平衡的二叉排序樹BT.⑥計(jì)算平衡的二叉排序樹BT的平均查找長度,輸出結(jié)果。
(2)用順序表作存儲(chǔ)結(jié)構(gòu):
①讀人一個(gè)整數(shù)序列L(要求該整數(shù)序列從磁盤文件讀取),生成一棵二叉排序樹T.②對(duì)二叉排序樹T作中序遍歷,輸出結(jié)果。③計(jì)算二叉排序樹T查找成功的平均查找長度,輸出結(jié)果。④輸人元素x,查找二叉排序樹T. 若存在含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷。
二、代碼
經(jīng)過分析，本題需要完成的需求是：分別以順序表和二叉鏈表完成輸入，中序遍歷排序，查刪結(jié)點(diǎn)，求平均查找長度的操作。
1.C代碼
代碼如下（示例）：文章來源：http://www.zghlxwxcb.cn/news/detail-520814.html
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node
{
int data;
int height;
Node *rchild,*lchild,*parent;
}BSTNode,*BSTree;
BSTNode *T;
void insertBST(int k)
{
BSTNode *y=NULL;
BSTNode *x=T;
BSTNode *z;
z=(BSTNode *)malloc(sizeof(Node));
z->data=k;
z->height=1;
z->lchild=NULL;
z->rchild=NULL;
while(x!=NULL)
{
y=x;
if(z->data<x->data)
{
x=x->lchild;
z->height++;
}
else
{
x=x->rchild;
z->height++;
}
}
z->parent=y;
if(y==NULL) T=z;
else
{
if(z->data<y->data) y->lchild=z;
else y->rchild=z;
}
}
void Inorder(BSTNode *u)
{
if(u==NULL) return;
Inorder(u->lchild);
printf("%d ",u->data);
Inorder(u->rchild);
}
double CalLength(BSTree *T)
{
static double length=0;
static int n=0;
if(*T)
{
length+=(*T)->height;
CalLength(&(*T)->lchild);
n++;
CalLength(&(*T)->rchild);
}
return length/n;
}
BSTree SearchDeleteBST(int key) //刪除函數(shù)
{
BSTree p=T,q=NULL,s,f;
while(p!=NULL) //查找要?jiǎng)h除的點(diǎn)
{
if(p->data==key)
break;
q=p; //q指向要?jiǎng)h結(jié)點(diǎn)的父母
if(p->data>key) p=p->lchild;
else p=p->rchild;
}
if(p==NULL)
return T; //查找失敗
if(p->lchild==NULL) //p指向當(dāng)前要?jiǎng)h除的結(jié)點(diǎn)
{
if(q==NULL) T=p->rchild;
else if(q->lchild==p) q->lchild=p->rchild; //p為q的左孩子
else q->rchild=p->rchild; //p為q的右孩子
free(p);
}
else
{ //p的左孩子不為空
f=p;
s=p->lchild;
while(s->rchild) //左拐后向右走到底
{
f=s;
s=s->rchild;
}
if(f==p) f->lchild=s->lchild; //重接f的左子樹
else f->rchild=s->lchild; //重接f的右子樹
p->data=s->data;
free (s);
}
return T;
}
int searchBST(BSTree T,int key,BSTree f,BSTree *p) //查找函數(shù)
{
if(!T)
{
*p=f;
return 0;
} //查找不成功
else if(key==T->data)
{
*p=T;
return 1;
} /*查找成功*/
else if(key<T->data) searchBST(T->lchild,key,T,p); //在左子樹中繼續(xù)查找
else searchBST(T->rchild,key,T,p); //在右子樹中繼續(xù)查找
}
int main()
{
int num;
char ch;
BSTree p=NULL;
printf("輸入L:");
do
{
scanf("%d",&num);
insertBST(num);
scanf("%c",&ch);
if(ch=='\n') break;
}while(ch!='\n');
printf("中序遍歷結(jié)果為:\n");
Inorder(T);
printf("\n");
printf("平均查找長度為：%3.1f",CalLength(&T));
printf("\n");
printf("輸入查找元素,若該結(jié)點(diǎn)存在則刪除該結(jié)點(diǎn):");
scanf("%d",&num);
if(searchBST(T,num,NULL,&p))
{
T=SearchDeleteBST(num);
printf("\n刪除成功，中序遍歷輸出：\n");
Inorder(T);
}
else
printf("沒有找到該結(jié)點(diǎn)%d",num);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define LH 1
#define EH 0
#define RH -1
typedef struct Node
{
int data;
int BF;//平衡因子（balance factor）
struct Node *lchild,*rchild;
}BSTNode,*BSTree;
void R_Rotate(BSTree *p)//以p為根節(jié)點(diǎn)的二叉排序樹進(jìn)行右旋轉(zhuǎn)
{
BSTree L;
L=(*p)->lchild;
(*p)->lchild=L->rchild;
L->rchild=(*p);
*p=L;//p指向新的根節(jié)點(diǎn)
}
void L_Rotate(BSTree *p)//以p為根節(jié)點(diǎn)的二叉排序樹進(jìn)行左旋轉(zhuǎn)
{
BSTree R;
R=(*p)->rchild;
(*p)->rchild=R->lchild;
R->lchild=(*p);
*p=R;
}
void LeftBalance(BSTree *T)
{
BSTree L,Lr;
L=(*T)->lchild;
switch(L->BF)
{
//檢查T的左子樹平衡度，并作相應(yīng)的平衡處理
case LH://新節(jié)點(diǎn)插入在T的左孩子的左子樹上，做單右旋處理
(*T)->BF=L->BF=EH;
R_Rotate(T);
break;
case RH://新插入節(jié)點(diǎn)在T的左孩子的右子樹上，做雙旋處理
Lr=L->rchild;
switch(Lr->BF)
{
case LH:
(*T)->BF=RH;
L->BF=EH;
break;
case EH:
(*T)->BF=L->BF=EH;
break;
case RH:
(*T)->BF=EH;
L->BF=LH;
break;
}
Lr->BF=EH;
L_Rotate(&(*T)->lchild);
R_Rotate(T);
}
}
void RightBalance(BSTree *T)
{
BSTree R,Rl;
R=(*T)->rchild;
switch(R->BF)
{
case RH://新節(jié)點(diǎn)插在T的右孩子的右子樹上，要做單左旋處理
(*T)->BF=R->BF=EH;
L_Rotate(T);
break;
case LH://新節(jié)點(diǎn)插在T的右孩子的左子樹上，要做雙旋處理
Rl=R->lchild;
switch(Rl->BF)
{
case LH:
(*T)->BF=EH;
R->BF=RH;
break;
case EH:
(*T)->BF=R->BF=EH;
break;
case RH:
(*T)->BF=LH;
R->BF=EH;
break;
}
Rl->BF=EH;
R_Rotate(&(*T)->rchild);
L_Rotate(T);
}
}
bool InsertAVL(BSTree *T,int e,bool *taller)//變量taller反應(yīng)T長高與否
{
if(!*T)
{
*T=(BSTree)malloc(sizeof(BSTNode));
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->BF=EH;
*taller=true;
}
else
{
if(e==(*T)->data)//不插入
{
*taller=false;
return false;
}
if(e<(*T)->data)
{
if(!InsertAVL(&(*T)->lchild,e,taller))//未插入
return false;
if(*taller)//以插入左子樹，且左子樹變高
{
switch((*T)->BF)
{
case LH://原本左子樹比右子樹高，需要做左平衡處理
LeftBalance(T);
*taller=false;
break;
case EH://原本左右子樹等高，現(xiàn)因左子樹增高而樹增高
(*T)->BF=LH;
*taller=true;
break;
case RH://原本右子樹比左子樹高，現(xiàn)在左右子樹等高
(*T)->BF=EH;
*taller=false;
break;
}
}
}
else
{
//應(yīng)在T的右子樹中搜尋
if(!InsertAVL(&(*T)->rchild,e,taller))
return false;
if(*taller)//插入右子樹，且右子樹長高
{
switch((*T)->BF)
{
case LH://原本左子樹比右子樹高，現(xiàn)在左右子樹等高
(*T)->BF=EH;
*taller=false;
break;
case EH://原本左右子樹等高，現(xiàn)在右子樹變高
(*T)->BF=RH;
*taller=true;
break;
case RH://原本右子樹比左子樹高，現(xiàn)在需做右平衡處理
RightBalance(T);
*taller=false;
break;
}
}
}
}
return true;
}
bool Find(BSTree T,int key)
{
if(!T)
return false;
else if(T->data==key)
return true;
else if(T->data<key)
return Find(T->rchild,key);
else
return Find(T->lchild,key);
}
void Inorder(BSTree T)
{
if(T)
{
printf("%d",T->data);
if(T->lchild||T->rchild)
{
printf("(");
Inorder(T->lchild);
printf(",");
Inorder(T->rchild);
printf(")");
}
}
}
double CalAveLength(BSTree T,int A[],int num)
{
double len=0;
int i;
BSTree rt;
for(i=0;i<num;i++)
{
rt=T;
for(;;)
{
len++;
if (rt->data==A[i]) break;
if(rt->data<A[i])
rt=rt->rchild;
else
rt=rt->lchild;
}
}
return (double)len/num;
}
int main()
{
int i;
int j;//插入數(shù)
int num;
int A[]={3,2,1,4,5,6,7,10,9,8};
BSTree T=NULL;
bool taller;
num=sizeof(A)/sizeof(int);
for(i=0;i<sizeof(A)/sizeof(int);i++)
InsertAVL(&T,A[i],&taller);
Inorder(T);
printf("\n");
printf("插入結(jié)點(diǎn)值：");
scanf("%d",&j);
InsertAVL(&T,j,&taller);
Inorder(T);
printf("\n");
printf("平均查找長度為：%3.1f",CalAveLength(T,A,num));
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define N 100
typedef struct
{
int *data;
int dnum;
}BST;
float length;
void InsertBST(BST T,int i,int key)
{
if(i<1||i>N)
printf("ERROR!\n");
if(T.data[i]==0)
T.data[i]=key;
else if(key<T.data[i])
InsertBST(T,2*i,key);
else InsertBST(T,2*i+1,key);
}
BST CreatBST(int *A,int num)
{
BST T;
int i,j;
T.data=(int *)malloc(N*sizeof(int));
for(j=0;j<N;j++)
T.data[j]=0;
T.dnum=0;
for(i=0;i<num;i++)
{
InsertBST(T,1,A[i]);
++T.dnum;
}
return T;
}
void Inorder(BST T,int i)
{
if(T.data[i])
{
Inorder(T,2*i);
printf("%d ",T.data[i]);
Inorder(T,2*i+1);
}
}
int search(BST T,int key,int i)
{
length++;
if(!T.data[i]) return 0;
else if(key==T.data[i]) return i;
else if(key<T.data[i]) search(T,key,2*i);
else search(T,key,2*i+1);
}
BST DeleteBST(BST T,int key)
{
BST q;
int i;
q.data=(int *)malloc(N*sizeof(int));
for(i=0;i<N;i++)
q.data[i]=0;
q.dnum=0;
for(i=1;i<N&&T.dnum>0;i++)
{
if(T.data[i]==0||T.data[i]==key) continue;
InsertBST(q,1,T.data[i]);
--T.dnum;
++q.dnum;
}
delete T.data;
return q;
}
int main()
{
BST T;
int A[N];
char ch;
int i=0;
int num,j;
printf("輸入L：");
do
{
scanf("%d",&num);
A[i++]=num;
scanf("%c",&ch);
if(ch=='\n') break;
}while(ch!='\n');
T=CreatBST(A,i);
printf("中序遍歷結(jié)果：");
Inorder(T,1);
printf("\n");
length=0;
for(int s=0;s<T.dnum;s++)
search(T,A[s],1);
printf("平均查找長度：");
float f;
f=length/T.dnum;
printf("%3.1f\n",f);
printf("輸入查找元素，若該節(jié)點(diǎn)存在，則刪除該結(jié)點(diǎn)：");
scanf("%d",&num);
j=search(T,num,1);
if(j)
{
T=DeleteBST(T,num);
printf("刪除成功，中序遍歷結(jié)果：");
Inorder(T,1);
i--;
}
else printf("沒有找到該結(jié)點(diǎn)%d",num);
}
總結(jié)
構(gòu)造二叉排序樹。我們對(duì)于給定序列，取其第一個(gè)點(diǎn)為根結(jié)點(diǎn)，然后依次選擇后續(xù)節(jié)點(diǎn)邊比較邊插入。如果比當(dāng)前結(jié)點(diǎn)小，往該節(jié)點(diǎn)左子樹移動(dòng)比較，如果比當(dāng)前結(jié)點(diǎn)大，則往該節(jié)點(diǎn)右子樹移動(dòng)比較。直到到一個(gè)待比較位置為空的位置，就是該節(jié)點(diǎn)的最終位置。
查找操作通過遞歸算法實(shí)現(xiàn)。思路很簡單，僅需要從根節(jié)點(diǎn)開始比較就可以，比當(dāng)前結(jié)點(diǎn)大就找左子樹，小就找右子樹直到找到為止。
刪除操作相對(duì)于前面的查找與插入就復(fù)雜一些了。刪除某元素需要維護(hù)二叉排序樹的形狀。文章來源地址http://www.zghlxwxcb.cn/news/detail-520814.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)課設(shè)（五）二叉排序樹與平衡二叉樹的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![數(shù)據(jù)結(jié)構(gòu)07：查找[C++][平衡二叉排序樹AVL]](https://imgs.yssmx.com/Uploads/2024/02/502021-1.png)
![[數(shù)據(jù)結(jié)構(gòu)] 樹與二叉樹](https://imgs.yssmx.com/Uploads/2024/03/837706-1.png)
