《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 平衡二叉樹(shù)83847》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 平衡二叉樹(shù)83847（7頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 平衡二叉樹(shù).txt看一個(gè)人的的心術(shù)，要看他的眼神；看一個(gè)人的身價(jià)，要看他的對(duì)手；看一個(gè)人的底牌，要看他的朋友。明天是世上增值最快的一塊土地，因它充滿了希望。/*
數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 平衡二叉樹(shù)
P236
編譯環(huán)境：Dev-C++ 4.9.9.2
日期：2011年2月15日
*/
#include
#include
#define LH +1 // 左高
#define EH 0 // 等高
#define RH -1 // 右高
#define N 5 // 數(shù)據(jù)元素個(gè)數(shù)
typ
2、edef char KeyType; // 設(shè)關(guān)鍵字域?yàn)樽址?
typedef struct
{
KeyType key;
int order;
}ElemType; // 數(shù)據(jù)元素類型
// 平衡二叉樹(shù)的類型
typedef struct BSTNode
{
ElemType data;
// bf結(jié)點(diǎn)的平衡因子,只能夠取0，-1，1，它是左子樹(shù)的深度減去
// 右子樹(shù)的深度得到的
int bf;
struct BSTNode *lchild,*rchild; // 左、右孩子指針
}BSTNode,*BSTree;
// 構(gòu)
3、造一個(gè)空的動(dòng)態(tài)查找表DT
int InitDSTable(BSTree *DT)
{
*DT=NULL;
return 1;
}
// 銷毀動(dòng)態(tài)查找表DT
void DestroyDSTable(BSTree *DT)
{
if(*DT) // 非空樹(shù)
{
if((*DT)->lchild) // 有左孩子
DestroyDSTable(&(*DT)->lchild); // 銷毀左孩子子樹(shù)
if((*DT)->rchild) // 有右孩子
DestroyDSTable(&(*DT)->rchild); // 銷毀右孩
4、子子樹(shù)
free(*DT); // 釋放根結(jié)點(diǎn)
*DT=NULL; // 空指針賦0
}
}
// 算法9.5(a)
// 在根指針T所指二叉排序樹(shù)中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素，
// 若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針,否則返回空指針。
BSTree SearchBST(BSTree T,KeyType key)
{
if((!T)|| (key == T->data.key))
return T; // 查找結(jié)束
else if(key < T->data.key) // 在左子樹(shù)中繼續(xù)查找
retur
5、n SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key); // 在右子樹(shù)中繼續(xù)查找
}
// 算法9.9 P236
// 對(duì)以*p為根的二叉排序樹(shù)作右旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)
// 處理之前的左子樹(shù)的根結(jié)點(diǎn)。
void R_Rotate(BSTree *p)
{
BSTree lc;
lc=(*p)->lchild; // lc指向p的左子樹(shù)根結(jié)點(diǎn)
(*p)->lchild=lc->rchild; // lc的右子樹(shù)掛接為p的左子樹(shù)
lc->rchil
6、d=*p;
*p=lc; // p指向新的根結(jié)點(diǎn)
}
// 算法9.10 P236
// 對(duì)以*p為根的二叉排序樹(shù)作左旋處理，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)
// 處理之前的右子樹(shù)的根結(jié)點(diǎn)。
void L_Rotate(BSTree *p)
{
BSTree rc;
rc=(*p)->rchild; // rc指向p的右子樹(shù)根結(jié)點(diǎn)
(*p)->rchild=rc->lchild; // rc的左子樹(shù)掛接為p的右子樹(shù)
rc->lchild=*p;
*p=rc; // p指向新的根結(jié)點(diǎn)
}
// 算法9.12 P238
// 對(duì)以
7、指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，
// 指針T指向新的根結(jié)點(diǎn)。
void LeftBalance(BSTree *T)
{
BSTree lc,rd;
lc=(*T)->lchild; // lc指向*T的左子樹(shù)根結(jié)點(diǎn)
switch(lc->bf)
{ // 檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理
case LH: // 新結(jié)點(diǎn)插入在*T的左孩子的左子樹(shù)上，要作單右旋處理
(*T)->bf=lc->bf=EH;
R_Rotate(T);
break;
case RH: // 新結(jié)點(diǎn)插入在*T的左孩子的右子樹(shù)
8、上，要作雙旋處理
rd=lc->rchild; // rd指向*T的左孩子的右子樹(shù)根
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;
}
rd->bf=EH;
L_Rotate(&(*T)->lchild); // 對(duì)*T的左子樹(shù)作左旋平衡處
9、理
R_Rotate(T); // 對(duì)*T作右旋平衡處理
}
}
// 對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，
// 指針T指向新的根結(jié)點(diǎn)
void RightBalance(BSTree *T)
{
BSTree rc,rd;
rc=(*T)->rchild; // rc指向*T的右子樹(shù)根結(jié)點(diǎn)
switch(rc->bf)
{ // 檢查*T的右子樹(shù)的平衡度，并作相應(yīng)平衡處理
case RH: // 新結(jié)點(diǎn)插入在*T的右孩子的右子樹(shù)上，要作單左旋處理
(*T)->bf=rc->bf=EH;
L_Rot
10、ate(T);
break;
case LH: // 新結(jié)點(diǎn)插入在*T的右孩子的左子樹(shù)上，要作雙旋處理
rd=rc->lchild; // rd指向*T的右孩子的左子樹(shù)根
switch(rd->bf)
{ // 修改*T及其右孩子的平衡因子
case RH: (*T)->bf=LH;
rc->bf=EH;
break;
case EH: (*T)->bf=rc->bf=EH;
break;
case LH: (*T)->bf=EH;
rc->bf=RH;
}
rd->bf=EH;
R_Rota
11、te(&(*T)->rchild); // 對(duì)*T的右子樹(shù)作右旋平衡處理
L_Rotate(T); // 對(duì)*T作左旋平衡處理
}
}
// 算法9.11
// 若在平衡的二叉排序樹(shù)T中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)
// 數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否則返回0。若因插入而使二叉排序樹(shù)
// 失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長(zhǎng)高與否。
int InsertAVL(BSTree *T,ElemType e,int *taller)
{
if(!*T)
{ // 插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為1
12、*T=(BSTree)malloc(sizeof(BSTNode));
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->bf=EH;
*taller=1;
}
else
{
if(e.key == (*T)->data.key)
{ // 樹(shù)中已存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入
*taller=0;
return 0;
}
if(e.key < (*T)->data.key)
{ // 應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索
if(!InsertAV
13、L(&(*T)->lchild,e,taller)) // 未插入
return 0;
if(*taller)
// 已插入到*T的左子樹(shù)中且左子樹(shù)“長(zhǎng)高”
switch((*T)->bf) // 檢查*T的平衡度
{
case LH:
// 原本左子樹(shù)比右子樹(shù)高，需要作左平衡處理
LeftBalance(T);
*taller=0; //標(biāo)志沒(méi)長(zhǎng)高
break;
case EH:
// 原本左、右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高
(*T)-
14、>bf=LH;
*taller=1; //標(biāo)志長(zhǎng)高
break;
case RH:
// 原本右子樹(shù)比左子樹(shù)高，現(xiàn)左、右子樹(shù)等高
(*T)->bf=EH;
*taller=0; //標(biāo)志沒(méi)長(zhǎng)高
}
}
else
{
// 應(yīng)繼續(xù)在*T的右子樹(shù)中進(jìn)行搜索
if(!InsertAVL(&(*T)->rchild,e,taller)) // 未插入
return 0;
if(*taller) // 已插入到T的右子樹(shù)且右子樹(shù)“長(zhǎng)高”
switch((*T
15、)->bf) // 檢查T的平衡度
{
case LH:
(*T)->bf=EH; // 原本左子樹(shù)比右子樹(shù)高，現(xiàn)左、右子樹(shù)等高
*taller=0;
break;
case EH: // 原本左、右子樹(shù)等高，現(xiàn)因右子樹(shù)增高而使樹(shù)增高
(*T)->bf=RH;
*taller=1;
break;
case RH: // 原本右子樹(shù)比左子樹(shù)高，需要作右平衡處理
RightBalance(T);
*taller
16、=0;
}
}
}
return 1;
}
// 按關(guān)鍵字的順序?qū)T的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit()一次
void TraverseDSTable(BSTree DT,void(*Visit)(ElemType))
{
if(DT)
{
TraverseDSTable(DT->lchild,Visit); // 先中序遍歷左子樹(shù)
Visit(DT->data); // 再訪問(wèn)根結(jié)點(diǎn)
TraverseDSTable(DT->rchild,Visit); // 最后中序遍歷右子樹(shù)
}
}
void print(E
17、lemType c)
{
printf("(%d,%d)",c.key,c.order);
}
int main()
{
BSTree dt,p;
int k;
int i;
KeyType j;
ElemType r[N]={
{13,1},{24,2},{37,3},{90,4},{53,5}
}; // (以教科書P234圖9.12為例)
InitDSTable(&dt); // 初始化空樹(shù)
for(i=0;i
18、Table(dt,print); // 按關(guān)鍵字順序遍歷二叉樹(shù)
printf("\n請(qǐng)輸入待查找的關(guān)鍵字: ");
scanf("%d",&j);
p=SearchBST(dt,j); // 查找給定關(guān)鍵字的記錄
if(p)
print(p->data);
else
printf("表中不存在此值");
printf("\n");
DestroyDSTable(&dt);
system("pause");
return 0;
}
/*
輸出效果：
(13,1)(24,2)(37,3)(53,5)(90,4)
請(qǐng)輸入待查找的關(guān)鍵字: 53
(53,5)
請(qǐng)按任意鍵繼續(xù). . .
*/
數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 平衡二叉樹(shù)83847
