C語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)平衡二叉樹(shù)實(shí)例詳解
更新時(shí)間：2017年06月21日 09:47:51 投稿：lqh
這篇文章主要介紹了C語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)平衡二叉樹(shù)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
數(shù)據(jù)結(jié)構(gòu)平衡二叉樹(shù)
參考代碼如下：
/*
名稱：平衡二叉樹(shù)
語(yǔ)言：數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版
編譯環(huán)境：VC++ 6.0
日期： 2014-3-26
*/
#include <stdio.h>
#include <malloc.h>
#include <windows.h>
#define LH +1 // 左高
#define EH 0 // 等高
#define RH -1 // 右高
#define N 5 // 數(shù)據(jù)元素個(gè)數(shù)
typedef 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)造一個(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); // 銷毀右孩子子樹(shù)
free(*DT); // 釋放根結(jié)點(diǎn)
*DT=NULL; // 空指針賦0
}
}
// 在根指針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ù)查找
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key); // 在右子樹(shù)中繼續(xù)查找
}
// 對(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->rchild=*p;
*p=lc; // p指向新的根結(jié)點(diǎn)
}
// 對(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)
}
// 對(duì)以指針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ù)上，要作雙旋處理
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ù)作左旋平衡處理
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_Rotate(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_Rotate(&(*T)->rchild); // 對(duì)*T的右子樹(shù)作右旋平衡處理
L_Rotate(T); // 對(duì)*T作左旋平衡處理
}
}
// 若在平衡的二叉排序樹(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
*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(!InsertAVL(&(*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)->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)->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=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(ElemType 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<N;i++)
InsertAVL(&dt,r[i],&k); // 建平衡二叉樹(shù)
TraverseDSTable(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ù). . .
*/
運(yùn)行結(jié)果如下：
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)三子棋小游戲的示例代碼
這篇文章主要介紹了如何通過(guò)C語(yǔ)言實(shí)現(xiàn)三子棋小游戲，三子棋小游戲的實(shí)現(xiàn)主要依賴于循環(huán)語(yǔ)句、函數(shù)和數(shù)組，感興趣的小伙伴可以嘗試一下2022-10-10
C++使用cjson操作Json格式文件(創(chuàng)建、插入、解析、修改、刪除)
本文主要介紹了C++使用cjson操作Json格式文件(創(chuàng)建、插入、解析、修改、刪除),文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
迭代器是一種檢查容器內(nèi)元素并遍歷元素的數(shù)據(jù)類型。迭代器是一個(gè)變量，提供對(duì)一個(gè)容器中的對(duì)象的（間接）訪問(wèn)方法，并且定義了容器中對(duì)象的范圍。迭代器可以指向容器中的某個(gè)元素，通過(guò)迭代器就可以對(duì)非數(shù)組（存儲(chǔ)空間不連續(xù)）的數(shù)據(jù)結(jié)構(gòu)進(jìn)行遍歷2022-10-10
Map是字典一樣的數(shù)據(jù)結(jié)構(gòu),它是(鍵,值)對(duì)的關(guān)聯(lián)數(shù)組,其中每個(gè)唯一鍵僅與單個(gè)值相關(guān)聯(lián),下面這篇文章主要給大家介紹了關(guān)于C++中map 字典的基本使用的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-09-09
繼承是C++面向?qū)ο缶幊讨械囊婚T。繼承是子類繼承父類的特征和行為，或者是繼承父類得方法，使的子類具有父類得的特性和行為。重寫是子類對(duì)父類的允許訪問(wèn)的方法實(shí)行的過(guò)程進(jìn)行重新編寫，返回值和形參都不能改變。就是對(duì)原本的父類進(jìn)行重新編寫，但是外部接口不能被重寫2022-05-05
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言版實(shí)現(xiàn)鏈隊(duì)列，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-07-07
使用c++實(shí)現(xiàn)OpenCV繪制圓端矩形
這篇文章主要介紹了使用c++實(shí)現(xiàn)OpenCV繪制圓端矩形，其中著重的講解了OpenCV使用過(guò)程中需要注意的一些小細(xì)節(jié)，避免浪費(fèi)大家在開(kāi)發(fā)過(guò)程中浪費(fèi)多余的時(shí)間2021-08-08
C++中高性能內(nèi)存池的實(shí)現(xiàn)詳解
在 C/C++ 中，內(nèi)存管理是一個(gè)非常棘手的問(wèn)題，我們?cè)诰帉懸粋€(gè)程序的時(shí)候幾乎不可避免的要遇到內(nèi)存的分配邏輯。本文將通過(guò)C++實(shí)現(xiàn)高性能內(nèi)存池，感興趣的可以了解一下2022-10-10
C++ 面向?qū)ο蟪绦蛟O(shè)計(jì)--內(nèi)存分區(qū)詳解
這篇文章主要介紹了剖析C++的面向?qū)ο缶幊趟枷?C++的面向?qū)ο筇匦允瞧鋵?duì)C語(yǔ)言的重要拓展之處,需要的朋友可以參考下，希望能夠給你帶來(lái)幫助2021-08-08
C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07