《数据结构与算法》——树与二叉树的应用之二叉排序树（Binary Sort Tree）总结

朱雀 2021-10-29 11:20 262阅读 0赞

# 《数据结构与算法》——树与二叉树的应用之二叉排序树（Binary Sort Tree）总结 #

它来了，它来了，二叉排序树挥舞着它的两个子树向我们走来了~

纠结于复习树和森林的遍历还是树的应用时，天气太热，不纠结了，点点豆豆，点到谁就是谁~

**目录**

《数据结构与算法》——树与二叉树的应用之二叉排序树（Binary Sort Tree）总结

定义

方法实现

构建方法

插入方法

查找方法

删除方法

程序测试

总结

参考文献

--------------------

## 定义 ##

什么是二叉排序树？它是干嘛用的？咋用？（素质三连问，手动滑稽脸）

**二叉排序树**被称为**BST**，又被称为**二叉查找树。**显然，它是一棵二叉树，或者一棵空树。

作用从字面上来看是用来**实现排序和查找作用的**。

**咋用？**无非就是构建二叉排序树，在其中查找，在其中排序，删除某个结点。在讲解这些功能的时候，首先先搬出二叉排序树的标准定义。

二叉排序树或是一棵空树，或是符合以下特性的非空二叉树：

1.如果左子树非空，则**左**子树的所有结点的关键字值均**小于根**结点的关键字值；

2.如果右子树非空，则**右**子树的所有结点的关键字值均**大于根**结点的关键字值；

3.左右自树各自为一棵二叉排序树。

## 方法实现 ##

### 构建方法 ###

首先我们先构建一棵二叉排序树。构建二叉树就是从一个初始集合（数组/序列，随你咋叫）中不断取值并将其添加（插入）到二叉排序树中。

当插入某个值时，如果当前二叉树是空树，就把当前值作为二叉树的根节点；若不是空树，比较当前结点的值的大小，如果比当前值大，则递归的向左子树进行插入，如果比当前值小，则递归的向右子树进行插入。当然插入的终点就是递归的的终点，即当前树/结点为空值时的位置。

代码实现

void CreateBST(BiTree &T,Elemtype elem[],int n){//构建二叉树非递归实现
    	//T为当前树的根节点
    	//elem的值为关键字数组
    	//n为数组长度，即规模
    	T = NULL;//初始为一棵空树 
    	int i = 0;
    	while(i<n)
    		BSTInsert(T,elem[i++]);
    }

快看，**这里传入的变量类型为****BiTree****，就是普通的二叉树！**

这里出现了一个BSTInsert()方法，这是啥？

### 插入方法 ###

怎么向二叉排序树中插入一个结点呢？像上面构建方法那样。在上面把过程写的那么多，但是怎么没见实现这些步骤呢？什么左呀右呀的，一行代码也没见，其实现的功能全部在插入方法BSTInsert()中。再陈述一下本方法的实现步骤。

当插入某个值时，如果当前二叉树是空树，就把当前值作为二叉树的根节点；若不是空树，比较当前结点的值的大小，如果比当前值大，则递归的向左子树进行插入，如果比当前值小，则递归的向右子树进行插入。当然插入的终点就是递归的的终点，即当前树/结点为空值时的位置。当然还有一种情况，就是当前值和插入值相等时，不用管它，直接结束当前层次的算法运行。因为**二叉排序树不允许出现两个值相同的结点**。

代码实现

bool BSTInsert(BiTree &T , Elemtype elem){//二叉排序树的插入
    	 if(T==NULL){//插入当前位置 
    	 	T = (BiTree)malloc(sizeof(BiTNode));
    	 	T->data = elem;
    	 	T->lchild = T->rchild = NULL;
    	 	return true;
    	 }
    	if(T->data == elem)//已存在值 
    	 	return 0;
    	if(T->data < elem)//插入右子树 
    	 	return BSTInsert(T->rchild,elem);
    	return BSTInsert(T->lchild,elem);//插入左子树 
    }

### 查找方法 ###

现在的树构造成功了，实现它最主要的功能——查找的时候到了！

首先我们手里有一棵二叉排序树和一个待查找的元素elem，首先我们需要和根节点比较，比它的关键值大就在右子树里进行查找，比它的关键值小就在左子树里进行查找。依次直到找到相等结点值为止，当然也会有一种情况，没有这个值，那我们就给它返回一个空值。

代码实现

BiTree BSTSearch(BiTree T , Elemtype elem){//二叉排序树的插入
    	BiTree p = T;
    	while(p&&p->data!=elem){
    		if(p->data<elem)
    			p = p->rchild;
    		else
    			p = p->lchild;
    	}
    	return p;
    }

### 删除方法 ###

在复习这个方法之前心里发怵，原因是一想到什么左转，右转什么的就烦躁！emmm…..和平衡二叉树的插入搞混了。

其实仔细想想删除方法里的操作还是比较容易的，当准备删除一个结点时，我们可以观察它，如果这个子树无儿无女，那删了就删了。可要是它有一个孩子呢？那它唯一的孩子结点就得补上来。可要是有两个孩子结点呢？传给谁就值得讨论一下了。可以传给左孩子家族里最大（右）的结点，它是和删除结点最近的点（前驱结点），也可以传给右孩子家族里最小（左）的结点，它是和删除结点最近的点（后继结点）。他们来继承此位置，就可以看作是删除了继承结点原位置的结点。

代码实现

bool BSTDelect(BiTree &T , Elemtype elem){//二叉排序树的删除 
    	BiTree delt = (BiTree)malloc(sizeof(BiTNode));
    	delt = T;
    	BiTree p = NULL;//记录前结点 
    	int temp = 2;//标记左右结点 
    	//寻找该点
    	while(delt&&delt->data!=elem){
    		p = delt; 
    		if(delt->data<elem){
    			delt = delt->rchild;
    			temp = 0;
    		}	
    		else{
    			delt = delt->lchild;
    			temp = 1;
    		}	
    	}//delt为需要删除的点 
    	//进行删除
    	if(delt==NULL)
    		return 0;
    	if(!delt->lchild&&!delt->rchild){//叶子结点 
    		if(!temp)
    			p->rchild = NULL;
    		else
    			p->lchild = NULL; 
    		return 1;
    	}
    	
    	if(delt->lchild&&!delt->rchild){//只有左点 
    		if(!temp)
    			p->rchild = delt->lchild;
    		else if(temp==1)
    			p->lchild = delt->lchild;
    		return 1;
    	}
    	if(!delt->lchild&&delt->rchild){//只有右点 
    		if(!temp)
    			p->rchild = delt->lchild;
    		else if(temp==1)
    			p->lchild = delt->lchild;
    		return 1;
    	}
    	//左右子树均存在
    	//寻找右子树最左点
    	BiTree rp = delt->rchild;//记录前结点
    	while(rp->lchild)
    		rp = rp->lchild;
    	delt->data = rp->data;
    	BSTDelect(rp->lchild,rp->data);
    	return 1;
    }

## 程序测试 ##

/*编译环境：
    win10专业版
    DEV C++ 5.11
    TDM-GCC 4.9.2 64bit
    */
    
    #include<iostream>
    #include "malloc.h"
    #define MAX 9 
    using namespace std;
    
    typedef char Elemtype;
    typedef struct BiTNode{//定义二叉树结构 
    	Elemtype data;
    	BiTNode *lchild,*rchild;
    } BiTNode,*BiTree;
    
    void visit(BiTree b){//访问结点
    	cout<<b->data<<"\t";
    }
    
    void PreOrder(BiTree T){//先序遍历·递归（PreOrder）
    	if(T){
    		visit(T);
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    }
    
    /*此处添加需要测试的方法代码*/
    
    int main(){
    	Elemtype elem[MAX]={'e','g','m','r','f','d','n','c','h'};
    	BiTree T = (BiTree)malloc(sizeof(BiTNode));
    	BiTree temp = NULL;
    	CreateBST(T,elem,MAX);
    	cout<<"说明：\n构建序列为：'e','g','m','r','f','d','n','c','h'"<<endl;
    	cout<<"以二叉树的先序遍历为例进行展示。"<<endl; 
    	cout<<"************************************************"<<endl; 
    
    	cout<<"构建二叉排序树完成：\t";PreOrder(T);
    	temp = BSTSearch(T , 'r');
    	if(temp)
    		cout<<endl<<"查找'r'完成：\t";visit(temp);
    	if(BSTInsert(T ,'b'))	
    		cout<<endl<<"插入结点'b'完成：\t";PreOrder(T);
    	if(!BSTInsert(T ,'b'))	
    		cout<<endl<<"插入结点'b'失败！已存在该点！";
    	if(BSTDelect(T ,'b'))	
    		cout<<endl<<"删除叶子结点'b'完成：\t";PreOrder(T);
    	if(!BSTDelect(T ,'b'))	
    		cout<<endl<<"删除叶子结点'b'失败！不存在该点！";
    	if(BSTDelect(T ,'d'))	
    		cout<<endl<<"删除单子结点'd'完成：\t";PreOrder(T);
    	if(BSTDelect(T ,'e'))	
    		cout<<endl<<"删除双子结点'e'完成：\t";PreOrder(T);
    	return 0; 
    }

## 总结 ##

只要思想不滑坡，方法总比困难多。嗯，其实也没那么难。

## 参考文献 ##

王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.

**如有错误，还请朋友不吝指正。**