二叉树的应用（排序二叉树的实现及其详解）以及平衡二叉树的调整方法

矫情吗；* 2022-12-13 04:22 188阅读 0赞

## 排序二叉树 ##

所谓的排序二叉树，看名字就能看出来肯定是能够用来排序的二叉树，按照我们以前构造的二叉树，无论是中序、后序、先序都不能够保证输出序列能够有序的输出。  
现在我们来看，二叉排序树是怎么一回事。  
二叉排序树只**有两种情况**  
①一棵空的二叉树  
②具有以下特征的二叉树  
**1.若二叉树的左子树非空，那么左子树上的结点值都小于根节点。  
2.若二叉树的右子树非空，那么右子树上的结点值都大于根节点。  
3.左右子树又全部满足以上两条特征。**  
现在我们构造如下图所示的二叉树  
![在这里插入图片描述][20201010000324669.png_pic_center]分析可知，该二叉树是一个二叉排序树。  
接下来我们对其进行中序的遍历输出，输出序列为**2,3，4,5,6,7**  
惊奇的发现，输出序列是一个**升序**的序列。  
接下来我们构造一个二叉排序树。  
**思考一下：** 之前我们建立普通二叉树的时候，可以采用递归的形式进行输入构造，但是二叉排序树建立的时候，我们却需要进行关键字大小的比较，递归输入的形式已经不满足需求，因此，我们需要先输入数据，之后再进行二叉树的构造。  
二叉排序树是一种特殊的二叉树，因此它的存储结构与二叉树相同。

typedef struct treeNode{
        
    	int data;
    	treeNode *lchild,*rchild;
    }*Tree;

接下来我们进行输入数据，创建结点，amazing 这不就是二叉树插入一个结点么 所以我们把 两个方法分开写 这样的话 方便我们再次插入节点时复用该方法。  
上代码：  
构造二叉树方法（这个方法不做过多的解释）

void createTree(Tree &T){
           //创建二叉树 
    	int data = 0;    //初始化data为0 
    	T = NULL;        //根节点初始化时指向空 
    	while(data != -1){
           //输入-1的时候  代表输入结束 
    		cin >> data;    //输入数据 
    		if(data!=-1)    //防止结束的时候将-1节点作为数据插入二叉树 
    		insertTree(T,data);   //调用插入二叉树的方法 
    	}
    }

插入节点方法

int insertTree(Tree &T,int data){
        	//插入节点的方法 
    	if(T == NULL){
        
    		T = new treeNode;    //初始化根节点 
    		T->lchild = NULL;
    		T->rchild = NULL;
    		T->data = data;
    		return 1;
    	}
    	else if(data == T->data){
           //如果data与某一个数据相同，插入失败 
    		return 0;
    	}else if(data < T->data){
           //如果data小于根节点的值 插入左子树 
    		insertTree(T->lchild,data); //递归依次进行结点的找寻 
    	}else{
             
    		insertTree(T->rchild,data);   
    	}
    }

\*\*思路：\*\*当我们输入第一个数据的时候，此时二叉树还是一颗空树，于是我们将第一个数据作为根节点![在这里插入图片描述][20201010005311822.png_pic_center]**重点：** 第二次输入数据，T依然指向根节点，我们与根节点做判别，如果小于根节点，就进入第二层递归根节点的孩子结点，初始化根节点的孩子结点，完成后返回1 重复输入数据 我们会很快的构造一个排序二叉树  
![在这里插入图片描述][20201010005651920.png_pic_center]  
**注意** **T指针始终指向二叉树的根节点**  
创建完成后 我们使用中序遍历的方法进行遍历，来测试我们是否构造成功。

//中序遍历输出各个节点的值 
    void printTree(Tree &T){
        
    	if(T){
            //判断树是否为空，  若不为空  输出数据   递归调用自身 
    	printTree(T->lchild);  
    	cout<<T->data<<endl;
    	printTree(T->rchild);
    	}
    }

我们会发现，二叉排序树既然能够有序的输出元素， 与折半查找有异曲同工之妙。我们在二叉排序树中的查找又该怎么去实现呢，其实非常简单，我们只需要按照查找的值与访问结点的值比较来确定值的位置即可，代码 如下

//二叉排序树中的查找操作
    treeNode *search(Tree &T,int data){
        
    	treeNode *p = T;
    	while(p!=NULL && p->data != data){
        
    		if(data < p->data) p=p->lchild;
    		else p=p->rchild;
    	}
    	return p;
    }

虽然不用递归完全可以实现，但是使用递归的方式也可以实现 代码如下

//也可以使用递归的方法进行查找
    treeNode *searchDG(Tree &T,int data){
        
    	treeNode *p = T;
    	if(p == NULL){
        
    		return NULL;
    	}
    	if(p->data == data){
        
    		return p;
    	}
    	if(data < p->data)
    	searchDG(p->lchild,data);
    	else
    	searchDG(p->rchild,data);
    }

其实我觉得只是在遍历之前加了一些判断条件而已  
**接下来我们进行二叉排序树中删除结点的操作**（这个比较繁琐，因为删除结点的同时不破坏二叉排序树的结构会有三种情况）  
**如下图第一种情况：删除结点只有**左孩子**或者**右孩子一个节点  
我们会发现只需要将删除结点的孩子结点代替删除结点便能够恢复二叉排序树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 1]**第二种情况，** 删除结点如果是叶子节点，那么不需要做任何的改动，二叉排序树的性质依旧全部满足。  
**第三种情况**删除的结点**同时**具有左右孩子结点，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 2]上图所示的二叉树删除78结点，使用左右孩子 结点代替删除结点都可以，但是如果是下图所示的情况  
![在这里插入图片描述][20201010171326905.png_pic_center]我们会发现，使用左右孩子代替均不能够满足二叉排序树的性质，那么我们来思考，如果想要继续满足性质的话，我们应该使用的是右子树的最小值来进行代替删除结点 也就是中序遍历的第一个结点。  
修改之后的树形结构如下所示。  
![在这里插入图片描述][20201010171722759.png_pic_center]实现代码如下

int Delete(Tree &T){
        
    	treeNode *temp , *pre;
    	if(T->rchild == NULL)  //如果删除结点的右孩子为空  //同时兼顾叶子节点的删除 
    	{
        
    		temp = T;
    		T=T->lchild;
    		delete(temp);
    	 }
    	 else if(T->lchild == NULL){
         //如果删除的结点的左孩子为空 
    	 	temp = T;
    	 	T = T->rchild;
    	 	delete(temp);
    	 }
    	 else    //要删除的结点同时有左右孩子 
    	 {
        
    		temp = T->rchild;    //temp指向要删除结点的右子树 
    		pre = temp;    //初始化时，pre指向temp 
    		while(temp->lchild!=NULL){
           //将temp修改到 右子树的最小结点 
    			pre = temp;    //pre指向temp最近一次访问的结点 
    			temp = temp->lchild;   
    		}
    		T->data = temp->data;   //将删除结点的数据修改为 最小结点的数据 
    		if(temp == pre)    //如果temp与pre指向用一个结点 （因为当删除结点的右子树没有左孩子的时候，temp与pre指向同一个结点，此时直接将temp的右子树接上去即可） 
    		{
        
    			T->rchild = temp->rchild;    
    		}else{
            //当删除结点的左孩子结点不为空的时候，需要在将最小结点的右子树接到最近访问的结点的左子树（也就是pre） 
    			pre->lchild = temp->rchild;
    		}
    		delete temp;   //删除多余的最小结点 
    	 }
    	 return 1;
    }
    int deleteNode(Tree &T,int data){
        
    	if(T==NULL)   //当树为空的时候，删除失败 
    	{
        
    		return 0;
    	}else{
         
    		if(data == T->data){
           //寻找到了删除结点的位置，调用删除方法 
    			Delete(T);
    		}
    		else if(data < T->data){
           //递归寻找左子树 
    			deleteNode(T->lchild,data);
    		}else{
        
    			deleteNode(T->rchild,data);  //递归寻找右子树 
    		}
    	}
    }

**详解：**  
deleteNode方法其实是为了寻找要删除结点的位置，寻找到之后将结点指针传入Delete方法。（与遍历有些相似）  
当找到了删除结点的位置开始执行Delete方法。  
删除结点只有一个子孩子，或者直接为叶子节点的时候，直接删除就好 理解起来比较简单。  
下面我们主要来说一下删除结点同时具有左右孩子的情况。

以删除78结点为例：  
1.刚开始进入方法，经过判断后，进入最后一个else。  
此时 T指针指向删除结点。  
temp指针指向删除结点的右孩子  
pre初始化的时候也会指向temp  
当temp指向的结点有左孩子的时候，说明temp现在指向的结点不是中序遍历的第一个结点（也就相当于不是最小值）  
此时我们调用while循环![在这里插入图片描述][20201010210825627.png_pic_center]利用排序树的性质来寻找删除结点的右子树的最下结点。  
而temp此时始终指向，temp最近访问的结点（作用就是为了在删除最小结点的时候能够将最小结点的子树接上pre指针指向的结点）  
寻找到最小结点之后，将最小结点复制到要删除的结点，  
![在这里插入图片描述][20201010211057413.png_pic_center]再进行嫁接，将最小节点的子树与之前的树相连。  
![在这里插入图片描述][2020101021113657.png_pic_center]只有当删除结点的右子树不具有左孩子的时候，才会出现temp与pre指向相同结点的情况，这时直接将最小结点的子树与删除结点的右孩子相连即可

else中，将最近访问结点的左指针域指向最小结点的右子树即可

最后删除多余的最小结点。  
结束删除、调整操作。

模拟一遍执行流程也不是特别的难

最后给大家贴上全部的代码：

#include <iostream>
    using namespace std;
    typedef struct treeNode{
           //二叉树的存储结构 
    	int data;
    	treeNode *lchild,*rchild;
    }*Tree;
    
    int insertTree(Tree &T,int data){
        	//插入节点的方法 
    	if(T == NULL){
        
    		T = new treeNode;    //初始化根节点 
    		T->lchild = NULL;
    		T->rchild = NULL;
    		T->data = data;
    		return 1;
    	}
    	else if(data == T->data){
           //如果data与某一个数据相同，插入失败 
    		return 0;
    	}else if(data < T->data){
           //如果data小于根节点的值 插入左子树 
    		insertTree(T->lchild,data); //递归依次进行结点的找寻 
    	}else{
             
    		insertTree(T->rchild,data);   
    	}
    }
    
    void createTree(Tree &T){
           //创建二叉树 
    	int data = 0;    //初始化data为0 
    	T = NULL;        //根节点初始化时指向空 
    	while(data != -1){
           //输入-1的时候  代表输入结束 
    		cin >> data;    //输入数据 
    		if(data!=-1)    //防止结束的时候将-1节点作为数据插入二叉树 
    		insertTree(T,data);   //调用插入二叉树的方法 
    	}
    }
    //中序遍历输出各个节点的值 
    void printTree(Tree &T){
        
    	if(T){
            //判断树是否为空，  若不为空  输出数据   递归调用自身 
    	printTree(T->lchild);  
    	cout<<T->data<<endl;
    	printTree(T->rchild);
    	}
    }
    //二叉排序树中的查找操作
    treeNode *search(Tree &T,int data){
        
    	treeNode *p = T;
    	while(p!=NULL && p->data != data){
        
    		if(data < p->data) p=p->lchild;
    		else p=p->rchild;
    	}
    	return p;
    }
    //也可以使用递归的方法进行查找
    treeNode *searchDG(Tree &T,int data){
        
    	treeNode *p = T;
    	if(p == NULL){
        
    		return NULL;
    	}
    	if(p->data == data){
        
    		return p;
    	}
    	if(data < p->data)
    	searchDG(p->lchild,data);
    	else
    	searchDG(p->rchild,data);
    }
    
    int Delete(Tree &T){
        
    	treeNode *temp , *pre;
    	if(T->rchild == NULL)  //如果删除结点的右孩子为空  //同时兼顾叶子节点的删除 
    	{
        
    		temp = T;
    		T=T->lchild;
    		delete(temp);
    	 }
    	 else if(T->lchild == NULL){
         //如果删除的结点的左孩子为空 
    	 	temp = T;
    	 	T = T->rchild;
    	 	delete(temp);
    	 }
    	 else    //要删除的结点同时有左右孩子 
    	 {
        
    		temp = T->rchild;    //temp指向要删除结点的右子树 
    		pre = temp;    //初始化时，pre指向temp 
    		while(temp->lchild!=NULL){
           //将temp修改到 右子树的最小结点 
    			pre = temp;    //pre指向temp最近一次访问的结点 
    			temp = temp->lchild;   
    		}
    		T->data = temp->data;   //将删除结点的数据修改为 最小结点的数据 
    		if(temp == pre)    //如果temp与pre指向用一个结点 （因为当删除结点的右子树没有左孩子的时候，temp与pre指向同一个结点，此时直接将temp的右子树接上去即可） 
    		{
        
    			T->rchild = temp->rchild;    
    		}else{
            //当删除结点的左孩子结点不为空的时候，需要在将最小结点的右子树接到最近访问的结点的左子树（也就是pre） 
    			pre->lchild = temp->rchild;
    		}
    		delete temp;   //删除多余的最小结点 
    	 }
    	 return 1;
    }
    int deleteNode(Tree &T,int data){
        
    	if(T==NULL)   //当树为空的时候，删除失败 
    	{
        
    		return 0;
    	}else{
         
    		if(data == T->data){
           //寻找到了删除结点的位置，调用删除方法 
    			Delete(T);
    		}
    		else if(data < T->data){
           //递归寻找左子树 
    			deleteNode(T->lchild,data);
    		}else{
        
    			deleteNode(T->rchild,data);  //递归寻找右子树 
    		}
    	}
    }
    
    
    int main()
    {
        
    	Tree T;
    	createTree(T);
    	printTree(T);
    	int sea;
    	cout<<"请输入要查找结点的值"<<endl;
    	cin >> sea; 
    	treeNode *res = searchDG(T,sea);
    	if(res!=NULL){
        
    		cout<<"查找成功！"<<endl;
    	}else{
        
    		cout<<"查找失败！"<<endl;
    	}
    	int data;
    	cout<<"请输入要删除的结点值"<<endl;
    	cin >> data;
    	int flag = deleteNode(T,data);
    	if(flag == 1){
        
    		cout<<"删除成功"<<endl;
    		printTree(T);
    	}else
    	{
        
    		cout << "删除失败！"<<endl;
    	}
    	return 0;
     }

至于平衡二叉树的话 主要难点在于删除 和 平衡性的调整  
在这里给大家推荐一个哔哩哔哩up猪  
https://www.bilibili.com/video/BV1xE411h7dd?from=search&seid=9001484221261281045

[20201010000324669.png_pic_center]: /images/20221123/48f453c7060f4cd9aa595e22855fe637.png
[20201010005311822.png_pic_center]: /images/20221123/1ad53dfccc6f4ffe944073a2e3783b49.png
[20201010005651920.png_pic_center]: /images/20221123/8ffbaf563780490588fe013bb7e50333.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/2ea1527656cc46ea8862d1df7e478e1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/83faa8a4f5644fc394fc073f204f45e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/02f384d1b4854bc8a0761e5c41e4944d.png
[20201010171326905.png_pic_center]: /images/20221123/2caaa6e3eec24e8c96c64b2e9864c20c.png
[20201010171722759.png_pic_center]: /images/20221123/3568f3106e424a62a871ce5fb64e802b.png
[20201010210825627.png_pic_center]: /images/20221123/29a51cd8c60e434f944395f03ea993b1.png
[20201010211057413.png_pic_center]: /images/20221123/74c45972828547ae8f283f98f12fb432.png
[2020101021113657.png_pic_center]: /images/20221123/3bc55c045ad54daeac78624a7c6c4228.png