banner
cos

cos

愿热情永存，愿热爱不灭，愿生活无憾
github
tg_channel
bilibili
主页归档关于♪歌单NFT作品集

数据结构学习笔记＜5＞ 二叉搜索树与平衡二叉树

#c++#数据结构#二叉树137
AI 生成的摘要
本文介绍了二叉搜索树和平衡二叉树的概念及相关操作函数。其中，二叉搜索树是一棵满足左子树小于根节点，右子树大于根节点的二叉树，操作函数包括查找、插入、删除等；平衡二叉树是一棵左右子树高度差不超过1的二叉树，操作函数包括插入时的旋转等。

一、二叉搜索树#

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);
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。