407-BST树讲解大全(下)

落日映苍穹つ 2022-09-04 07:53 135阅读 0赞

## BST树区间元素搜索问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**比如说，寻找10-70之间的所有元素**

**方法1：** 遍历1遍，符合的打印出来。但是效率不高。

**方法2：**  
利用**中序遍历**的升序的特点。

//求满足区间的元素值[i, j]
    void findValues(vector<T>& vec, int i, int j)
    {
        
    	findValues(root_, vec, i, j);
    }
    
    //求满足区间的元素值[i, j]实现
    void findValues(Node* node, vector<T>& vec, int i, int j)
    {
        
    	if (node != nullptr)
    	{
        
    		//在当前节点的左子树中搜索 LVR的方式，中序遍历
    		if (node->data_ > i)//比i小就不用去左子树搜索了
    		{
        
    			findValues(node->left_, vec, i, j);//执行L
    		}
    
    		if (node->data_ >= i && node->data_ <= j)//执行V
    		{
        
    			vec.push_back(node->data_);//存储满足区间元素的值
    		}
    
    		//在当前节点的右子树中搜索
    		if (node->data_ < j)//比j大就不用去右子树搜索了
    		{
        
    			findValues(node->right_, vec, i, j);//执行R
    		}
    	}
    }

## 判断一棵树是不是BST树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**要考虑到上图这种情况来实现代码**

**利用BST树的中序遍历是从小到大升序的思想**

//判断二叉树是否是BST树
    bool isBSTree()
    {
        
    	Node* pre = nullptr;//用来记录中序遍历前一个节点的值，一直要更新的
    	return isBSTree(root_, pre);
    }
    
    //判断二叉树是否是BST树的实现 利用BST树中序遍历是一个升序的特点
    bool isBSTree(Node* node, Node*& pre)
    {
        
    	if (node == nullptr)//都没有出过错
    	{
        
    		return true;
    	}
    
    	if (!isBSTree(node->left_, pre))//L主要判断使递归结束的条件
    	//当前节点的左子树已经不满足BST性质了，就不考虑右子树了
    	{
        
    		return false;
    	}
    	//V
    	if (pre != nullptr)
    	{
        
    		if (comp_(node->data_, pre->data_))
    		//当前节点的值小于前一个节点的值。主要判断使递归结束的条件
    		{
        
    			return false;
    		}
    	}
    	pre = node;//更新中序遍历的前驱节点
    
    	return isBSTree(node->right_, pre);//R //直接返回回去
    
    }

## 判断二叉树子树问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**判断下面这个小树是不是上面这棵大树的子树**  
![在这里插入图片描述][059198dfeafb47fd80275cae4fc7fc54.png]  
先在大树中找到这个小树的根节点67  
然后大树和小树同时往左走往右走遍历  
遍历到的值必须是相同的  
大树里的可以多，但不能少。

//判断子树问题
    bool isChildTree(BSTree<T, Comp>& child)
    {
        
    	// 在当前二叉树上找child的根节点
    	if (child.root_ == nullptr)
    	{
        
    		return true;
    	}
    
    	Node* cur = root_;
    	while (cur != nullptr)
    	{
        
    		if (cur->data_ == child.root_->data_)//树的节点与子树的根节点值相等
    		{
        
    			break;
    		}
    		else if (comp_(cur->data_, child.root_->data_))//当前节点的值小于子树的根节点的值
    		{
        
    			cur = cur->right_;
    		}
    		else//当前节点的值大于子树的根节点的值
    		{
        
    			cur = cur->left_;
    		}
    	}
    	if (cur == nullptr)
    	{
        
    		return false;//没有找到子树的根，不匹配
    	}
    	return isChildTree(cur, child.root_);
    }
    
    //判断子树问题实现
    bool isChildTree(Node* father, Node* child)
    {
        
    	if (father == nullptr && child == nullptr)
    	{
        
    		return true;
    	}
    
    	if (father == nullptr)//子树里面有的节点，当前二叉树没有
    	{
        
    		return false;
    	}
    
    	if (child == nullptr)
    	{
        
    		return true;
    	}
    
    	//判断值不相同
    	if (father->data_ != child->data_)// V 对应的值不相同
    	{
        
    		return false;
    	}
    
    	return isChildTree(father->left_, child->left_)// L 左右孩子同时进行判断
    		&& isChildTree(father->right_, child->right_);// R
    }

## 求LCA最近公共祖先节点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
**比如说**24和67，最近公共祖先节点就是58，  
34和62，最近公共祖先节点就是58  
5和41的最近公共祖先节点就是24  
62和64的最近公共祖先节点就是62

**怎么判断5和41的最近公共祖先节点是24，而不是58？**  
我们看，5和41都比58小，说明都在58的左子树，58就肯定不是它们的最近公共祖先节点。  
**所以说：最近公共祖先节点肯定是大于一个数而小于另一个数。**

**当搜索的时候值等于要比较的节点值，就是在一条分枝上。**

//最近公共祖先节点
    int getLCA(int val1, int val2)
    {
        
    	Node* node = getLCA(root_, val1, val2);
    	if (node == nullptr)//没找到
    	{
        
    		throw "no LCA!";
    	}
    	else
    	{
        
    		return node->data_;
    	}
    }
    
    //最近公共祖先节点实现
    Node* getLCA(Node* node, int val1, int val2)
    {
        
    	if (node == nullptr)
    	{
        
    		return nullptr;
    	}
    
    	if (comp_(node->data_, val1) && comp_(node->data_, val2))//当前节点的值小于val1和val2
    	{
        
    		return getLCA(node->right_, val1, val2);
    	}
    	else if (comp_(val1, node->data_) && comp_(val2, node->data_))//当前节点的值大于val1和val2
    	{
        
    		return getLCA(node->left_, val1, val2);
    	}
    	else//一个大于一个小于。就是最近公共祖先节点。
    	{
        
    		return node;
    	}
    }

## 二叉树镜像翻转问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**相当于有一面镜子**  
**翻转。**  
78就是在最左边  
0就是在最右边

**相当于根节点进行遍历，把左右的节点交换就可以了。**

//镜像翻转
    void mirror01()
    {
        
    	mirror01(root_);
    }
    //镜像翻转
    void mirror01(Node* node)
    {
        
    	if (node == nullptr)
    		return;
    	//前序遍历
    	//V
    	Node* tmp = node->left_;
    	node->left_ = node->right_;
    	node->right_ = tmp;//交换节点
    
    	mirror01(node->left_);//L操作
    	mirror01(node->right_);//R操作
    }

**照镜子，镜子里的二叉树的中序遍历就是降序的了。**  
![在这里插入图片描述][54c2363aed99441e969bf1bc521fbe11.png]

## 二叉树的镜像对称 ##

**就是在根节点放一面镜子**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**看左子树和右子树是不是对称，就是左右对应节点的值相等不相等。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]

//镜像对称
    bool mirror02()
    {
        
    	if (root_ == nullptr)
    		return true;
    	return mirror02(root_->left_, root_->right_);
    }
    //镜像对称
    bool mirror02(Node* node1, Node* node2)
    {
        
    	if (node1 == nullptr && node2 == nullptr)
    	{
        
    		return true;
    	}
    	if (node1 == nullptr || node2 == nullptr)
    	{
        
    		return false;
    	}
    	if (node1->data_ != node2->data_)
    	{
        
    		return false;
    	}
    	return mirror02(node1->left_, node2->right_)
    		&& mirror02(node1->right_, node2->left_);
    }

## 已知BST树的前序遍历和中序遍历，重建BST树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]

![在这里插入图片描述][83d9bef9c2f2459cbe1e6076f45ef83d.png]  
**前序遍历是VLR，中序遍历是LVR，  
所以说  
前序遍历的第一个数字58就是根节点！！！**  
但是58的左子树和右子树都有哪些节点？  
**中序遍历的58的左边数字就是根节点的左子树，58的右边数字就是根节点的右子树**

我们拿前序遍历的第一个数字i，**58，也就是根节点。**  
然后拿这个数值去中序遍历里面找。第k个位置。  
**m到k-1就是根节点58的左子树的节点**  
![在这里插入图片描述][5fcaa019592f4a5ba599be7689f95e0b.png]  
**根节点的左子树的节点个数**：k-m

**那58的左子树的前序遍历是什么呢？**  
58的左子树的前序遍历的下标就是从i+1开始到 i+（k-m）  
那它们的根就是下标为i+1的元素，即24  
然后拿24在中序遍历里找。  
24的左边就是它的左子树。就是 0,5  
右子树就是34,41

**创建根的右子树就是从k+1到n**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]

//重建二叉树
    void rebuild(int pre[], int i, int j, int in[], int m, int n)//前序，中序，起始，末尾下标
    {
        
    	root_ = _rebuild(pre, i, j, in, m, n);
    }
    //重建二叉树递归实现
    Node* _rebuild(int pre[], int i, int j, int in[], int m, int n)
    {
        
    	if (i > j || m > n)//已经遍历完了
    	{
        
    		return nullptr;
    	}
    
    	//创建当前子树的根节点
    	Node* node = new Node(pre[i]);//拿前序的第一个数字创建子树根节点 V
    	for (int k = m; k <= n; ++k)
    	{
        
    		if (pre[i] == in[k])//在中序遍历中找子树根节点的下标k
    		{
        
    			node->left_ = _rebuild(pre, i + 1, i + (k - m), in, m, k - 1);// L
    			node->right_ = _rebuild(pre, i + (k - m) + 1, j, in, k + 1, n);// R
    			return node;
    		}
    	}
    	return node;
    }

## 判断一棵BST树是否是平衡树 ##

**任意节点的左右子树的高度差不超过1（0,1，-1）**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

在回溯的时候检测，比较好。  
LRV

//判断平衡树
    bool isBalance()
    {
        
    	int l = 0;
    	bool flag = true;
    	isBalance02(root_, l, flag);
    	return flag;
    }
    
    //判断平衡树 效率比较低，遍历的次数太多了
    bool isBalance(Node* node)
    {
        
    	if (node == nullptr)
    		return true;
    	if (!isBalance(node->left_))//L
    		return false;
    	if (!isBalance(node->right_))//R
    		return false;
    
    	int left = high(node->left_);
    	int right = high(node->right_);
    	return abs(left - right) <= 1;//V
    }
    
    //判断平衡树 效率高 递归过程中，记录了节点的高度值 ，返回节点高度值
    int isBalance02(Node* node, int l, bool& flag)
    {
        
    	if (node == nullptr)
    	{
        
    		return l;
    	}
    
    	int left = isBalance02(node->left_, l + 1, flag);//L
    	if (!flag)
    		return left;
    	int right = isBalance02(node->right_, l + 1, flag);//R
    	if (!flag)
    		return right;
    
    	//V
    	if (abs(left - right) > 1)//节点失衡了
    	{
        
    		flag = false;
    	}
    	return max(left, right);
    }

## 求中序遍历倒数第k个节点 ##

**中序遍历：LVR**  
**我们用RVL就是正数第k个**

//求中序倒数第K个节点
    int getVal(int k)
    {
        
    	Node* node = getVal(root_, k);
    	if (node == nullptr)
    	{
        
    		string err = "no No.";
    		err += k;
    		throw err;
    	}
    	else
    	{
        
    		return node->data_;
    	}
    }
    
    //求中序倒数第K个节点
    int i = 1;
    Node* getVal(Node* node, int k)
    {
        
    	if (node == nullptr)
    		return nullptr;
    
    	Node* left = getVal(node->right_, k); // R
    	if (left != nullptr)
    		return left;
    	//V
    	if (i++ == k)//在VRL的顺序下，找到正数第k个元素
    	{
        
    		return node;
    	}
    	return getVal(node->left_, k);//L
    }

## BST树的析构函数 ##

//层序遍历思想释放BST树所有节点资源
    ~BSTree()//析构函数 
    {
        
    	if (root_ != nullptr)
    	{
        
    		queue<Node*> s;//队列
    		s.push(root_);//根节点入队
    		while (!s.empty())//模拟层序遍历删除节点
    		{
        
    			Node* front = s.front();//获取队头
    			s.pop();//出队
    
    			if (front->left_ != nullptr)
    			{
        
    				s.push(front->left_);
    			}
    			if (front->right_ != nullptr)
    			{
        
    				s.push(front->right_);
    			}
    			delete front;
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/7c08c4ddad64429496655c6b43b6c709.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/dff732a9e61c488fb1ea08754cf0d182.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/be5e36a5703d42aca038415495be1d1a.png
[059198dfeafb47fd80275cae4fc7fc54.png]: /images/20220829/4b0555d36be940caa12518a9c81fa46e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/06bfb27c091b4e5aa53660cf99422c0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/fe8904a3dac245a0a63558e918598146.png
[54c2363aed99441e969bf1bc521fbe11.png]: /images/20220829/bc88d75926a740e4a9263096f6d1dda1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/2fb7398b81704ceda059276293c98fa0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20220829/269b04dcc86b4e5fa7240ba1ba783861.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]: /images/20220829/258160f19fc34fd095fff155fd6b3618.png
[83d9bef9c2f2459cbe1e6076f45ef83d.png]: /images/20220829/b0bec695d45d4082bc696f057aabd068.png
[5fcaa019592f4a5ba599be7689f95e0b.png]: /images/20220829/992176d9612846308ff92500450dbbba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]: /images/20220829/3b295ab75bc94197b5194a69aa095d66.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a9b0115da23a4372b06e27167bb8d38e.png