數據結構學習筆記＜5＞二叉搜索樹與平衡二叉樹

一、二叉搜尋樹#

1. 二叉搜尋樹是什麼#

二叉搜尋樹（BST，Binary Search Tree)，又稱二叉排序樹或二叉查找樹，是一棵二叉樹，可以為空，當不為空時滿足以下性質：

非空左子樹的所有鍵值小於其根節點的鍵值
非空右子樹的所有鍵值大於其根節點的鍵值
左、右子樹都為二叉搜尋樹

2. 二叉搜尋樹的操作函數#

(1) 二叉搜尋樹的查找操作 Find#

要查找的值為 X

從根節點開始查找，若樹為空，則返回 NULL
若搜尋樹非空，則將X 與根節點的鍵值進行比較並進行以下處理
1. 若X 小於根節點鍵值，則在左子樹中搜尋
2. 若X 大於根節點鍵值，則在右子樹中搜尋
3. 若 X 與根節點鍵值相等，則搜尋完成，返回指向該節點的指針

尾遞歸實現#

Position Find(ElementType X, BinTree BST) {
	if( !BST ) return NULL;//查找失敗
	if( X > BST->Data )
		return Find(X, BST->Right);//操作1
	else if (X < BST->Data) 
		return Find(X, BST->Left); //操作2
	else 
		return BST; //操作3 查找成功
}

迭代函數實現#

Position Find(ElementType X, BinTree BST) {
	while(BST) {
		if (X > BST->Data)
			BST = BST->Right;//操作1
		else if (X < BST->Data)
			BST = BST->Left;//操作2
		else 
			return BST;//操作3 查找成功
	}
	return NULL;//查找失敗
}

(2) 查找最大元素和最小元素#

最大元素一定是在樹的最右分支的端節點上
最小元素一定是在樹的最左分支的端節點上

查找最大元素#

遞歸函數

Position FindMin(BinTree BST) {
	if (!BST ) return NULL;//空樹，返回NULL
	else if ( !BST->Left )
		return BST;	//找到了最左葉節點
	else 
		return FindMin(BST->Left);//沿左分支繼續查找
}

迭代函數

Position FindMin(BinTree BST) {	
	if (BST) {
		while (BST->Left)	BST = BST->Left;
	}
	return BST;
}

查找最小元素#

遞歸函數

Position FindMax(BinTree BST) {
	if (!BST ) return NULL;//空樹，返回NULL
	else if ( !BST->Right )
		return BST;	//找到了最左葉節點
	else 
		return FindMin(BST->Right);//沿右分支繼續查找
}

迭代函數

Position FindMax(BinTree BST) {	
	if (BST) {
		while (BST->Right)	BST = BST->Right;
	}
	return BST;
}

(3) 二叉搜尋樹的插入#

要保證插入後還為二叉搜尋樹，關鍵是要找到元素應該插入的位置。

BinTree Insert(ElementType X, BinTree BST) {
	if(!BST) {	//原樹為空，生成並返回一個節點的二叉搜尋樹
		BST = malloc(sizeof(struct TreeNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {	//開始尋找待插入元素的位置
		if (X < BST->Data)
			BST->Left = Insert(X, BST->Left);
		else if (X > BST->Data)
			BST->Right = Insert(X, BST->Right);
		else printf("該值已存在"); 
	}
	return BST;
}

(4) 二叉搜尋樹的刪除#

考慮三種情況

要刪除的是葉節點：直接刪除，並修改其父節點的指針
要刪除的節點只有一個孩子節點：將其父節點的指針指向要刪除節點的孩子節點
要刪除的節點有左、右兩棵子樹: 要用另一個節點替代被刪除的節點（右子樹的最小元素或左子樹的最大元素）

BinTree Delete(ElementType X, BinTree BST) {
	Position Tmp;
	if(!BST) printf("要刪除的元素未找到");
	else if (X < BST->Data) 
		BST->Left = Delete(X,BST->Left);
	else if (X > BST->Data) 
		BST->Right = Delete(X,BST->Right);
	else {	//找到了要刪除的節點
		if (BST->Left && BST->Right) {	//待刪除節點有左右兩個孩子
			Tmp = FindMin(BST->Right);	//在右子樹中找最小的元素填充刪除節點
			BST->Data = Tmp->Data;
			BST->Right = Delete(BST->Data,BST->Right);//填充完後，在右子樹中刪除該最小元素
		}
		else {	//待刪除節點有1個或無子節點
			Tmp = BST;
			if (!BST->Left) //有有孩子或無子節點
				BST = BST->Right;
			else if (!BST->Right)
				BST = BST->Left;
			free(Tmp);
		}
	}
	return BST;
}

二、平衡二叉樹#

1. 平衡二叉樹是什麼#

平衡二叉樹（AVL 樹，Banlanced Binary Tree)，可以為空，當不為空時滿足以下性質：

任一節點左、右子樹高度差的絕對值不超過 1
給定節點數為 n的 AVL 樹的最大高度為 O (log~2~n)!

平衡因子（BF,Banlanced Factor）(T) = h~L~-h~R~,h~L~ 和 h~R~ 分別為 T 的左、右子樹高度

2. 平衡二叉樹的調整#

RR 插入 ——RR 旋轉【右單旋】#

破壞節點（麻煩節點）位於被破壞節點（發現者）的右子樹的右子樹上
在這裡插入圖片描述

LL 插入 ——LL 旋轉【左單旋】#

破壞節點（麻煩節點）位於被破壞節點（發現者）的左子樹的左子樹上
在這裡插入圖片描述

LR 插入 ——LR 旋轉#

破壞節點（麻煩節點）位於被破壞節點（發現者）的左子樹的右子樹上
在這裡插入圖片描述

RL 插入 ——RL 旋轉#

破壞節點（麻煩節點）位於被破壞節點（發現者）的右子樹的左子樹上
在這裡插入圖片描述

ps：有時候插入元素即便不需要調整結構，也可能需要重新計算一些平衡因子#

3. 平衡二叉樹實現#

定義部分#

typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left, Right;
	int Height;
};
int Max(int a, int b) {
	return a>b?a:b;
}

左單旋#

ps必須要有一個左子節點 B，將 A 與 B 進行左單旋，並更新 A 與 B 的高度返回新的根節點 B

AVLTree SingleLeftRotation(AVLTree A) {
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( GetHeight(B->Left),A->Height ) + 1;
	return B;
}

右單旋#

ps必須要有一個右子節點 B，將 A 與 B 進行右單旋，並更新 A 與 B 的高度返回新的根節點 B

AVLTree SingleRightRotation(AVLTree A) {
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
	return B;
}

LR 旋轉#

ps必須要有一個左子節點 B，且 B 必須有一個右子節點 C
先將 B 與 C 做右單旋，返回 C
再將 A 與 C 做左單旋，返回 C

AVLTree DoubleLeftRightRotation(AVLTree A) {
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}

RL 旋轉#

ps必須要有一個右子節點 B，且 B 必須有一個左子節點 C
先將 B 與 C 做左單旋，返回 C
再將 A 與 C 做右單旋，返回 C

AVLTree DoubleRightLeftRotation(AVLTree A) {
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}

插入#

將 X 插入 AVL 樹 T 中，並返回調整後的 AVL 樹

AVLTree Insert(AVLTree T,ElementType X) {
	if (!T) {	//若要插入的樹是空樹，則新建一個包含節點X的樹
		T = (AVLTree) malloc(sizeof(struct AVLNode));
		T->Data = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
	} else if( X < T->Data) {
		T->Left = Insert(T->Left, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//需要左旋
			if (X < T->Left->Data)
				T = SingleLeftRotation(T);	//需要左單旋
			else 
				T = DoubleLeftRightRotation(T);//左-右雙旋
		}
	} else if (X > T->Data) {
		T->Right = Insert(T->Right, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//需要右旋
			if (X > T->Right->Data)
				T = SingleRightRotation(T);	//需要右單旋
			else 
				T = DoubleRightLeftRotation(T);//右-左雙旋
		}
	}
	//更新樹高
	T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
	return T;
}

完整代碼演示#

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left, Right;
	int Height;
};
int Max(int a, int b) {
	return a>b?a:b;
}
int GetHeight(AVLTree A) {
    if (A)
        return A->Height;
    else 
        return 0;
}
AVLTree SingleLeftRotation(AVLTree A) {//左單旋
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( GetHeight(B->Left),A->Height )+ 1;
	return B;
}
AVLTree SingleRightRotation(AVLTree A) {//右單旋
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
	return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A) {//左-右雙旋
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A) {//右-左雙旋
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T,ElementType X) {//將X插入AVL樹T中
	
	if (!T) {	//若要插入的樹是空樹，則新建一個包含節點X的樹
		T = (AVLTree) malloc(sizeof(struct AVLNode));
		T->Data = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
        
	} else if( X < T->Data) {
		T->Left = Insert(T->Left, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//需要左旋
			if (X < T->Left->Data)
				T = SingleLeftRotation(T);	//需要左單旋
			else 
				T = DoubleLeftRightRotation(T);//左-右雙旋
		}
	} else if (X > T->Data) {
		T->Right = Insert(T->Right, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//需要右旋
			if (X > T->Right->Data)
				T = SingleRightRotation(T);	//需要右單旋
			else 
				T = DoubleRightLeftRotation(T);//右-左雙旋
		}
	}
	//更新樹高
	T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
    return T;
}
void PreOrderTraversal(AVLTree T) {
	if(T) {
		printf("%d", T->Data);
		PreOrderTraversal( T->Left);
		PreOrderTraversal( T->Right);
	}
}
void InOrderTraversal(AVLTree T) {
	if(T) {
		InOrderTraversal( T->Left);
		printf("%d", T->Data);
		InOrderTraversal( T->Right);
	}
}
int main() {
    AVLTree T = NULL;
    int i;
    for (i = 1; i < 10; i++) {
        T = Insert(T,i);
    }
    PreOrderTraversal(T);//前序遍歷
    printf("\n");
    InOrderTraversal(T);//中序遍歷
    return 0;
}

輸出結果：

421365879
123456789

根據前序遍歷與中序遍歷易還原得到這樣一棵平衡二叉樹

在這裡插入圖片描述

三、判斷是否同一棵二叉搜尋樹#

題意：給定一個插入序列確定唯一一棵二叉搜尋樹，對於輸入的各種插入序列，判斷它們是否能生成一樣的二叉搜尋樹

如何判斷兩個序列是否對應相同搜尋樹呢
建一棵樹，再判別其他序列是否與該樹一致！
如輸入 3 1 4 2 確定一顆二叉搜尋樹，判斷 3 4 1 2 和 3 2 4 1 是否對應同一棵樹

1. 搜尋樹表示#

typedef struct TreeNode *Tree;
struct TreeNode {
	int v;
	Tree Left,Right;
	int flag;	//用來標記該節點是否已經被搜尋過 為1則搜尋過
};

2. 建搜尋樹 T#

Tree MakeTree(int N) {
	Tree T;
	int i, V;
	scanf("%d", &V);
	T = NewNode(V);
	for(i = 1; i < N; i++) {
		scanf("%d",&V);
		T = Insert(T,V);//將剩余節點插入二叉樹
	}
	return T;
}

Tree NewNode(int V) {
	Tree T = (Tree)malloc(sizeof(struct TreeNode));
	T->v = V;
	T->Left = T->Right = NULL;
	T->flag = 0;
	return T;
}

Tree Insert(Tree T, int V) {
	if(!T) T = NewNode(V);
	else {
		if (V > T->v) 
			T->Right = Insert(T->Right, V);
		else 
			T->Left = Insert(T->Left,V);
	}
	return T;
}

3. 判別一序列是否與搜尋樹 T 一致#

方法：在樹 T 中按順序搜尋序列 3 2 4 1 中的每個數

若每次搜尋所經過的節點在前面均搜尋過，則一致
否則（某次搜尋中遇到了前面未出現的節點），則不一致

int check(Tree T,int V) {
	if(T->flag) {//這個點查找過了,則判斷要在左子樹還是右子樹查找
		if(V < T->v) return check(T->Left,V);
		else if(V > T->v) return check(T->Right,V);
		else return 0;
	}
	else {	//要查找的剛好是這個點，進行標記
		if(V == T->v) {
			T->flag = 1;
			return 1;
		}
		else return 0; //碰到了以前沒見過的點
	}
}

判斷長度為 N 的插入序列產生的樹是否與搜尋樹一致

int Judge(Tree T,int N) {
	int i, V, flag = 0;//flag=0代表當前還一致，為1則說明已經不一致了
	scanf("%d",&V);
	if (V != T->v) flag = 1;
	else T->flag = 1;
	for(i = 1; i < N; i++) {
		scanf("%d", &V);
		if( (!flag) && (!check(T,V)) ) flag = 1;
	}
	if(flag) return 0;
	else return 1;
}

清除 T 中個節點的 flag 標記使其為 0

void ResetT(Tree T) {
	if(T->Left) ResetT(T->Left);
	if(T->Right) ResetT(T->Right);
	T->flag = 0;
}

釋放 T 的空間

void FreeTree(Tree T) {
	if(T->Left) FreeTree(T->Left);
	if(T->Right) FreeTree(T->Right);
	free(T);
}