【数据结构】-二叉树的应用(二叉排序树)

绝地灬酷狼 2023-03-03 13:28 22阅读 0赞

### 二叉排序树BST ###

*  1.头文件及类型定义
 *  2.二叉排序树结点类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 查找操作
     *   *  4.1.1 非递归查找
         *  4.1.2 递归查找
     *  4.2 插入操作
     *   *  4.2.1 非递归插入
         *  4.2.2 递归插入
     *  4.3 构造二叉排序树
     *  4.4 删除操作
     *   *  4.4.1 寻找最左下结点
         *  4.4.2 寻找最右下结点
         *  4.4.3 删除操作-用右子树中最左下结点填充
         *  4.4.4 删除操作-用左子树中最右下结点填充
     *  4.5 中序遍历
     *  4.6 main函数
     *  4.7 测试结果
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int

# 2.二叉排序树结点类型定义 #

//二叉排序树结点类型定义
    typedef struct BSTNode {
        
    	ElemType data;		//数据元素		
    	struct BSTNode* lchild, * rchild;	//左右指针
    }BSTNode, * BSTree;

# 3.函数声明 #

/*函数声明*/
    BSTNode* BST_Search(BSTree T, ElemType key);			//1-1.查找操作-非递归
    BSTNode* BSTSearch(BSTree T, ElemType key);				//1-2.查找操作-递归
    bool BST_Insert(BSTree& T, ElemType key);				//2-1.插入操作-非递归
    bool BSTInsert(BSTree& T, ElemType key);				//2-2.插入操作-递归
    void Create_BST(BSTree& T, ElemType arr[], int n);		//3.构造二叉排序树
    BSTNode* FirstNode(BSTNode* p);							//4-1.找到最左下结点
    BSTNode* LastNode(BSTNode* p);							//4-2.找到最右下结点
    BSTNode* BST_Delete1(BSTree& T, ElemType key);			//4-3.删除操作-用右子树中最左下结点填充
    BSTNode* BST_Delete2(BSTree& T, ElemType key);			//4-4.删除操作-用左子树中最右下结点填充
    void InOrder(BSTree T);									//5.中序遍历

# 4.基本操作 #

## 4.1 查找操作 ##

### 4.1.1 非递归查找 ###

//1-1.查找操作-非递归(最坏空间复杂度O(1))
    BSTNode* BST_Search(BSTree T, ElemType key) {
        
    	while (T != NULL && key != T->data) {
        	//若树空或找到结点，则结束循环
    		if (key < T->data)
    			T = T->lchild;		//小于，在左子树上查找
    		else
    			T = T->rchild;		//大于，在右子树上查找
    	}
    	return T;
    }

### 4.1.2 递归查找 ###

//1-2.查找操作-递归(最坏空间复杂度O(h),h指树的高度)
    BSTNode* BSTSearch(BSTree T, ElemType key) {
        
    	if (T == NULL)
    		return NULL;		//查找失败
    	if (key == T->data)
    		return T;			//查找成功
    	else if (key < T->data)
    		return BSTSearch(T->lchild, key);		//小于，在左子树上查找
    	else
    		return BSTSearch(T->rchild, key);		//大于，在右子树上查找
    }

## 4.2 插入操作 ##

### 4.2.1 非递归插入 ###

//2-1.插入操作-非递归(最坏空间复杂度O(1))
    bool BST_Insert(BSTree& T, ElemType key) {
        
    	BSTNode* p = T;					//搜索指针
    	BSTNode* parent = NULL;			//p的双亲结点
    	while (p) {
        	//找到插入位置
    		if (key == p->data)			//树中存在相同关键字的结点
    			return false;				//插入失败
    		else {
        
    			parent = p;				//保留p的双亲结点
    			if (key < p->data) 	
    				p = p->lchild;			//小于，在左子树上寻找插入位置
    			else
    				p = p->rchild;			//大于，在右子树上寻找插入位置
    		}	
    		
    	}
    	/*	直接插入到p是不会改变二叉树的
    		p = (BSTNode*)malloc(sizeof(BSTNode));		//分配存储空间
    		p->data = key;								//放入结点值		
    		p->lchild = p->rchild = NULL;				//左右孩子置空
    	*/
    	BSTNode* s = (BSTNode*)malloc(sizeof(BSTNode));
    	s->data = key;
    	s->lchild = s->rchild = NULL;
    	if (!parent)			//若T为空树
    		T = s;			//将s设为根结点
    	else if (key < parent->data)
    		parent->lchild = s;		//小于，插入pre的左子树
    	else
    		parent->rchild = s;		//大于，插入pre的右子树
    	return true;			//插入成功
    }

### 4.2.2 递归插入 ###

//2-2.插入操作-递归(最坏空间复杂度O(h),h指树的高度)
    bool BSTInsert(BSTree& T, ElemType key) {
        
    	if (T == NULL) {
        							//找到要插入的位置
    		T = (BSTNode*)malloc(sizeof(BSTNode));	//分配存储空间
    		T->data = key;							//放入结点值
    		T->lchild = T->rchild = NULL;	        //左右孩子置空
    		return true;		                        //插入成功
    	}
    	else if (key == T->data)		//树中存在相同关键字的结点
    		return false;					//插入失败
    	else if (key < T->data)						
    		return BSTInsert(T->lchild, key);		//小于，在左子树上插入
    	else if (key > T->data)
    		return BSTInsert(T->rchild, key);		//大于，在右子树上插入
    }

## 4.3 构造二叉排序树 ##

/*3.构造二叉排序树：按照arr[]中的关键字序列建立二叉排序树*/
    void Create_BST(BSTree& T, ElemType arr[], int n) {
        
    	T = NULL;			//初始T为空树		
    	int i = 0;
    	while (i < n) {
        		//依次将每个关键字插入到二叉排序树中 
    		BSTInsert(T, arr[i]);
    		i++;
    	}
    }

## 4.4 删除操作 ##

### 4.4.1 寻找最左下结点 ###

//4-1.找到最左下结点，也是最小结点
    BSTNode* FirstNode(BSTNode* p) {
        
    	if (p)					
    		while (p->lchild)	
    			p = p->lchild;
    	return p;
    }

### 4.4.2 寻找最右下结点 ###

//4-2.找到最右下结点，也是最大结点
    BSTNode* LastNode(BSTNode* p) {
        
    	if (p)
    		while (p->rchild)
    			p = p->rchild;
    	return p;
    }

### 4.4.3 删除操作-用右子树中最左下结点填充 ###

//4-3.删除操作-用右子树中最左下结点填充
    BSTNode* BST_Delete1(BSTree& T, ElemType key) {
        
    	BSTNode* tmp;
    	if (!T)
    		printf("要删除的元素未找到！");
    	else if (key < T->data)
    		T->lchild = BST_Delete1(T->lchild, key);		//小于，删除左孩子
    	else if (key > T->data)
    		T->rchild = BST_Delete1(T->rchild, key);		//大于，删除右孩子
    	else   //找到要删除的结点
    		if (T->lchild && T->rchild) {
        	//1.被删除结点右左右两个子结点
    			tmp = FirstNode(T->rchild);		//找到右子树的最左下结点填充删除结点
    			T->data = tmp->data;
    			T->rchild = BST_Delete1(T->rchild, T->data);		//在删除结点的右子树中删除最小结点
    		}
    		else {
        	//2.被删除结点有一个子结点或者都没有
    			tmp = T;
    			if (!T->lchild)
    				T = T->rchild;		//有右孩子或无子结点
    			else if (!T->rchild)
    				T = T->lchild;
    			free(tmp);
    		}
    	return T;
    }

### 4.4.4 删除操作-用左子树中最右下结点填充 ###

//4-4.删除操作-用左子树中最右下结点填充
    BSTNode* BST_Delete2(BSTree& T, ElemType key) {
        
    	BSTNode* tmp;
    	if (!T)
    		printf("要删除的元素未找到！");
    	else if (key < T->data)
    		T->lchild = BST_Delete2(T->lchild, key);
    	else if (key > T->data)
    		T->rchild = BST_Delete2(T->rchild, key);
    	else   //找到要删除的结点
    		if (T->lchild && T->rchild) {
        	//1.被删除结点有左右两个子结点
    			tmp = LastNode(T->lchild);		//找到左子树的最右下结点填充删除结点
    			T->data = tmp->data;
    			T->lchild = BST_Delete2(T->lchild, T->data);		//在删除结点的左子树中删除最大结点
    		}
    		else {
        	//2.被删除结点有一个子结点或者都没有
    			tmp = T;
    			if (!T->lchild)
    				T = T->rchild;		//有右孩子或无子结点
    			else if (!T->rchild)
    				T = T->lchild;
    			free(tmp);
    		}
    	return T;
    }

## 4.5 中序遍历 ##

/*5.中序遍历：由二叉排序树的特性，对二叉排序树进行中序遍历会得到递增序列*/
    void InOrder(BSTree T) {
        
    	if (T != NULL) {
        
    		InOrder(T->lchild);			//递归遍历左子树
    		printf("%d\t", T->data);	//访问根结点
    		InOrder(T->rchild);			//递归遍历右子树
    	}
    }

## 4.6 main函数 ##

int main() {
        
    	BSTree T;			//声明一棵二叉排序树
    	int arr[] = {
         19,13,11,8,50,26,21,30,66,60,70,63,61,65 };		//测试序列
    
    	/*1、构造一棵二叉排序树*/
    	Create_BST(T, arr, 14);
    	printf("<————————构造二叉排序树————————>\n");
    	InOrder(T);
    	
    	/*2、插入指定元素-递归*/
    	printf("\n<————————二叉排序树递归插入元素————————>\n");
    	if (BSTInsert(T, 62))
    		InOrder(T);
    	else
    		printf("树中已存在相同结点，插入失败！");
    
    	/*3、插入指定元素-非递归*/
    	printf("\n<————————二叉排序树非递归插入元素————————>\n");
    	if(BST_Insert(T, 67))
    		InOrder(T);
    	else
    		printf("树中已存在相同结点，插入失败！");
    
    	/*4、删除指定元素-右子树最左下结点填充*/
    	printf("\n<————————删除指定元素-右子树最左下结点填充————————>\n");
    	BST_Delete1(T, 60);
    	InOrder(T);
    
    	/*5、删除指定元素-左子树最右下结点填充*/
    	printf("\n<————————删除指定元素-左子树最右下结点填充————————>\n");
    	BST_Insert(T, 60);		//先恢复被删除的测试结点，便于对比
    	BST_Delete2(T, 60);
    	InOrder(T);
    
    	return 0;
    }

## 4.7 测试结果 ##

![测试结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]

# 5.小结 #

1.  **二叉排序树的特性**  
    最重要的特性：左子树结点值<根结点值<右子树结点值  
    所以对二叉排序树进行**中序遍历**，必然得到一个**单调递增的有序序列**。
2.  **二叉排序树的操作**  
    （1）二叉排序树的查找和插入均有**递归**和**非递归**两种实现方式，需要注意的是，在非递归的插入操作中，不能直接修改p，要记录其父结点，然后通过更改左右指针完成插入。  
    （2）二叉排序树的删除操作较为复杂，以下分类讨论  
    \------>①若删除结点x**无左右孩子**，则直接删除即可  
    \------>②若删除结点x**只有一个左子树或右子树**，则让x的子树代替x的位置。  
    \------>③若删除结点x**有左右两个孩子**，有两种实现方式：一种是找到x的左子树中最大的结点p(**即x的左子树的最右下结点**)，将p的值赋给x，然后删除p结点，对p的子树递归此过程。另一种是找到x的右子树中最小的结点q(**即x的右子树的最左下结点**)，将q的值赋给x，然后删除q结点，对q的子树递归此过程。*本质上是对被删除结点值的修改，对最左下或最右下结点的删除。*
3.  **二叉排序树的查找效率**  
    直接给出结论，二叉树的查找效率，主要取决于树的高度。即：在相同结点情况下，二叉树越低，查找效率越高，反之则越低。所以，如何构造最低高度的二叉排序树呢，引入**平衡二叉树**。
4.  **关于二叉树的其他应用**  
    除二叉排序树外，二叉树还有两个重要应用：平衡二叉树和哈夫曼树。

*  平衡二叉树–>掌握其四种旋转：**LL，RR，LR，RL**。
 *  哈夫曼树---->掌握其**构造方法和哈夫曼编码**。
    
    这两个应用主要在于理解其思想。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/aaebc7c4cd924918be0aee4120be1974.png