2022-1-2 数据结构—树—下(c语言代码)

2023-10-19 15:11:46

1. 二叉搜索树

定义
二叉搜索树（BST）也称二叉排序树或二叉查找树
二叉搜索树：一棵二叉树，可以为空；
如果不为空，满足以下性质：

非空左子树的所有键值小于其根结点的键值
非空右子树的所有键值大于其根结点的键值
左、右子树都是二叉搜索树

2. 抽象数据

2.1 特殊函数

#include<iostream>
#include<malloc.h>
using namespace std;
typedef int ElementType;
typedef struct TreeNode *BinTree;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

BinTree Find(ElementType X,BinTree BST)：从二叉搜索树 BST 中查找元素 X，返回其所在结点地址
BinTree FindMin(BinTree BST)：从二叉搜索树 BST 中查找并返回最小元素所在结点的地址
BinTree FindMax(BinTree BST)：从二叉搜索树 BST 中查找并返回最大元素所在结点的地址
BinTree Insert(ElementType X,BinTree BST)：插入一个元素进 BST
BinTree Delete(ElementType X,BinTree BST)：从 BST 中删除一个元素

2.2 查找

查找从根结点开始，如果树为空，返回 NULL
若搜索树不为空，则根结点键值和 X 进行比较，并进行不同处理：
* 若 X 小于根结点键值，在左子树中继续查找
* 若 X 大于根结点键值，在右子树中继续查找
* 如 X 等于根节点键值，查找结束，返回指向此结点的指针
查找最大和最小元素
* 最大元素一定是在树的最右分支的端结点上
* 最小元素一定是在树的最左分支的端结点上

2.2.1 查找递归实现

// 查找递归实现 
BinTree Find(ElementType X,BinTree BST){
	if(!BST)  // 如果根结点为空，返回 NULL 
		return NULL; 
	if(X < BST->Data) // 比根结点小，去左子树查找 
		return Find(X,BST->Left); 
	else if(BST->Data < X)  // 比根结点大，去右子树查找 
		return Find(X,BST->Right);
	else if(BST->Data == X) // 找到了 
		return BST;
}

查找最小值的递归实现

// 查找最小值的递归实现
BinTree FindMin(BinTree BST){
	if(!BST)    // 如果为空了，返回 NULL 
		return NULL;  
	else if(BST->Left)   // 还存在左子树，沿左分支继续查找 
		return FindMin(BST->Left);
	else  // 找到了 
		return BST;
}

2.2.2 查找非递归实现

// 查找非递归实现
BinTree IterFind(ElementType X,BinTree BST){
	while(BST){
		if(X < BST->Data)
			BST = BST->Left;
		else if(BST->Data < X)  // 比根结点大，去右子树查找 
			BST = BST->Right;
		else if(BST->Data == X) // 找到了 
			return BST;
	}
	return NULL;
}

查找最大值的非递归实现

// 查找最大值的非递归实现
BinTree FindMax(BinTree BST){
	if(BST)  // 如果不空 
		while(BST->Right)   // 只要右子树还存在 
			BST = BST->Right;
	return BST;
}

2.3 删除

删除的三种情况：
1. 要删除的是叶结点：直接删除，并将其父结点指针置为 NULL
2. 要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
3. 要删除的结点有左、右两棵子树：用右子树的最小元素或左子树的最大元素替代被删除结点

// 删除
BinTree Delete(ElementType X,BinTree BST){
	BinTree tmp;
	if(!BST)  //递归结束标志！！！！！
		cout<<"要删除的元素未找到";
	else if(X < BST->Data)   // X 比当前结点值小，在左子树继续查找删除 
		BST->Left = Delete(X,BST->Left);
	else if(BST->Data < X)   // X 比当前结点值大，在右子树继续查找删除 
		BST->Right = Delete(X,BST->Right);
	else{  //  找到被删除结点 
		if(BST->Left && BST->Right){  // 被删除结点有俩孩子结点 
			tmp = FindMin(BST->Right);   // 找到右子树中值最小的
			BST->Data = tmp->Data;     // 用找到的值覆盖当前结点 
			BST->Right = Delete(tmp->Data,BST->Right);    // 把前面找到的右子树最小值结点删除 
		}else{  // 被删除结点只有一个孩子结点或没有孩子结点 
			tmp = BST;
			if(!BST->Left && !BST->Right)  // 没有孩子结点 
				BST = NULL;
			else if(BST->Left && !BST->Right)  // 只有左孩子结点 
				BST = BST->Left;
			else if(!BST->Left && BST->Right)  // 只有右孩子结点 
				BST = BST->Right;
			free(tmp);
		}
	}
	return BST;
}

2.4 插入

// 插入
BinTree Insert(ElementType X,BinTree BST){
	if(!BST){  // 如果为空，初始化该结点 ，结束标志！！！！！！！！！！！
		BST = (BinTree)malloc(sizeof(struct TreeNode));
		BST->Data = X;
		BST->Left = NULL;
		BST->Right = NULL;
	}else{ // 不为空 
		if(X < BST->Data)  // 如果小，挂在左边 
			BST->Left = Insert(X,BST->Left);
		else if(BST->Data < X)  // 如果大，挂在右边 
			BST->Right = Insert(X,BST->Right);
		// 如果相等，什么都不用做 
	}
	return BST;
}

2.5 中序遍历

// 中序遍历 
void  InOrderTraversal(BinTree BT){
	if(BT){
		InOrderTraversal(BT->Left);  // 进入左子树 
		cout<<BT->Data;  // 打印根 
		InOrderTraversal(BT->Right);  // 进入右子树 
	}
}

2.6 测试

int main(){
	BinTree BST = NULL;
	BST = Insert(5,BST); 
	BST = Insert(7,BST); 
	BST = Insert(3,BST); 
	BST = Insert(1,BST); 
	BST = Insert(2,BST); 
	BST = Insert(4,BST); 
	BST = Insert(6,BST); 
	BST = Insert(8,BST); 
	BST = Insert(9,BST); 
	/*
			    5
			   /\
			  3  7
             /\	 /\
            1 4 6  8
			\      \
			 2      9
	*/
	cout<<"中序遍历的结果是："; 
	InOrderTraversal(BST);
	cout<<endl;
	cout<<"查找最小值是："<<FindMin(BST)->Data<<endl;
	cout<<"查找最大值是："<<FindMax(BST)->Data<<endl; 
	cout<<"查找值为3的结点左子树结点值为："<<Find(3,BST)->Left->Data<<endl;
	cout<<"查找值为7的结点右子树结点值为："<<IterFind(7,BST)->Right->Data<<endl;
	cout<<"删除值为5的结点"<<endl;
	Delete(5,BST);
	/*
			    6
			   /\
			  3  7
             /\	  \
            1 4    8
			\      \
			 2      9
	*/
	cout<<"中序遍历的结果是："; 
	InOrderTraversal(BST);
	cout<<endl;
	return 0;
}

3.平衡二叉树

二叉搜索树的搜索效率与其树的深度相关，而二叉搜索树的组成又与其插入序列相关，在极端情况下，二叉搜索树退化为一条单链（比如插入序列是 1 2 3 … n），使得搜索效率大大降低，为了避免这种情况出现，我们采用二叉平衡树对插入结点进行调整，使得树的深度尽可能小。
平衡因子：BF(T) = hL-hR, 分别是左右子树的高度
平衡二叉树(AVL 树)：空树，或者任一结点左、右子树高度差的绝对值不超过 1，即 |BF(T)|≤1 的树

4.平衡二叉树的调整

遵循原则
从离插入结点最近的结点调整

4.1 RR 单旋

当"插入结点"(BR)是"被破坏平衡结点"(A)右子树的右子树时，即 RR 插入时，采用 RR 旋转调整

将 B 的左子树腾出来挂到 A 的右子树上，返回 B 作为当前子树的根
C

AVLTree RRRotation(AVLTree A){
	AVLTree B = A->right;   // B 为 A 的右子树  
	A->right = B->left;    // B 的左子树挂在 A 的右子树上 
	B->left = A;   //  A 挂在 B 的左子树上 
	return B;  // 此时 B 为根结点了   
}

4.2 LL 单旋

当"插入结点"(BL)是"被破坏平衡结点"(A)左子树的左子树时，即 LL 插入，采用 RR 旋转调整

把 B 的右子树腾出来挂到 A 的左子树上，返回 B 作为当前子树的根
c

AVLTree LLRotation(AVLTree A){
	// 此时根节点是 A 
	AVLTree B = A->left;  // B 为 A 的左子树  
	A->left = B->right;   // B 的右子树挂在 A 的左子树上 
	B->right = A;     //  A 挂在 B 的右子树上 
	return B;  // 此时 B 为根结点了 
}

4.3 LR 双旋

当"插入结点"(CL 或者 CR)是"被破坏平衡结点"(A)左子树的右子树时，即 LR 插入，采用 LR 旋转调整

AVLTree LRRotation(AVLTree A){
	// 先 RR 单旋
	A->left = RRRotation(A->left);
	// 再 LL 单旋 
	return LLRotation(A);
}

总结：叫 LR 双旋是从上到下看，而实际先 RR 单旋再 LL 单旋是从下往上的过程

4.4 RL 双旋

当"插入结点"(CL 或者 CR)是"被破坏平衡结点"(A)右子树的左子树时，即 RL 插入，采用 RL 旋转调整

基本思想是先将 B 作为根结点进行 LL 单旋转化为 RR 插入，再将 A 作为根结点进行 RR单旋（先 LL 再 RR）

AVLTree RLRotation(AVLTree A){
	// 先 LL 单旋
	A->right = LLRotation(A->right);
	// 再 RR 单旋 
	return RRRotation(A); 
}

总结：叫 RL 双旋是从上到下看，而实际先 LL 单旋再 RR 单旋是从下往上的过程

码农公寓