数据结构学习笔记＜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);
}