C語言之平衡二叉樹怎么實現

本文小編為大家詳細介紹“C語言之平衡二叉樹怎么實現”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C語言之平衡二叉樹怎么實現”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

什么是平衡二叉樹

平衡二叉樹是具有平衡屬性的有序二叉樹，所謂的平衡即當前樹的左右子樹高度差的絕對值不超過1。因為平衡二叉樹是由蘇聯數學家Adelson-Velskii和Landis提出，所以又稱為AVL樹。

平衡二叉樹的基本特點

• 是特殊的有序二叉樹

• 左右子樹高度差的絕對值不超過1

• 左右子樹仍然是平衡二叉樹

為什么會出現平衡二叉樹

在學習平衡二叉樹之前必定已經學過有序二叉樹，有序二叉樹的結構特點就是將數據有序的排好，查找起來快，但是有序二叉樹有一個缺點，就是當節點呈現的狀態是一邊倒，那查找數據的時候就沒有發揮出二叉樹折半查找的優勢了，這個時候是線性的查找（類似于鏈表的查找）。平衡二叉樹就是解決有序二叉樹一邊倒的問題。如果有序二叉樹是平衡的，那么查找數據就很快。時間復雜度為O ( l o g n ) O(logn)O(logn)。這樣就充分發揮了二叉樹的優勢。

二叉樹四種不平衡的情況

當樹的左右子樹高度差的絕對值大于1的時候就需要進行旋轉操作，將不平衡的樹變成平衡的樹。以下是會出現的四種不平衡的情況。

• 左左不平衡

• 右右不平衡

• 左右不平衡

• 右左不平衡

左左不平衡旋轉成平衡狀態：

右右不平衡旋轉成平衡狀態：

左右不平衡旋轉成平衡狀態：

右左不平衡旋轉成平衡狀態：

上面是圖解這四種不平衡狀態旋轉成平衡狀態的情況。

C語言實現平衡二叉樹

平衡二叉樹的結構體描述：

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

初始化函數:

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;
}

輔助宏函數：

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

使用宏函數的好處是運行過程中不需要進行函數壓棧的操作，效率快一點。

前序遍歷平衡二叉樹：

//前序打印
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);
}

使用前序遍歷能更好地看出節點的高度，更方便還原平衡二叉樹。

四種不平衡狀態旋轉的算法實現：

算法核心思想：找到新根的位置，然后進行對應的調整，最后返回新根的地址，這樣就實現了旋轉的操作，因為旋轉后節點的高度改變了，所以在返回之前先調整一下節點的高度。

例如：左左不平衡進行旋轉操作

因為是左左不平衡，所以新根的位置是當前根的左子樹，那就使用一個指針（newRoot）去接收當前根的左子樹，然后使勁將當前根拉下來，讓新根代替當前根的位置，那就必須將當前根的LChild指向newRoot的右子樹（因為newRoot不一定是空的所以不能直接讓curRoot→LChild指向空）。最后就是將newRoot→RChild指向curRoot這樣就把位置調整好了。在返回newRoot之前把curRoot和newRoot的高度調整一下。保持樹的準確性。

其他的不平衡情況也是類似的操作。

//出現不平衡的情況
//左左不平衡
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);
}

平衡二叉樹的插入操作：

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

• 當前節點是空的

• 要插入進來的數據比當前節點的數據小

• 要插入進來的數據比當前節點的數據大

• 要插入進來的數據和當前節點的數據一樣大

情況一的解決方案：直接申請一個節點內存。

情況二的解決方案：遞歸往左邊跑，然后跑到對應的位置就申請內存，插入完成后判斷需不需要調整。

情況三的解決方案：遞歸往右邊跑，然后跑到對應的位置就申請內存，插入完成后判斷需不需要調整。

情況四的解決方案：因為我們做的是一棵沒有重復數據的平衡二叉樹所以遇到這種情況的時候不進行插入操作。當然如果做的是一棵可以有重復數據的平衡二叉樹，那遇到這種情況的時候可以個人的想法放左邊放右邊都可以。

源代碼：

//插入數據
Node *insertNode(Node *curRoot, Ty data)
{
	//插入分有四個大情況
	if (curRoot == NULL)			  //當前節點是空的
		curRoot = creatAVLTree(data); //如果是空就直接創建一個新的節點
	else if (data < curRoot->data)	  //要插入的數據比當前節點的數據小
	{
		//往左邊跑
		curRoot->LChild = insertNode(curRoot->LChild, data);
		//插入完成之后，判斷需不需要調整樹
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			//因為插入的位置在左邊，所以插入完成之后，左子樹的高度大于等于右子樹高度
			curRoot = data < curRoot->LChild->data ? LL_Rotation(curRoot) : LR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要插入的數據比當前節點的數據大
	{
		//往右邊跑
		curRoot->RChild = insertNode(curRoot->RChild, data);
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			//因為插入的位置在右邊，所以插入完成之后，右子樹的高度大于等于左子樹高度
			curRoot = data > curRoot->RChild->data ? RR_Rotation(curRoot) : RL_Rotation(curRoot);
	}
	else //要插入的數據和當前節點的數據一樣大
		printf("無法插入數據\n");
	//獲取新高度
	curRoot->height = GET_NEW_HEIGHT(curRoot);
	return curRoot; //插入完成之后返回當前節點的指針
}

平衡二叉樹的刪除操作：

刪除操作也是要考慮四個大情況：

• 當前節點是空的

• 要刪除的數據比當前數據小

• 要刪除的數據比當前數據大

• 要刪除的數據和當前數據一樣大

情況一的解決方案：沒有刪除的必要了，結束掉函數

情況二的解決方案：往左邊遞歸找到對應位置，然后進行刪除操作

情況三的解決方案：往右邊遞歸找到對應位置，然后進行刪除操作

情況四的解決方案：針對這個情況又要分為兩個小情況

• 當前節點的左子樹和右子樹都存在

• 當前節點的左右子樹至多有一個存在

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

源代碼：

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

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

//刪除數據
Node *deleteNode(Node *curRoot, Ty data)
{
	//刪除數據有四個大情況
	if (curRoot == NULL)	  //當前節點是空的
		return NULL;		  //刪除了個寂寞直接結束掉整個函數
	if (data < curRoot->data) //要刪除的數據比當前節點的數據小
	{
		//往左邊跑
		curRoot->LChild = deleteNode(curRoot->LChild, data);
		//獲取新高度
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		//判斷需不需要調整
		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) //要刪除的數據比當前節點的數據大
	{
		//往右邊跑
		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
	{ //要刪除的數據和當前節點的數據一樣大
		//針對于curRoot這個節點做刪除操作
		//主要有兩個主要的情況
		if (curRoot->LChild && curRoot->RChild) // curRoot有左子樹和右子樹
		{
			//先判斷左右子樹的高度，將高度比較高的子樹的節點拿到上面來
			if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
			{ //左子樹的高度比右子樹的高度高
				//找到左子樹的最大節點
				Node *max = maxNode(curRoot->LChild);
				//找到之后就將max的數據替換curRoot的數據
				curRoot->data = max->data;
				//賦值完成之后繼續遞歸，然后釋放掉max對應的節點，不能直接在這里釋放，因為要調整樹的高度
				curRoot->LChild = deleteNode(curRoot->LChild, max->data);
			}
			else
			{ //左子樹的高度小于等于右子樹的高度
				//找到右子樹的最小節點
				Node *min = minNode(curRoot->RChild);
				curRoot->data = min->data;
				curRoot->RChild = deleteNode(curRoot->RChild, min->data);
			}
		}
		else //上一種情況的否定，即curRoot沒有子樹或者只有一邊
		{
			//釋放內存
			Node *temp = curRoot;
			// curRoot拿到存在的子樹
			curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
			free(temp);
		}
	}

	return curRoot; //刪除完成之后就返回當前節點
}

主函數測試：

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

運行結果：

刪除前和刪除后的平衡二叉樹：

讀到這里，這篇“C語言之平衡二叉樹怎么實現”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。