C語(yǔ)言之平衡二叉樹(shù)怎么實(shí)現(xiàn)

本文小編為大家詳細(xì)介紹“C語(yǔ)言之平衡二叉樹(shù)怎么實(shí)現(xiàn)”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“C語(yǔ)言之平衡二叉樹(shù)怎么實(shí)現(xiàn)”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。

什么是平衡二叉樹(shù)

平衡二叉樹(shù)是具有平衡屬性的有序二叉樹(shù)，所謂的平衡即當(dāng)前樹(shù)的左右子樹(shù)高度差的絕對(duì)值不超過(guò)1。因?yàn)槠胶舛鏄?shù)是由蘇聯(lián)數(shù)學(xué)家Adelson-Velskii和Landis提出，所以又稱為AVL樹(shù)。

平衡二叉樹(shù)的基本特點(diǎn)

• 是特殊的有序二叉樹(shù)

• 左右子樹(shù)高度差的絕對(duì)值不超過(guò)1

• 左右子樹(shù)仍然是平衡二叉樹(shù)

為什么會(huì)出現(xiàn)平衡二叉樹(shù)

在學(xué)習(xí)平衡二叉樹(shù)之前必定已經(jīng)學(xué)過(guò)有序二叉樹(shù)，有序二叉樹(shù)的結(jié)構(gòu)特點(diǎn)就是將數(shù)據(jù)有序的排好，查找起來(lái)快，但是有序二叉樹(shù)有一個(gè)缺點(diǎn)，就是當(dāng)節(jié)點(diǎn)呈現(xiàn)的狀態(tài)是一邊倒，那查找數(shù)據(jù)的時(shí)候就沒(méi)有發(fā)揮出二叉樹(shù)折半查找的優(yōu)勢(shì)了，這個(gè)時(shí)候是線性的查找（類(lèi)似于鏈表的查找）。平衡二叉樹(shù)就是解決有序二叉樹(shù)一邊倒的問(wèn)題。如果有序二叉樹(shù)是平衡的，那么查找數(shù)據(jù)就很快。時(shí)間復(fù)雜度為O ( l o g n ) O(logn)O(logn)。這樣就充分發(fā)揮了二叉樹(shù)的優(yōu)勢(shì)。

二叉樹(shù)四種不平衡的情況

當(dāng)樹(shù)的左右子樹(shù)高度差的絕對(duì)值大于1的時(shí)候就需要進(jìn)行旋轉(zhuǎn)操作，將不平衡的樹(shù)變成平衡的樹(shù)。以下是會(huì)出現(xiàn)的四種不平衡的情況。

• 左左不平衡

• 右右不平衡

• 左右不平衡

• 右左不平衡

左左不平衡旋轉(zhuǎn)成平衡狀態(tài)：

右右不平衡旋轉(zhuǎn)成平衡狀態(tài)：

左右不平衡旋轉(zhuǎn)成平衡狀態(tài)：

右左不平衡旋轉(zhuǎn)成平衡狀態(tài)：

上面是圖解這四種不平衡狀態(tài)旋轉(zhuǎn)成平衡狀態(tài)的情況。

C語(yǔ)言實(shí)現(xiàn)平衡二叉樹(shù)

平衡二叉樹(shù)的結(jié)構(gòu)體描述：

#define Ty int  //以整型數(shù)據(jù)為例
typedef struct Node
{
	Ty data;             //數(shù)據(jù)
	int height;          //高度
	struct Node* LChild; //左子樹(shù)
	struct Node* RChild; //右子樹(shù)
}Node,AVLTree;

初始化函數(shù):

AVLTree* creatAVLTree(Ty data)
{
    AVLTree* tree = (AVLTree*)malloc(sizeof(AVLTree));
    assert(tree);
    tree->data = data;
    tree->height = 0;
    tree->LChild = NULL;
    tree->RChild = NULL;
    return tree;
}

輔助宏函數(shù)：

//輔助函數(shù)
#define HEIGHT(x) ((x==NULL)?(-1):(x->height))
#define MAX(a,b)  ((a>b)?(a):(b))
//獲取樹(shù)的新高度
#define GET_NEW_HEIGHT(x) (MAX(HEIGHT(x->LChild),HEIGHT(x->RChild)) + 1)

使用宏函數(shù)的好處是運(yùn)行過(guò)程中不需要進(jìn)行函數(shù)壓棧的操作，效率快一點(diǎn)。

前序遍歷平衡二叉樹(shù)：

//前序打印
void show_pre(AVLTree* root)
{
	if(root==NULL)
		return;
	printf("data:%d\theight:%d\n",root->data,root->height);
	show_pre(root->LChild);
	show_pre(root->RChild);
}

使用前序遍歷能更好地看出節(jié)點(diǎn)的高度，更方便還原平衡二叉樹(shù)。

四種不平衡狀態(tài)旋轉(zhuǎn)的算法實(shí)現(xiàn)：

算法核心思想：找到新根的位置，然后進(jìn)行對(duì)應(yīng)的調(diào)整，最后返回新根的地址，這樣就實(shí)現(xiàn)了旋轉(zhuǎn)的操作，因?yàn)樾D(zhuǎn)后節(jié)點(diǎn)的高度改變了，所以在返回之前先調(diào)整一下節(jié)點(diǎn)的高度。

例如：左左不平衡進(jìn)行旋轉(zhuǎn)操作

因?yàn)槭亲笞蟛黄胶?，所以新根的位置是?dāng)前根的左子樹(shù)，那就使用一個(gè)指針（newRoot）去接收當(dāng)前根的左子樹(shù)，然后使勁將當(dāng)前根拉下來(lái)，讓新根代替當(dāng)前根的位置，那就必須將當(dāng)前根的LChild指向newRoot的右子樹(shù)（因?yàn)閚ewRoot不一定是空的所以不能直接讓curRoot→LChild指向空）。最后就是將newRoot→RChild指向curRoot這樣就把位置調(diào)整好了。在返回newRoot之前把curRoot和newRoot的高度調(diào)整一下。保持樹(shù)的準(zhǔn)確性。

其他的不平衡情況也是類(lèi)似的操作。

//出現(xiàn)不平衡的情況
//左左不平衡
Node *LL_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->LChild;
	curRoot->LChild = newRoot->RChild;
	newRoot->RChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}

//右右不平衡
Node *RR_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->RChild;
	curRoot->RChild = newRoot->LChild;
	newRoot->LChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}
//左右不平衡
Node *LR_Rotation(Node *curRoot)
{
	curRoot->LChild = RR_Rotation(curRoot->LChild);
	return LL_Rotation(curRoot);
}
//右左不平衡
Node *RL_Rotation(Node *curRoot)
{
	curRoot->RChild = LL_Rotation(curRoot->RChild);
	return RR_Rotation(curRoot);
}

平衡二叉樹(shù)的插入操作：

插入操作需要考慮到四種情況：

• 當(dāng)前節(jié)點(diǎn)是空的

• 要插入進(jìn)來(lái)的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)小

• 要插入進(jìn)來(lái)的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大

• 要插入進(jìn)來(lái)的數(shù)據(jù)和當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)一樣大

情況一的解決方案：直接申請(qǐng)一個(gè)節(jié)點(diǎn)內(nèi)存。

情況二的解決方案：遞歸往左邊跑，然后跑到對(duì)應(yīng)的位置就申請(qǐng)內(nèi)存，插入完成后判斷需不需要調(diào)整。

情況三的解決方案：遞歸往右邊跑，然后跑到對(duì)應(yīng)的位置就申請(qǐng)內(nèi)存，插入完成后判斷需不需要調(diào)整。

情況四的解決方案：因?yàn)槲覀冏龅氖且豢脹](méi)有重復(fù)數(shù)據(jù)的平衡二叉樹(shù)所以遇到這種情況的時(shí)候不進(jìn)行插入操作。當(dāng)然如果做的是一棵可以有重復(fù)數(shù)據(jù)的平衡二叉樹(shù)，那遇到這種情況的時(shí)候可以個(gè)人的想法放左邊放右邊都可以。

源代碼：

//插入數(shù)據(jù)
Node *insertNode(Node *curRoot, Ty data)
{
	//插入分有四個(gè)大情況
	if (curRoot == NULL)			  //當(dāng)前節(jié)點(diǎn)是空的
		curRoot = creatAVLTree(data); //如果是空就直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)
	else if (data < curRoot->data)	  //要插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)小
	{
		//往左邊跑
		curRoot->LChild = insertNode(curRoot->LChild, data);
		//插入完成之后，判斷需不需要調(diào)整樹(shù)
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			//因?yàn)椴迦氲奈恢迷谧筮?，所以插入完成之后，左子?shù)的高度大于等于右子樹(shù)高度
			curRoot = data < curRoot->LChild->data ? LL_Rotation(curRoot) : LR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大
	{
		//往右邊跑
		curRoot->RChild = insertNode(curRoot->RChild, data);
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			//因?yàn)椴迦氲奈恢迷谟疫?，所以插入完成之后，右子?shù)的高度大于等于左子樹(shù)高度
			curRoot = data > curRoot->RChild->data ? RR_Rotation(curRoot) : RL_Rotation(curRoot);
	}
	else //要插入的數(shù)據(jù)和當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)一樣大
		printf("無(wú)法插入數(shù)據(jù)\n");
	//獲取新高度
	curRoot->height = GET_NEW_HEIGHT(curRoot);
	return curRoot; //插入完成之后返回當(dāng)前節(jié)點(diǎn)的指針
}

平衡二叉樹(shù)的刪除操作：

刪除操作也是要考慮四個(gè)大情況：

• 當(dāng)前節(jié)點(diǎn)是空的

• 要?jiǎng)h除的數(shù)據(jù)比當(dāng)前數(shù)據(jù)小

• 要?jiǎng)h除的數(shù)據(jù)比當(dāng)前數(shù)據(jù)大

• 要?jiǎng)h除的數(shù)據(jù)和當(dāng)前數(shù)據(jù)一樣大

情況一的解決方案：沒(méi)有刪除的必要了，結(jié)束掉函數(shù)

情況二的解決方案：往左邊遞歸找到對(duì)應(yīng)位置，然后進(jìn)行刪除操作

情況三的解決方案：往右邊遞歸找到對(duì)應(yīng)位置，然后進(jìn)行刪除操作

情況四的解決方案：針對(duì)這個(gè)情況又要分為兩個(gè)小情況

• 當(dāng)前節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都存在

• 當(dāng)前節(jié)點(diǎn)的左右子樹(shù)至多有一個(gè)存在

具體解決方案看代碼和注釋

源代碼：

//查找節(jié)點(diǎn)
//找最大節(jié)點(diǎn)
Node *maxNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	//往右邊找
	while (curRoot->RChild)
		curRoot = curRoot->RChild;
	return curRoot;
}

//找最小節(jié)點(diǎn)
Node *minNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	while (curRoot->LChild)
		curRoot = curRoot->LChild;
	return curRoot;
}

//刪除數(shù)據(jù)
Node *deleteNode(Node *curRoot, Ty data)
{
	//刪除數(shù)據(jù)有四個(gè)大情況
	if (curRoot == NULL)	  //當(dāng)前節(jié)點(diǎn)是空的
		return NULL;		  //刪除了個(gè)寂寞直接結(jié)束掉整個(gè)函數(shù)
	if (data < curRoot->data) //要?jiǎng)h除的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)小
	{
		//往左邊跑
		curRoot->LChild = deleteNode(curRoot->LChild, data);
		//獲取新高度
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		//判斷需不需要調(diào)整
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			curRoot = HEIGHT(curRoot->RChild->LChild) > HEIGHT(curRoot->RChild->RChild) ? RL_Rotation(curRoot) : RR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要?jiǎng)h除的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大
	{
		//往右邊跑
		curRoot->RChild = deleteNode(curRoot->RChild, data);
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			curRoot = HEIGHT(curRoot->LChild->RChild) > HEIGHT(curRoot->LChild->LChild) ? LR_Rotation(curRoot) : LL_Rotation(curRoot);
	}
	else
	{ //要?jiǎng)h除的數(shù)據(jù)和當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)一樣大
		//針對(duì)于curRoot這個(gè)節(jié)點(diǎn)做刪除操作
		//主要有兩個(gè)主要的情況
		if (curRoot->LChild && curRoot->RChild) // curRoot有左子樹(shù)和右子樹(shù)
		{
			//先判斷左右子樹(shù)的高度，將高度比較高的子樹(shù)的節(jié)點(diǎn)拿到上面來(lái)
			if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
			{ //左子樹(shù)的高度比右子樹(shù)的高度高
				//找到左子樹(shù)的最大節(jié)點(diǎn)
				Node *max = maxNode(curRoot->LChild);
				//找到之后就將max的數(shù)據(jù)替換curRoot的數(shù)據(jù)
				curRoot->data = max->data;
				//賦值完成之后繼續(xù)遞歸，然后釋放掉max對(duì)應(yīng)的節(jié)點(diǎn)，不能直接在這里釋放，因?yàn)橐{(diào)整樹(shù)的高度
				curRoot->LChild = deleteNode(curRoot->LChild, max->data);
			}
			else
			{ //左子樹(shù)的高度小于等于右子樹(shù)的高度
				//找到右子樹(shù)的最小節(jié)點(diǎn)
				Node *min = minNode(curRoot->RChild);
				curRoot->data = min->data;
				curRoot->RChild = deleteNode(curRoot->RChild, min->data);
			}
		}
		else //上一種情況的否定，即curRoot沒(méi)有子樹(shù)或者只有一邊
		{
			//釋放內(nèi)存
			Node *temp = curRoot;
			// curRoot拿到存在的子樹(shù)
			curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
			free(temp);
		}
	}

	return curRoot; //刪除完成之后就返回當(dāng)前節(jié)點(diǎn)
}

主函數(shù)測(cè)試：

int main()
{
	AVLTree *tree = NULL;
	for (int i = 1; i < 10; i++)
		tree = insertNode(tree, i);
	show_pre(tree); //前序打印樹(shù)
	printf("----------------------------\n");
	//刪除6這個(gè)節(jié)點(diǎn)
	tree = deleteNode(tree, 6);
	show_pre(tree);
	printf("程序結(jié)束\n");
	return 0;
}

運(yùn)行結(jié)果：

刪除前和刪除后的平衡二叉樹(shù)：

讀到這里，這篇“C語(yǔ)言之平衡二叉樹(shù)怎么實(shí)現(xiàn)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。