第四章-平衡二叉樹
我們為了解決二叉樹的查找，我們構建出了二叉搜索樹（左子樹小於其父結點，右子樹大於其父結點）。但是這樣顯然是不夠的，這樣的查找太過於笨重，我們就想出了二叉平衡樹：
就是一個結點的左右子樹高度差不能等於2，當等於2時，我們就對它進行平衡，這樣減少了極端情況，可以明顯的縮小查找的時間，二叉平衡在插入的時候會出現四種情況——LL，RR，LR，RL。下面我們用程式碼進行說明：
#include <stdio.h>
#include <stdlib.h>
typedef struct TNode {
int data;
struct TNode *left;
struct TNode *right;
int height;
}TNode,*Tree;
typedef struct QNode {
Tree data;
int top;
int base;
int maxsize;
}QNode,*Queue;
void InitQueue (Queue *q);//初始化隊列。
void En (Queue q, Tree T);//進隊。
Tree De (Queue q);//出隊。
int IsFull (Queue q);//判斷是否為滿。
int IsEmpty (Queue q);//判斷是否為空。
void Level (Tree T);//層次遍歷二叉樹。
void Level (Tree T)//層次遍歷是用來檢驗二叉樹是否平衡正確。
{
Queue q;
InitQueue (&q);
En(q,T);
Tree temp;
while(!IsEmpty(q)) {
temp = De(q);
printf(“%d “,temp->data);
if(temp->left) En(q,temp->left);
if(temp->right) En(q,temp->right);
}
}
void InitQueue (Queue *q)
{
(*q) = (QNode*) malloc(sizeof(QNode));
(*q)->top = (*q)->base = 0;
(*q)->maxsize = 10;
(*q)->data = (Tree) malloc(sizeof(TNode) * (*q)->maxsize);
}
int IsFull(Queue q)
{
return ((q->top + 1) % (q->maxsize – 1) == q->base);
}
int IsEmpty (Queue q)
{
return (q->base == q->top);
}
void En (Queue q, Tree T)
{
if (IsFull(q)) {
printf(“The queue is full!\n”);
}else {
TNode *temp;
temp = T;
q->data[q->top] = *temp;
q->top = (q->top + 1) % (q->maxsize -1 );
}
}
Tree De (Queue q)
{
if(IsEmpty(q)) {
printf(“The queue is empty!\n”);
}else {
Tree T;
T = &(q->data[q->base]);
q->base = (q->base + 1) % (q->maxsize – 1);
return T;
}
}
int Height (Tree T)//返回當前結點的高度。
{
if(!T) {
return -1;
}else {
return T->height;
}
}
int Max (int a, int b)//返回a，b中最大的數字
{
return a>b?a:b;
}
Tree RotateWithLeft (Tree T)//左旋轉來平衡該結點。
{
Tree temp;
temp = T->left;
T->left = temp->right;
temp->right = T;
T->height = Max(Height(T->left),Height(T->right)) + 1;
temp->height = Max (Height(temp->left),Height(temp->right)) + 1;
return temp;
}
Tree RotateWithRight (Tree T)//右旋轉平衡該結點。
{
Tree temp;
temp = T->right;
T->right = temp->left;
temp->left = T;
T->height = Max(Height(T->left),Height(T->right)) + 1;//更新T的高度。
temp->height = Max(Height(temp->left),Height(temp->right)) + 1;//更系temp結點的高度。
return temp;
}
Tree RotateWithLeftRight (Tree T)//左右旋轉平衡。
{
T->left = RotateWithRight(T->left);
return (RotateWithLeft(T));
}
Tree RotateWithRightLeft (Tree T)//RL旋轉平衡。
{
T->right = RotateWithLeft (T->right);
return RotateWithRight(T);
}
Tree Insert (int x, Tree T)
{
if (!T) {//若結點為空，則生成新結點。
T = malloc(sizeof(TNode));
T->data = x;
T->height = 0;
T->left = T->right = NULL;
}else if (x < T->data) {//小於的話，則插入左子樹。
T->left = Insert (x,T->left);
if (Height(T->left) – Height(T->right) == 2) {//插入後，若左右子樹的高度差等於2，則進行平衡。
if (x < T->left->data) {//若小於，肯定屬於LL旋轉。
T = RotateWithLeft (T);
}else {//否則屬於LR旋轉。
T = RotateWithLeftRight(T);
}
}
}else if (x > T->data) {//大於就插入右子樹。
T->right = Insert (x,T->right);
if (Height(T->right) – Height(T->left) == 2){
if (x > T->right->data) {//若大於，同上。
T = RotateWithRight(T);
}else {
T = RotateWithRightLeft(T);//同上。
}
}
}
T->height = Max(Height(T->left),Height(T->right)) + 1;//完成後，我們需要更新該結點的高度。
return T;
}
int main ()//測試函數。
{
Tree T;
int i;
for( i =1 ;i < 10;i++) {
T = Insert (i,T);
//printf(“data is %d”,T->data);
}
Level (T);
return 0;
}
今天就寫到這裡吧，期待下一次！
