C++高级数据结构算法#二叉搜索树(BST树)的基本操作(递归与非递归)

今天药忘吃喽~ 2022-01-14 13:41 214阅读 0赞

### 文章目录 ###

*   *   *  二叉搜索树
         *  二叉搜索树的结构定义
         *  BST树插入操作
         *   *  非递归操作
             *  递归操作
         *  BST树删除操作
         *   *  非递归操作
             *  递归操作
         *  BST树查找操作
         *   *  非递归操作
             *  递归操作
         *  BST树相关的经典题目
         *   *  BST树的镜像翻转(递归实现)
             *  返回BST树所有节点的个数(递归实现)
             *  返回BST树的层数/高度(递归实现)
             *  判断当前二叉树是不是一颗BST树(递归实现)
             *  打印BST树中 , 区间\[first, last\]的所有元素(递归实现)
             *  获取两个节点的最近公共祖先节点(递归实现)
             *  获取中序遍历倒数第k个节点的值(递归实现)
             *  判断参数tree是否是当前BST树的一颗子树(递归实现)
             *  已知一棵BST树的前序遍历结果pre数组，和中序遍历结果in数组，重建二叉树(递归实现)
         *  完整代码

### 二叉搜索树 ###

**定义 :** **对于任意节点X , X的左子树中的每个节点的关键码均应小于节点X的关键码 , 而X的右子树中的每个节点的关键码均应大于节点X的关键码** . 满足上述条件的二叉树就是一棵二叉搜索树

### 二叉搜索树的结构定义 ###

template<typename T>
    class BSTree
    {
        
    public:
    	BSTree():_root(nullptr){
        }
    private:
    	// 定义BST树节点的类型
    	struct BSTNode
    	{
        
    		BSTNode(T data=T())
    			:_data(data)     //数据
    			,_left(nullptr)  //左孩子
    			,_right(nullptr) //右孩子
    		{
        }
    		T _data;
    		BSTNode *_left;
    		BSTNode *_right;
    	};
    	BSTNode *_root; // 指向树的根节点
    };

### BST树插入操作 ###

#### 非递归操作 ####

// 非递归实现BST树的插入操作
    	/*
    	寻找适合插入的位置 , 插入的数值先与根节点进行比较 , 大于则向右进入右子树 , 小于则向左进入左子树
    	如此循环 , 直到找到某个位置的左孩子(或右孩子)为空(nullptr) , 则说明找到这个地方
    	然后判断该节点大于(还是小于)父节点 , 即插在父节点的左孩子还是右孩子 , 最后将节点插入即可
    	*/
    	void noninsert(const T &val)
    	{
        
    		//先要判断插入的节点是不是根节点
    		if(_root == nullptr)
    		{
        
    			_root = new BSTNode(val);
    			return;
    		}
    		BSTNode* pre = nullptr; //记录父节点
    		BSTNode* node = _root;
    		//循环开始找位置
    		while(node != nullptr)
    		{
        
    			pre = node;
    			//向右
    			if(val > node->_data)
    			{
        
    				node = node->_right;
    				continue;
    			}
    			//向左
    			else if(val < node->_data)
    			{
         node = node->_left ; }
    			else
    			//等于说明已经有同一节点 , 不必再插入 ,返回即可
    			{
          return ; }
    		}
    		//判断插在父节点的左还是右
    		if(val < pre->_data)
    		{
         pre->_left = new BSTNode(val) ; }
    		else
    		{
         pre->_right = new BSTNode(val) ; }
    	}

#### 递归操作 ####

//递归实现BST的插入操作
    	void insert(const T &val)
    	{
        
    		this->insert(_root,val);
    	}

//递归实现插入操作
    	BSTNode* insert(BSTNode* node,int val)
    	{
        
    		//插入的是根节点
    		if(node == nullptr)
    		{
        			
    			return new BSTNode(val);
    		}
    		//进入右子树
    		if(val > node->_data)
    		{
        
    			node->_right = insert(node->_right,val);
    		}
    		//进入左子树
    		else if(val < node->_data)
    		{
        
    			node->_left = insert(node->_left,val);
    		}
    		//为啥?  插入之后的更新
    		return node;
    	}

### BST树删除操作 ###

#### 非递归操作 ####

// 非递归实现BST树的删除操作
    	/*
    	再从一棵二叉搜索树中删除一个节点之前必须先找到该节点所在的位置
    	删除操作往往会引起很多后果 , 主要来自两个方面 : 
    	一方面删除树中的一个节点必然会导致原本连通的树结构发生阻隔
    	其次 , 当二叉搜索树中的某个节点被删除之后 , 树中的有序关系可能遭到破坏
    
    	具体而言分为三种情况 : 
    	1.删除的节点没有孩子
    	2.删除的节点只有一个孩子
    	3.删除的节点有两个孩子
    	注 : 1和2可以看成是一种类型 , 只有一个孩子 , 这个孩子是空(nullptr)
    	情况三的处理方法 , 使用前驱结点或者后继节点代替该节点 , 删除前驱即可
    	前驱结点 : 当前节点的左子树中 , 元素的最大值
    	后继节点 : 当前节点的右子树中 , 元素的最小值
    
    	流程: 
    	1. 从_root开始寻找值为val的节点，cur指向它
    	2. 先判断是否满足情况3，如果满足，需要找cur的前驱节点，用前驱把cur节点的值给覆盖掉，直接删前驱
    	3. 删除情况1和情况2   直接删除cur指针指向的节点就可以了
    	*/
    	void nonremove(const T &val)
    	{
        
    		// 1. 从_root开始寻找值为val的节点，cur指向它
    		BSTNode *pre = nullptr;  //记录父节点
    		BSTNode *cur = _root;
    		while(cur != nullptr)
    		{
        
    			if(val < cur->_data)
    			{
        
    				pre = cur;
    				cur = cur->_left;
    			}
    			else if(val > cur->_data)
    			{
        
    				pre = cur;
    				cur = cur->_right;
    			}
    			else
    			{
        
    				break;
    			}
    		}
    		//判断找没找到
    		if(cur == nullptr)
    			return;
    
    		// 2. 先判断是否满足情况3，如果满足，需要找cur的前驱节点，用前驱把cur节点的值给覆盖掉，直接删前驱
    		if(cur->_left != nullptr && cur->_right != nullptr)
    		{
        
    			BSTNode *old = cur;
    			pre = cur;
    			//找前驱
    			cur = cur->_left;
    			while(cur->_right != nullptr)
    			{
        
    				pre = cur;
    				cur = cur->_right;
    			}
    			//用前驱覆盖被删除节点
    			old->_data = cur->_data;
    		}
    		// 3. 删除情况1和情况2   直接删除cur指针指向的节点就可以了
    		BSTNode *child = cur->_left;
    		if(child == nullptr)
    		{
        
    			child = cur->_right;
    		}
    
    		if(pre == nullptr) // cur指向的根节点
    		{
        
    			_root = child;
    		}
    		else
    		{
        
    			// 要把删除节点的孩子赋给cur父节点相应的地址域里面
    			if(cur == pre->_left)
    			{
        
    				pre->_left = child;
    			}
    			else
    			{
        
    				pre->_right = child;
    			}
    		}
    		delete cur;
    	}

#### 递归操作 ####

//递归实现BST树的删除操作
    	void remove(const T &val)
    	{
        
    		_root = remove(_root,val);
    	}

//递归实现删除操作
    	BSTNode* remove(BSTNode* node , int val)
    	{
        
    		if(node == nullptr)
    			return nullptr;
    		//查找被删除节点
    		if(val > node->_data)
    		{
        
    			node->_right = remove(node->_right,val);
    		}
    		else if(val < node->_data)
    		{
        
    			node->_left = remove(node->_left,val);
    		}
    		else
    		{
        
    			//判断是否满足情况3
    			if(node->_left != nullptr && node->_right != nullptr)
    			{
        
    				//找前驱节点
    				BSTNode* pre = node->_left;
    				while(pre->_right != nullptr)
    				{
        
    					pre = pre->_right;
    				}
    				node->_data = pre->_data;
    				//寻找前驱 , 直接删除前驱 
    				node->_left = remove(node->_left,pre->_data);
    			}
    			else
    			{
        
    				//情况2
    				if(node->_left != nullptr)
    				{
        
    					BSTNode* left = node->_left;
    					delete node;
    					return left;
    				}
    				else if(node->_right != nullptr)
    				{
        
    					BSTNode* right = node->_right;
    					delete node;
    					return right;
    				}
    				else
    				{
        
    					//情况1
    					delete node;
    					return nullptr;
    				}
    			}
    		}
    		//更新节点信息
    		return node;
    	}

### BST树查找操作 ###

#### 非递归操作 ####

//实现BST树查找指定的元素值val是否存在
    	bool nonquery(const T &val) 
    	{
        
    		if(_root == nullptr)
    		{
        
    			return false;
    		}
    		BSTNode* node = _root;
    		while(node != nullptr)
    		{
        
    			if(val > node->_data)
    			{
        
    				node = node->_right;
    			}
    			else if(val < node->_data)
    			{
        
    				node = node->_left;
    			}
    			else
    			{
        
    				return true;
    			}
    		}
    		return false;
    	}

#### 递归操作 ####

//递归实现查询val的值 , 找到返回true , 否则返回false
    	bool query(const T &val)
    	{
        
    		return query(_root,val);
    	}

bool query(BSTNode* node,int val)
    	{
        
    		if(node == nullptr)
    			return false;
    		if(node->_data == val)
    			return true;
    		int a = query(node->_left,val);
    		if(a == 1)
    		{
        
    			return true;
    		}
    		return query(node->_right,val);
    	}

### BST树相关的经典题目 ###

#### BST树的镜像翻转(递归实现) ####

void mirror()
    	{
        
    		mirror(_root);
    	}

//镜像翻转
    	/*
    	通过遍历每个节点 , 将每个节点都进行翻转
    	*/
    	void mirror(BSTNode *node)
    	{
        
    		if(node == nullptr)
    			return;
    
    		BSTNode *ptmp = node->_left;
    		node->_left = node->_right;
    		node->_right = ptmp;
    
    		mirror(node->_left);
    		mirror(node->_right);
    	}

#### 返回BST树所有节点的个数(递归实现) ####

int number()
    	{
        
    		return number(_root);
    	}

// 返回以node为根节点的子树节点的总数
    	int number(BSTNode *node)
    	{
        
    		if(node == nullptr)
    			return 0;
    		return 1 + number(node->_left) + number(node->_right);
    	}

#### 返回BST树的层数/高度(递归实现) ####

// 递归实现返回BST树的层数/高度
    	int level()
    	{
        
    		return level(_root);
    	}

//返回层数
    	int level(BSTNode *node)
    	{
        
    		if (node == nullptr)
    		{
        
    			return 0;
    		}
    		else
    		{
        
    			int left = level(node->_left);
    			int right = level(node->_right);
    			return left > right ? left + 1 : right + 1;
    		}
    	}

#### 判断当前二叉树是不是一颗BST树(递归实现) ####

//判断当前二叉树是不是一颗BST树
    	bool isBSTree()
    	{
        
    		BSTNode* pre = nullptr ;
    		return isBSTree(_root , pre);
    	}

//以node为根节点 , 判断当前二叉树是不是BST树
    	//递归中 , 要更新形参的数据 , 要在形参中加引用
    	/*
    	中序遍历是从小到大排列 , 所以每次遍历都记录的当前节点
    	然后不断更新 , 如果出现当前节点比后继节点大的情况 , 就说明不是BST树
    	*/
    	bool isBSTree(BSTNode* node , BSTNode* &pre)
    	{
        
    		if(node == nullptr)
    			return true;
    
    		if(!isBSTree(node->_left)) 
    			return false;
    		//中序遍历 , 判断节点与他的直接后继的大小关系
    		if(pre != nullptr)
    		{
        
    			if(node->_data < pre->_data)
    				return false;
    		}
    
    		//更新
    		pre = node;
    
    		return isBSTree(node->_right) ; 
    		
    	}

#### 打印BST树中 , 区间\[first, last\]的所有元素(递归实现) ####

//在当前BST树中 , 把满足区间[first, last]的所有元素打印出来
    	/*
    	创建一个vector容器 , 将符合条件的节点的值都存入容器中 
    	最后打印容器
    	*/
    	void findAreaData(int first , int last)
    	{
        
    		vector<int> vec;
    		findAreaData(_root , first , last , vec);
    		cout<<"["<<first<<","<<last<<"]"<<" : ";
    		for(int v : vec)
    		{
        
    			cout<< v<<" ";
    		}
    		cout<<endl;
    	}

//以node为根节点 , 中序遍历BST树 , 寻找满足区间[first, last]的元素
    	void findAreaData(BSTNode* node , int first , int last ,vector<int> &vec)
    	{
        
    		if(node == nullptr)
    			return ;
    		if(node->_data > last)
    			return;
    
    		findAreaData(node->_left,first,last,vec);
    		if(node->_data >= first && node->_data <= last)
    		{
        
    			vec.push_back(node->_data);
    		}
    		findAreaData(node->_right,first,last,vec);
    	}

#### 获取两个节点的最近公共祖先节点(递归实现) ####

// 获取两个节点的最近公共祖先节点
    	/*
    	因为要作为两个结点的公共祖先，必须满足，该结点的值一定在两结点值的中间位置 
    	流程 : 
    	* 若该结点的值同时大于传入的两个结点的值，那么该结点向左子树遍历 
    	* 使其值变小 
    	* 若该结点的值同时小于传入的两个结点的值，那么该结点向右子树遍历 
    	* 使其值变大 
    	* 若该结点的值在传入的两个结点值之间，则找到，返回。
    	*/
    	int getLCA(int val1, int val2)
    	{
        
    		BSTNode *p = getLCA(_root, val1, val2);
    		if (p != nullptr)
    		{
        
    			return p->_data;
    		}
    		else
    		{
        
    			throw "no LCA node!";
    		}
    	}

// 以node为根节点，开始寻找val1和val2的LCA
    	BSTNode* getLCA(BSTNode *node, int val1, int val2)
    	{
        
    		if (node == nullptr)
    		{
        
    			return nullptr;
    		}
    			
    		if (val1 < node->_data && val2 < node->_data) 
    		{
        
    			return getLCA(node->_left, val1, val2);
    		}
    		else if (val1 > node->_data && val2 > node->_data)
    		{
        
    			return getLCA(node->_right, val1, val2);
    		}
    		else
    		{
        
    			return node;
    		}
    	}

#### 获取中序遍历倒数第k个节点的值(递归实现) ####

// 获取中序遍历倒数第k个节点的值
    	/*
    	中序遍历是先做后右 , 反向遍历就可以是先右后左 , 
    	再记录遍历的次数 , 当到达次数的时候返回即可
    	*/
    	int getLastKValue(int k) // LVR    RVL
    	{
        
    		int i = 0;
    		BSTNode *p = getLastKValue(_root, k, i);
    		if (p != nullptr)
    		{
        
    			return p->_data;
    		}
    		else
    		{
        
    			throw "no last k value, k is invalid!";
    		}
    	}

// LVR RVL 以node为根节点，找反向中序遍历的第K个节点
    	BSTNode* getLastKValue(BSTNode *node, int k, int &i)
    	{
        
    		if (node == nullptr)
    		{
        
    			return nullptr;
    		}
    
    		BSTNode *p1 = getLastKValue(node->_right, k, i); // R
    		if (p1 != nullptr)
    		{
        
    			return p1;
    		}
    
    		i++;
    		if (k == i)
    		{
        
    			return node; // V
    		}
    
    		return getLastKValue(node->_left, k, i); // L
    	}

#### 判断参数tree是否是当前BST树的一颗子树(递归实现) ####

/*
    	流程:
    	首先在树中找到子树的根节点 , 找不到返回false
    	然后进行递归操作	
    	如果父树和字数都遍历到最后都为空, 则说明子树为真
    	如果父树的节点为空 , 子树的节点不为空 , 说明子树为假
    	如果父树节点不为空 , 子树节点为空 , 说明子树为真
    	*/
    	bool isChildTree(const BSTree<T> &tree)
    	{
        
    		if (_root == nullptr)
    			return false;
    		BSTNode *cur = _root;
    		while (cur != nullptr)
    		{
        
    			if (tree._root->_data > cur->_data)
    			{
        
    				cur = cur->_right;
    			}
    			else if (tree._root->_data < cur->_data)
    			{
        
    				cur = cur->_left;
    			}
    			else
    			{
        
    				break;
    			}
    		}
    		if (cur == nullptr)
    			return false;
    
    		return isChildTree(cur, tree._root);
    	}

// 从father节点开始判断，是否全包含child的节点
    	/*
    	如果父树和字数都遍历到最后都为空, 则说明子树为真
    	如果父树的节点为空 , 子树的节点不为空 , 说明子树为假
    	如果父树节点不为空 , 子树节点为空 , 说明子树为真
    	*/
    	bool isChildTree(BSTNode *father, BSTNode *child)
    	{
        
    		if (father == nullptr && child == nullptr)
    		{
        
    			return true;
    		}
    
    		if (father == nullptr)
    		{
        
    			return false;
    		}
    
    		if (child == nullptr)
    		{
        
    			return true;
    		}
    
    		if (father->_data != child->_data)
    		{
        
    			return false;
    		}
    
    		return isChildTree(father->_left, child->_left)
    			&& isChildTree(father->_right, child->_right);
    	}

#### 已知一棵BST树的前序遍历结果pre数组，和中序遍历结果in数组，重建二叉树(递归实现) ####

/*
    	前序遍历的第一个数是这棵树的根节点
    	中序遍历是按照从小到大排列 , 在中序遍历中找到根节点 
    	左边的就是左子树 , 右边的就是右子树
    	然后用得到的左右子树的个数 , 用前序遍历的数组进行重构
    	*/
    	void rebuildBSTree(int pre[], int len1, int in[], int len2)
    	{
        
    		this->_root = rebuildBSTree(pre, 0, len1-1, in, 0, len2-1);
    	}

//重建
    	BSTNode* rebuildBSTree(int pre[], int i, int j, int in[], int m, int n)
    	{
        
    		if (i > j || m > n)
    		{
        
    			return nullptr;
    		}
    		//前序遍历的根节点
    		BSTNode *root = new BSTNode(pre[i]);
    		for (int k = m; k <= n; ++k)
    		{
        
    			if (pre[i] == in[k]) // 中序遍历种找到根节点了
    			{
        
    				root->_left = rebuildBSTree(pre, i+1, i+(k-m), in, m, k-1);
    				root->_right = rebuildBSTree(pre, i+(k - m)+1, j, in, k+1, n);
    				break;
    			}
    		}
    		//更新
    		return root;
    	}

### 完整代码 ###

#include<iostream>
    #include<queue>
    #include<ctime>
    #include<stack>
    #include<vector>
    using namespace std;
    
    /*
    二叉树 : 
    BST树 : 二叉搜索树
    
    树的高度  log_2n
    
    判断一个二叉树是不是BST树
    
    前驱结点 : 当前节点的左子树中 , 元素的最大值
    后继节点 : 当前节点的右子树中 , 元素的最小值
    
    删除的三种情况 (1 , 2 情况属于一种 , 孩子为空):
    1. 删除的节点没有孩子
    2. 删除的节点只有一个孩子
    3. 删除的节点有两个孩子
    
      用当前的前驱结点或者后继结点 , 代替当前要删除的节点
    */
    
    #if 0
    template<typename T>
    class BSTree
    {
        
    public:
    	BSTree():_root(nullptr){
        }
    	// 非递归实现BST树的插入操作
    	/*
    	寻找适合插入的位置 , 插入的数值先与根节点进行比较 , 大于则向右进入右子树 , 小于则向左进入左子树
    	如此循环 , 直到找到某个位置的左孩子(或右孩子)为空(nullptr) , 则说明找到这个地方
    	然后判断该节点大于(还是小于)父节点 , 即插在父节点的左孩子还是右孩子 , 最后将节点插入即可
    	*/
    	void noninsert(const T &val)
    	{
        
    		//先要判断插入的节点是不是根节点
    		if(_root == nullptr)
    		{
        
    			_root = new BSTNode(val);
    			return;
    		}
    		BSTNode* pre = nullptr; //记录父节点
    		BSTNode* node = _root;
    		//循环开始找位置
    		while(node != nullptr)
    		{
        
    			pre = node;
    			//向右
    			if(val > node->_data)
    			{
        
    				node = node->_right;
    				continue;
    			}
    			//向左
    			else if(val < node->_data)
    			{
         node = node->_left ; }
    			else
    			//等于说明已经有同一节点 , 不必再插入 ,返回即可
    			{
          return ; }
    		}
    		//判断插在父节点的左还是右
    		if(val < pre->_data)
    		{
         pre->_left = new BSTNode(val) ; }
    		else
    		{
         pre->_right = new BSTNode(val) ; }
    	}
    
    	//递归实现BST的插入操作
    	void insert(const T &val)
    	{
        
    		this->insert(_root,val);
    	}
    
    	// 非递归实现BST树的删除操作
    	/*
    	再从一棵二叉搜索树中删除一个节点之前必须先找到该节点所在的位置
    	删除操作往往会引起很多后果 , 主要来自两个方面 : 
    	一方面删除树中的一个节点必然会导致原本连通的树结构发生阻隔
    	其次 , 当二叉搜索树中的某个节点被删除之后 , 树中的有序关系可能遭到破坏
    
    	具体而言分为三种情况 : 
    	1.删除的节点没有孩子
    	2.删除的节点只有一个孩子
    	3.删除的节点有两个孩子
    	注 : 1和2可以看成是一种类型 , 只有一个孩子 , 这个孩子是空(nullptr)
    	情况三的处理方法 , 使用前驱结点或者后继节点代替该节点 , 删除前驱即可
    	前驱结点 : 当前节点的左子树中 , 元素的最大值
    	后继节点 : 当前节点的右子树中 , 元素的最小值
    
    	流程: 
    	1. 从_root开始寻找值为val的节点，cur指向它
    	2. 先判断是否满足情况3，如果满足，需要找cur的前驱节点，用前驱把cur节点的值给覆盖掉，直接删前驱
    	3. 删除情况1和情况2   直接删除cur指针指向的节点就可以了
    	*/
    	void nonremove(const T &val)
    	{
        
    		// 1. 从_root开始寻找值为val的节点，cur指向它
    		BSTNode *pre = nullptr;  //记录父节点
    		BSTNode *cur = _root;
    		while(cur != nullptr)
    		{
        
    			if(val < cur->_data)
    			{
        
    				pre = cur;
    				cur = cur->_left;
    			}
    			else if(val > cur->_data)
    			{
        
    				pre = cur;
    				cur = cur->_right;
    			}
    			else
    			{
        
    				break;
    			}
    		}
    		//判断找没找到
    		if(cur == nullptr)
    			return;
    
    		// 2. 先判断是否满足情况3，如果满足，需要找cur的前驱节点，用前驱把cur节点的值给覆盖掉，直接删前驱
    		if(cur->_left != nullptr && cur->_right != nullptr)
    		{
        
    			BSTNode *old = cur;
    			pre = cur;
    			//找前驱
    			cur = cur->_left;
    			while(cur->_right != nullptr)
    			{
        
    				pre = cur;
    				cur = cur->_right;
    			}
    			//用前驱覆盖被删除节点
    			old->_data = cur->_data;
    		}
    		// 3. 删除情况1和情况2   直接删除cur指针指向的节点就可以了
    		BSTNode *child = cur->_left;
    		if(child == nullptr)
    		{
        
    			child = cur->_right;
    		}
    
    		if(pre == nullptr) // cur指向的根节点
    		{
        
    			_root = child;
    		}
    		else
    		{
        
    			// 要把删除节点的孩子赋给cur父节点相应的地址域里面
    			if(cur == pre->_left)
    			{
        
    				pre->_left = child;
    			}
    			else
    			{
        
    				pre->_right = child;
    			}
    		}
    		delete cur;
    	}
    
    	//递归实现BST树的删除操作
    	void remove(const T &val)
    	{
        
    		_root = remove(_root,val);
    	}
    
    	//实现对BST树的镜像翻转
    	void mirror()
    	{
        
    		mirror(_root);
    	}
    
    	// 递归实现返回BST树所有节点的个数
    	int number()
    	{
        
    		return number(_root);
    	}
    
    	// 递归实现返回BST树的层数/高度
    	int level()
    	{
        
    		return level(_root);
    	}
    
    	//实现BST树查找指定的元素值val是否存在
    	bool nonquery(const T &val) 
    	{
        
    		if(_root == nullptr)
    		{
        
    			return false;
    		}
    		BSTNode* node = _root;
    		while(node != nullptr)
    		{
        
    			if(val > node->_data)
    			{
        
    				node = node->_right;
    			}
    			else if(val < node->_data)
    			{
        
    				node = node->_left;
    			}
    			else
    			{
        
    				return true;
    			}
    		}
    		return false;
    	}
    
    	//递归实现查询val的值 , 找到返回true , 否则返回false
    	bool query(const T &val)
    	{
        
    		return query(_root,val);
    	}
    
    	//递归实现 , 前序遍历
    	void Pre_out()
    	{
        
    		cout<<"递归实现 , 前序遍历 : ";
    		Pre_out(_root);
    		cout << endl;
    	}
    	//递归实现 , 中序遍历
    	void Mid_out()
    	{
        
    		cout<<"递归实现 , 中序遍历 : ";
    		Mid_out(_root);
    		cout << endl;
    	}
    	//递归实现 , 后序遍历
    	void Last_out()
    	{
        
    		cout<<"递归实现 , 后序遍历 : ";
    		Last_out(_root);
    		cout << endl;
    	}
    
    	// 非递归实现层序遍历(从根节点开始，一层一层按从左向右的顺序打印BST树节点的值)
    	/*
    	广度遍历需要用到队列来完成 , 通过队列的先进先出 , 来实现层序遍历
    	*/
    	void nonlevelOrder()
    	{
        
    		// 1.如果_root为空，直接返回
    		if(_root == nullptr)
    			return;
    		// 2._root -> queue
    		queue<BSTNode*> que;
    		que.push(_root);
    
    		// 3.循环判断队列是否为空， 不为空取出队头元素，分别判断左右孩子是否为nullptr，不为空
    		// 就要依次入队，然后打印队头元素，继续判断下一个队头元素
    		while(!que.empty())
    		{
        
    			BSTNode *front = que.front();
    			cout<<front->_data<<" ";
    			que.pop();
    			if(front->_left != nullptr)
    			{
        
    				que.push(front->_left);
    			}
    			if(front->_right != nullptr)
    			{
        
    				que.push(front->_right);
    			}
    		}
    	}
    
    	//递归实现层序遍历
    	/*
    	根据传递的层数进行打印 , 不到指定层不打印
    	*/
    	void levelOrder()
    	{
        
    		cout<<"递归实现层序遍历 : ";
    		int l = level(_root);
    		for(int i = 0; i < l ;++i)
    		{
        
    			levelOrder(_root , i);
    		}
    		cout<<endl;
    	}
    
    	//非递归实现BST的前序遍历 VLR
    	/*
    	深度是用栈 , 广度是用队列
    	因为是先序遍历是先左后右 , 入栈的之后要反着来(先右后左)
    
    	流程: 
    	现将根节点入栈 
    	以栈是否为空作为条件进行循环 
    	出栈顶元素 , 打印
    	将该节点的右孩子和左孩子依次压栈(因为出的时候要先左后右)
    	周而复始
    	*/
    	void nonpreOrder()
    	{
        
    		if(_root == nullptr)
    			return ;
    		BSTNode* node = _root;
    		stack<BSTNode*> st;
    		st.push(_root);
    		cout<<"非递归实现 , 前序遍历 : ";
    		while(!st.empty())
    		{
        
    			BSTNode* tmp = st.top();
    			st.pop();
    			cout<<tmp->_data<<" ";
    			if(tmp->_right != nullptr)
    			{
        
    				st.push(tmp->_right);
    			}
    			if(tmp->_left != nullptr)
    			{
        
    				st.push(tmp->_left);
    			}
    		}
    		cout<<endl;
    	}
    
    	//非递归实现BST的中序遍历 LVR , 是按照从小到大排列的
    	/*
    	流程:
    	中序遍历左子树
    	当遍历到最后的叶子节点时 
    	弹出栈顶元素 , 打印
    	然后将该节点的右孩子进行压栈
    	周而复始
    	*/
    	void noninOrder()
    	{
        
    		if(_root == nullptr)
    			return ;
    		stack<BSTNode*> st;
    		BSTNode* tmp = _root;
    		cout<<"非递归实现 , 中序遍历 : ";
    
    		while(!st.empty() || tmp != nullptr)
    		{
        
    			if(tmp != nullptr)
    			{
        
    				st.push(tmp);
    				tmp = tmp->_left;
    			}
    			else
    			{
        
    				BSTNode* top = st.top();
    				st.pop();
    				cout<<top->_data<<" ";
    				tmp = top->_right;
    			}
    		}
    		cout<<endl;
    	}
    
    	//非递归实现BST的后序遍历 LRV
    	/*
    	后序遍历 , 使用一个栈实现是很困难的
    	要牵扯到回退的问题 , 代码层面实现起来有一定的难度
    	那么, 就得使用两个栈 
    
    	先将根节点放入栈1中 
    	以栈不为空作为循环条件
    	将栈1元素弹出
    	并将弹出的元素压入栈2
    	然后按照后续遍历的顺序 , 将该节点的左孩子和右孩子依次入栈
    	周而复始
    	等到栈1全部为空  , 退出循环之后
    	将栈2的元素依次弹出打印
    	*/
    	void nonpostOrder()
    	{
        
    		if(_root == nullptr)
    			return ;
    		stack<BSTNode*>  st1;
    		stack<BSTNode*>  st2;
    		BSTNode* node = _root;
    		st1.push(node);
    		while(!st1.empty())
    		{
        
    			BSTNode* tmp = st1.top();
    			st1.pop();
    			st2.push(tmp);
    			if(tmp->_left != nullptr)
    				st1.push(tmp->_left);
    			if(tmp->_right != nullptr)
    				st1.push(tmp->_right);
    		}
    		cout<<"非递归实现 , 后序遍历 : ";
    		while(!st2.empty())
    		{
        
    			BSTNode* node = st2.top();
    			cout<<node->_data<<" ";
    			st2.pop();
    		}
    		cout<<endl;
    	}
    
    	//判断当前二叉树是不是一颗BST树
    	bool isBSTree()
    	{
        
    		BSTNode* pre = nullptr ;
    		return isBSTree(_root , pre);
    	}
    
    	//在当前BST树中 , 把满足区间[first, last]的所有元素打印出来
    	/*
    	创建一个vector容器 , 将符合条件的节点的值都存入容器中 
    	最后打印容器
    	*/
    	void findAreaData(int first , int last)
    	{
        
    		vector<int> vec;
    		findAreaData(_root , first , last , vec);
    		cout<<"["<<first<<","<<last<<"]"<<" : ";
    		for(int v : vec)
    		{
        
    			cout<< v<<" ";
    		}
    		cout<<endl;
    	}
    
    
    	// 获取两个节点的最近公共祖先节点
    	/*
    	因为要作为两个 结点的公共祖先，必须满足，该结点的值一定在两结点值的中间位置 
    	流程 : 
    	* 若该结点的值同时大于传入的两个结点的值，那么该结点向左子树遍历 
    	* 使其值变小 
    	* 若该结点的值同时小于传入的两个结点的值，那么该结点向右子树遍历 
    	* 使其值变大 
    	* 若该结点的值在传入的两个结点值之间，则找到，返回。
    	*/
    	int getLCA(int val1, int val2)
    	{
        
    		BSTNode *p = getLCA(_root, val1, val2);
    		if (p != nullptr)
    		{
        
    			return p->_data;
    		}
    		else
    		{
        
    			throw "no LCA node!";
    		}
    	}
    
    	// 获取中序遍历倒数第k个节点的值
    	/*
    	中序遍历是先做后右 , 反向遍历就可以是先右后左 , 
    	再记录遍历的次数 , 当到达次数的时候返回即可
    	*/
    	int getLastKValue(int k) // LVR    RVL
    	{
        
    		int i = 0;
    		BSTNode *p = getLastKValue(_root, k, i);
    		if (p != nullptr)
    		{
        
    			return p->_data;
    		}
    		else
    		{
        
    			throw "no last k value, k is invalid!";
    		}
    	}
    
    	// 判断参数tree是否是当前BST树的一颗子树，是返回true，否则返回false
    	/*
    	流程:
    	首先在树中找到子树的根节点 , 找不到返回false
    	然后进行递归操作	
    	如果父树和字数都遍历到最后都为空, 则说明子树为真
    	如果父树的节点为空 , 子树的节点不为空 , 说明子树为假
    	如果父树节点不为空 , 子树节点为空 , 说明子树为真
    	*/
    	bool isChildTree(const BSTree<T> &tree)
    	{
        
    		if (_root == nullptr)
    			return false;
    		BSTNode *cur = _root;
    		while (cur != nullptr)
    		{
        
    			if (tree._root->_data > cur->_data)
    			{
        
    				cur = cur->_right;
    			}
    			else if (tree._root->_data < cur->_data)
    			{
        
    				cur = cur->_left;
    			}
    			else
    			{
        
    				break;
    			}
    		}
    		if (cur == nullptr)
    			return false;
    
    		return isChildTree(cur, tree._root);
    	}
    
    	// 已知一棵BST树的前序遍历结果pre数组，和中序遍历结果in数组，重建二叉树
    	/*
    	前序遍历的第一个数是这棵树的根节点
    	中序遍历是按照从小到大排列 , 在中序遍历中找到根节点 
    	左边的就是左子树 , 右边的就是右子树
    	然后用得到的左右子树的个数 , 用前序遍历的数组进行重构
    	*/
    	void rebuildBSTree(int pre[], int len1, int in[], int len2)
    	{
        
    		this->_root = rebuildBSTree(pre, 0, len1-1, in, 0, len2-1);
    	}
    
    
    
    private:
    	// 定义BST树节点的类型
    	struct BSTNode
    	{
        
    		BSTNode(T data=T())
    			:_data(data)
    			,_left(nullptr)
    			,_right(nullptr)
    		{
        }
    		T _data;
    		BSTNode *_left;
    		BSTNode *_right;
    	};
    	BSTNode *_root; // 指向树的根节点
    	//镜像翻转
    	/*
    	通过遍历每个节点 , 将每个节点都进行翻转
    	*/
    	void mirror(BSTNode *node)
    	{
        
    		if(node == nullptr)
    			return;
    
    		BSTNode *ptmp = node->_left;
    		node->_left = node->_right;
    		node->_right = ptmp;
    
    		mirror(node->_left);
    		mirror(node->_right);
    	}
    
    	// 返回以node为根节点的子树节点的总数
    	int number(BSTNode *node)
    	{
        
    		if(node == nullptr)
    			return 0;
    		return 1 + number(node->_left) + number(node->_right);
    	}
    
    	//返回层数
    	int level(BSTNode *node)
    	{
        
    		if (node == nullptr)
    		{
        
    			return 0;
    		}
    		else
    		{
        
    			int left = level(node->_left);
    			int right = level(node->_right);
    			return left > right ? left + 1 : right + 1;
    		}
    	}
    	
    	/*
    	VLR    只有根节点是打印
    	1.先打印根节点 
    	2.以VLR的方式继续访问左孩子
    	3.以VLR的方式继续访问右孩子
    	*/
    
    	//递归实现 , 先序遍历   VLR
    	void Pre_out(BSTNode *node)	//前序遍历
    	{
        
    		if (node != nullptr)
    		{
        
    			cout << node->_data << " ";
    			Pre_out(node->_left);
    			Pre_out(node->_right);
    		}
    	}
    	//递归实现 , 中序遍历   LVR
    	void Mid_out(BSTNode *node)	
    	{
        
    		if (node != nullptr)
    		{
        
    			Mid_out(node->_left);
    			cout << node->_data << " ";
    			Mid_out(node->_right);
    		}
    	}
    	//递归实现 , 后序遍历   LRV
    	void Last_out(BSTNode *node)	
    	{
        
    		if (node != nullptr)
    		{
        
    			Last_out(node->_left);
    			Last_out(node->_right);
    			cout << node->_data << " ";
    		}
    	}
    	//打印一Node为节点的树的层序遍历
    	void levelOrder(BSTNode* node , int n)
    	{
        
    		if(node == nullptr)
    			return;
    		if(n == 0)
    		{
        
    			cout<<node->_data<<" ";
    			return;
    		}
    		levelOrder(node->_left,n-1);
    		levelOrder(node->_right , n-1);
    		
    	}
    
    	//以node为根节点 , 判断当前二叉树是不是BST树
    	//递归中 , 要更新形参的数据 , 要在形参中加引用
    	/*
    	中序遍历是从小到大排列 , 所以每次遍历都记录的当前节点
    	然后不断更新 , 如果出现当前节点比后继节点大的情况 , 就说明不是BST树
    	*/
    	bool isBSTree(BSTNode* node , BSTNode* &pre)
    	{
        
    		if(node == nullptr)
    			return true;
    
    		if(!isBSTree(node->_left)) 
    			return false;
    		//中序遍历 , 判断节点与他的直接后继的大小关系
    		if(pre != nullptr)
    		{
        
    			if(node->_data < pre->_data)
    				return false;
    		}
    
    		//更新
    		pre = node;
    
    		return isBSTree(node->_right) ; 
    		
    	}
    
    	//以node为根节点 , 中序遍历BST树 , 寻找满足区间[first, last]的元素
    	void findAreaData(BSTNode* node , int first , int last ,vector<int> &vec)
    	{
        
    		if(node == nullptr)
    			return ;
    		if(node->_data > last)
    			return;
    
    		findAreaData(node->_left,first,last,vec);
    		if(node->_data >= first && node->_data <= last)
    		{
        
    			vec.push_back(node->_data);
    		}
    		findAreaData(node->_right,first,last,vec);
    	}
    
    	// 以node为根节点，开始寻找val1和val2的LCA
    	BSTNode* getLCA(BSTNode *node, int val1, int val2)
    	{
        
    		if (node == nullptr)
    		{
        
    			return nullptr;
    		}
    			
    		if (val1 < node->_data && val2 < node->_data) 
    		{
        
    			return getLCA(node->_left, val1, val2);
    		}
    		else if (val1 > node->_data && val2 > node->_data)
    		{
        
    			return getLCA(node->_right, val1, val2);
    		}
    		else
    		{
        
    			return node;
    		}
    	}
    
    	// LVR RVL 以node为根节点，找反向中序遍历的第K个节点
    	BSTNode* getLastKValue(BSTNode *node, int k, int &i)
    	{
        
    		if (node == nullptr)
    		{
        
    			return nullptr;
    		}
    
    		BSTNode *p1 = getLastKValue(node->_right, k, i); // R
    		if (p1 != nullptr)
    		{
        
    			return p1;
    		}
    
    		i++;
    		if (k == i)
    		{
        
    			return node; // V
    		}
    
    		return getLastKValue(node->_left, k, i); // L
    	}
    
    	// 从father节点开始判断，是否全包含child的节点
    	/*
    	如果父树和字数都遍历到最后都为空, 则说明子树为真
    	如果父树的节点为空 , 子树的节点不为空 , 说明子树为假
    	如果父树节点不为空 , 子树节点为空 , 说明子树为真
    	*/
    	bool isChildTree(BSTNode *father, BSTNode *child)
    	{
        
    		if (father == nullptr && child == nullptr)
    		{
        
    			return true;
    		}
    
    		if (father == nullptr)
    		{
        
    			return false;
    		}
    
    		if (child == nullptr)
    		{
        
    			return true;
    		}
    
    		if (father->_data != child->_data)
    		{
        
    			return false;
    		}
    
    		return isChildTree(father->_left, child->_left)
    			&& isChildTree(father->_right, child->_right);
    	}
    
    	//重建
    	BSTNode* rebuildBSTree(int pre[], int i, int j, int in[], int m, int n)
    	{
        
    		if (i > j || m > n)
    		{
        
    			return nullptr;
    		}
    		//前序遍历的根节点
    		BSTNode *root = new BSTNode(pre[i]);
    		for (int k = m; k <= n; ++k)
    		{
        
    			if (pre[i] == in[k]) // 中序遍历种找到根节点了
    			{
        
    				root->_left = rebuildBSTree(pre, i+1, i+(k-m), in, m, k-1);
    				root->_right = rebuildBSTree(pre, i+(k - m)+1, j, in, k+1, n);
    				break;
    			}
    		}
    		//更新
    		return root;
    	}
    
    	bool query(BSTNode* node,int val)
    	{
        
    		if(node == nullptr)
    			return false;
    		if(node->_data == val)
    			return true;
    		int a = query(node->_left,val);
    		if(a == 1)
    		{
        
    			return true;
    		}
    		return query(node->_right,val);
    	}
    
    	//递归实现插入操作
    	BSTNode* insert(BSTNode* node,int val)
    	{
        
    		//插入的是根节点
    		if(node == nullptr)
    		{
        			
    			return new BSTNode(val);
    		}
    		//进入右子树
    		if(val > node->_data)
    		{
        
    			node->_right = insert(node->_right,val);
    		}
    		//进入左子树
    		else if(val < node->_data)
    		{
        
    			node->_left = insert(node->_left,val);
    		}
    		//为啥?  插入之后的更新
    		return node;
    	}
    
    	//递归实现删除操作
    	BSTNode* remove(BSTNode* node , int val)
    	{
        
    		if(node == nullptr)
    			return nullptr;
    		//查找被删除节点
    		if(val > node->_data)
    		{
        
    			node->_right = remove(node->_right,val);
    		}
    		else if(val < node->_data)
    		{
        
    			node->_left = remove(node->_left,val);
    		}
    		else
    		{
        
    			//判断是否满足情况3
    			if(node->_left != nullptr && node->_right != nullptr)
    			{
        
    				//找前驱节点
    				BSTNode* pre = node->_left;
    				while(pre->_right != nullptr)
    				{
        
    					pre = pre->_right;
    				}
    				node->_data = pre->_data;
    				//寻找前驱 , 直接删除前驱 
    				node->_left = remove(node->_left,pre->_data);
    			}
    			else
    			{
        
    				//情况2
    				if(node->_left != nullptr)
    				{
        
    					BSTNode* left = node->_left;
    					delete node;
    					return left;
    				}
    				else if(node->_right != nullptr)
    				{
        
    					BSTNode* right = node->_right;
    					delete node;
    					return right;
    				}
    				else
    				{
        
    					//情况1
    					delete node;
    					return nullptr;
    				}
    			}
    		}
    		//更新节点信息
    		return node;
    	}
    
    	
    };
    
    
    int main()
    {
        
    	//srand(time(NULL));
    	BSTree<int> tree;
    	/*for(int i = 0 ; i < 20; i++)
    	{	
    		tree.noninsert(rand()%101);
    	}*/
    	tree.noninsert(40);
    	tree.noninsert(20);
    	tree.noninsert(60);
    	tree.noninsert(25);
    	tree.noninsert(45);
    	tree.noninsert(70);
    
    	//tree.nonlevelOrder();
    
    	cout<<endl<<"================"<<endl;
    	/*tree.nonremove(40);
    	tree.nonlevelOrder();
    	cout<<endl;*/
    
    	/*if(tree.query(25))
    		cout<<"Yes"<<endl;
    	else
    		cout<<"No"<<endl;
    
    	cout<<tree.level()<<endl;*/
    
    	/*tree.Pre_out();
    	tree.Mid_out();
    	tree.Last_out();
    	tree.levelOrder();
    
    	tree.nonpreOrder();
    	tree.noninOrder();
    	tree.nonpostOrder();
    
    	tree.findAreaData(20,60);*/
    
    	//cout<<tree.getLCA(45,60)<<endl;
    	
    	//tree.getLastKValue(6);	
    	//cout<<endl;
    
    	/*BSTree<int> tree1;
    	tree.noninsert(60);
    	tree.noninsert(45);
    	tree.noninsert(70);
    	if(tree.isChildTree(tree1))
    		cout<<"Yes"<<endl;
    	else
    		cout<<"No"<<endl*/;
    	
    	//tree.Pre_out();
    	tree.Mid_out();
    	cout<<"====="<<endl;
    
    	//int arr1[] = {40,20,25,60,50,70};
    	//int len1 = sizeof(arr1)/sizeof(arr1[0]);
    	//int arr2[] = {20,25,40,50,60,70};
    	//int len2 = sizeof(arr2)/sizeof(arr2[0]);
    	//
    	//tree.rebuildBSTree(arr1,len1,arr2,len2);
    	//tree.Pre_out();
    	//tree.Mid_out();
    
    
    	/*if(tree.query(45))
    		cout<<"Yes"<<endl;
    	else
    		cout<<"No"<<endl;*/
    
    	//tree.insert(5);
    	//tree.Mid_out();
    	tree.remove(70);
    	tree.Mid_out();
    
    	return 0;
    }
    
    #endif