258-二叉排序树(BST树)

分手后的思念是犯贱 2022-10-22 04:29 153阅读 0赞

## 二叉排序树(BST树) ##

**又叫二叉搜索树**  
![在这里插入图片描述][20210404105558534.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

## 堆的图解如下 ##

以完全二叉树来组织，用于优先级队列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]

## 二叉排序树的定义 ##

#include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    typedef int KeyType;
    typedef struct BstNode
    {
        
    	KeyType key;
    	BstNode* leftchild;
    	BstNode* parent;
    	BstNode* rightchild;
    }BstNode, * BSTree;

## 二叉排序树的查询 ##

我们首先查询根节点，如果相等，就返回根节点，如果不相等，如果小于根节点，跑到根节点的左边去找；如果大于根节点，跑到根节点的右边去找。  
如果左边找不到，不用回到右边去找。  
因为根节点大于左子树的所有关键码，小于右子树的所有关键码。

**非递归写法：**

BstNode* FindValue(BstNode * ptr, KeyType kx)
    {
        
    	while (ptr != nullptr && ptr->key != kx)
    	{
        
    		ptr = kx < ptr->key ? ptr->leftchild : ptr->rightchild;
    	}
    	return ptr;
    }

**递归写法：**

BstNode* SearchValue(BstNode* ptr, KeyType kx)
    {
        
    	if (ptr == nullptr || ptr->key == kx)
    		return ptr;
    	else if (kx < ptr->key)
    		return SearchValue(ptr->leftchild, kx);
    	else
    		return SearchValue(ptr->rightchild, kx);
    }

## 二叉排序树的插入 ##

下面这种传参的形式是错误的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
**这里的ptr指向结点，不能带动root指向结点，因为都是一级指针。**

**正确代码如下：**  
先建立根节点。pa指向双亲，p指向当前结点。

BstNode* Buynode(KeyType kx)
    {
        
    	BstNode* s = (BstNode*)malloc(sizeof(BstNode));
    	if (nullptr == s) exit(1);
    	memset(s, 0, sizeof(BstNode));
    	s->key = kx;
    	return s;
    }
    bool Insert(BstNode *&ptr,KeyType kx)//注意是要用引用的形式！ 
    {
        
    	if (ptr == nullptr)
    	{
        
    		ptr = Buynode(kx);
    		return true;
    	}
    	BstNode* pa = nullptr;
    	BstNode* p = ptr;
    	while (p != nullptr && p->key != kx)
    	{
        
    		pa = p;
    		p = kx < p->key ? p->leftchild : p->rightchild;
    	}
    	if (p != nullptr && p->key == kx) return false;
    	p = Buynode(kx);//购买节点 
    	p->parent = pa;
    	if (p->key < pa->key)
    	{
        
    		pa->leftchild = p;
    	}
    	else
    	{
        
    		pa->rightchild = p;
    	}
    	return true;
    }

**二级插入：**

bool Insert(BstNode*& ptr, KeyType kx)
    {
        
    	BstNode* pa = nullptr;
    	BstNode* p = ptr;
    	while (p != nullptr && p->key != kx)
    	{
        
    		pa = p;
    		p = kx < p->key ? p->leftchild : p->rightchild;
    	}
    	if (p != nullptr && p->key == kx) return false;
    	p = Buynode(kx);
    	p->parent = pa;
    	if (pa == nullptr)
    	{
        
    		ptr = p;
    	}
    	else
    	{
         
    		if (p->key < pa->key)
    		{
        
    			pa->leftchild = p;
    		}
    		else
    		{
        
    			pa->rightchild = p;
    		}
    	}
    	return true;
    }

## 二叉排序树的中序遍历 ##

void InOrder(BstNode* ptr)
    {
        
    	if (ptr != nullptr)
    	{
        
    		InOrder(ptr->leftchild);
    		cout << ptr->key << " ";
    		InOrder(ptr->rightchild);
    	}
    }

int main()
    {
        
    	BSTree root = nullptr;
    	vector<int> ar = {
         53,17,78,9,45,65,87,23,81,94,88,92 };
    	for (auto& x : ar)
    	{
        
    		Insert(root, x);
    	}
    
    	InOrder(root);
    	cout << endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
**二叉排序树的中序遍历是从小到大的！！！**

## 如何判断是不是二叉排序树 ##

和前一个结点进行比较。按照中序遍历进行比较。如果前驱结点大于当前结点，就不是二叉排序树。

bool Is_BST(BstNode* ptr)
    {
        
    	bool res = true;
    	if (ptr == nullptr) return res;
    	BstNode* pre = nullptr;
    	std::stack<BstNode*> st;//定义栈 
    	while (ptr != nullptr || !st.empty())
    	{
        
    		while (ptr != nullptr)
    		{
        
    			st.push(ptr);
    			ptr = ptr->leftchild;
    		}
    		ptr = st.top(); st.pop();//取栈顶，然后出栈 
    		if (pre != nullptr && pre->key >= ptr->key)
    		{
        
    			res = false;
    			break;
    		}
    		pre = ptr;//记录双亲 
    		ptr = ptr->rightchild;//指向右子树 
    	}
    	return res;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
程序分析：最开始的时候，我们的ptr指向根节点，res初始化为真，我们定义一个前驱指针pre，初始化为空，进入while循环，我们首先把53结点入栈，然后把17和9结点入栈，然后为空了，把9结点出栈，pre为空，不进入，把ptr给pre，即指向9结点，ptr指向右边，为空了，再出栈，即出17结点，然后pre不为空，9<17，pre指向17，ptr指向45。以此类推。

## 二叉排序树的删除 ##

有如下情况：  
**1、root是空的  
2、删除的是不存在的结点  
3、找到之后，（1）删除叶子  
（2）删除的是单分枝（把双亲找到，指向删除结点的孩子）  
（3）删除的是双分枝（如果我们把78删掉，85和67都会争夺这个位置，我们找到78的直接后继81，81覆盖78，删除之前的81位置，保证了删除之后仍然是中序遍历，从小到大有序，或者也可以找它的直接前驱，81不可能有双分枝，如果有，78的直接后继就不是81了。78的直接后继是最左边的）**  
**（4）根节点的右边删完了。要动根节点**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]

void Freenode(BstNode* p)//释放结点 
    {
        
    	free(p);
    }
    BstNode* Prev(BstNode* ptr)//查找直接前驱 
    {
        
    	while (ptr != nullptr && ptr->rightchild != nullptr)
    	{
        
    		ptr = ptr->rightchild;
    	}
    	return ptr;
    }
    BstNode* Next(BstNode* ptr)//查找直接后继 （最左端） 
    {
        
    	while (ptr != nullptr && ptr->leftchild != nullptr)
    	{
        
    		ptr = ptr->leftchild;
    	}
    	return ptr;
    }
    bool Remove(BstNode*& ptr, KeyType kx)//删除函数 
    {
        
    	bool res = false;
    	if (ptr == nullptr) return res;
    	BstNode* p = ptr;
    	while (p != nullptr && p->key != kx)
    	{
        
    		p = kx < p->key ? p->leftchild : p->rightchild;
    	}
    	if (p == nullptr) return false;//找不到
    	
    	if (p->leftchild != nullptr && p->rightchild != nullptr)//解决双分枝 
    	{
        
    		BstNode* nt = Next(p->rightchild);//找直接后继 
    		p->key = nt->key;
    		p = nt;//接下去要删除nt了
    	}
    	BstNode* pa = p->parent;
    
    	BstNode* child = p->leftchild != nullptr ? p->leftchild : p->rightchild;
    	if (child != nullptr) child->parent = pa;
    	
    	if (pa == nullptr)//要动根节点了 (单分枝) 
    	{
        
    		ptr = child;//直接指向叶子，重置根
    	}
    	else
    	{
        
    		if (pa->leftchild == p)
    		{
        
    			pa->leftchild = child;
    		}
    		else
    		{
        
    			pa->rightchild = child;
    		}
    	}
    	Freenode(p); p = nullptr;
    	return true;
    }
    
    int main()//主函数 
    {
        
    	BSTree root = nullptr;
    	vector<int> ar = {
         53,17,78,9,45,65,87,23,81,94,88,92 };
    	for (auto& x : ar)
    	{
        
    		Insert(root, x);
    	}
    	InOrder(root);
    	cout << endl;
    	int x;
    	while (cin >> x, x != -1)
    	{
        
    		Remove(root, x);
    		InOrder(root);
    		cout << endl;
    	}
    	return 0;
    }

[20210404105558534.png_pic_center]: /images/20221022/dd8a1efc51344ef38ad6a6ed864bcbf0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/73c7eb2a213643b095013e7c47fb7e63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/89cfb6e2e74b4dd29803867e8ec279a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/86fbff530c7e42e193eb4a73ed653f9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/9b0d1a8912b745cda33409c5a829fa61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/1e0fe76f9f9f473281ef7ff86dc300df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/b70c1c84b2d04e4dbfb6533bb2dafc0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/029084f1100d461da4b9c649b09ba85a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221022/6e9b9c800a76493782cf4368e1ce04da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221022/6d87d753e01e4250a4e97cf15a56110e.png