二叉搜索树（c++）

二叉搜索树概念（BST）

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

 

 BST特性：中序遍历结果是有序的

最左侧节点中的值域是最小的， 最右侧节点中的值域是最大的。

二叉搜索树的操作

          

 1. 二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在

while(cur)
{
if(cur->data==key)
return cur->data;
else if(key<cur->data)
cur=cur->left;
else
cur=cur->right;
}

2. 二叉搜索树的插入

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

假如插入值为9的节点：

1.确认值为9的节点是否存在  存在：不插入   不存在：再插入

2.插入节点：

构造一个新节点  与parent中的值域比较 

小于parent中的值域：parent左侧

大于parent中的值域：parent右侧

3. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：

a. 叶子节点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程 如下：

1.只有右孩子&&叶子节点

2.只有左孩子

3.左右孩子都有：不能直接删除。在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点 中，再来处理该结点的删除问题--替换法删除。

删除的三种情况的代码实现 ：

bool Earse(const T& data){//空树：直接返回if (nullptr == _root){return false;}//非空//1.找值为data的节点Node* cur = _root;Node* parent = nullptr;while (cur){if (data == cur->_data)break;else if (data < cur->_data){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}//确认是否找到？if (nullptr == cur)return false;//2.删除该节点//1.只有右孩子&&叶子节点//2.只有左孩子//3.左右孩子都有//情况一：只有右孩子&&叶子节点if (nullptr == cur->_left){if (nullptr == parent){//cur现在就是根节点_root = cur->_right;delete cur;}else{//cur一定不是根节点//parent一定不为空if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}}//情况二：只有左孩子else if (nullptr == cur->_right){if (nullptr == parent){//cur现在就是根节点_root = cur->_left;delete cur;}else{//cur一定不是根节点//parent一定不为空if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}}//情况三：左右孩子均存在// cur不能直接被删除，需要在其子树中找到一个替代节点//将情况三变为情况一或者情况二else{//选择在右子树中找替代节点Node* del = cur->right;parent = cur;//1.找cur右子树中最小（左侧）的节点while (del->_left){parent = del;del = del->_left;}//2.使用del中的值域替换cur中的值域cur->_data = del->_data;//删除del，注意del可能是其双亲的左孩子  ||  可能是其右孩子if (del == parent->_left)parent->_left = del->_right;elseparent->_right = del->_right;delete del;}}

 代码整体实现：

template<class T>
struct BSTNode
{BSTNode<T>* _left;BSTNode<T>* _right;T _data;BSTNode(const T& data = T()): _left(nullptr), _right(nullptr), _data(data){}
};template<class T>
class BSTree
{typedef BSTNode<T> Node;
public:BSTree():_root(nullptr){}~BSTree(){_DestroyBSTree(_root);} bool Insert(const T& data){//空树，直接插入（根节点）if (nullptr == _root){_root = new Node(data);return true;}//非空//1.在BSTree中查找值为data的元素是否存在//注意：需要保存cur双亲Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (data == cur->_data)return false;else if (data < cur->_data)cur = cur->_left;elsecur = cur->_right;}//2.插入新节点cur = new Node(data);if (data < parent->_data)parent->_left = cur;elseparent->_right = cur;return true;}Node* Find(const T& data){Node* cur = _root;while (cur){if (cur->_data == data)return cur;else if (cur->_data > data)cur = cur->_left;else{cur = cur->_right;}}return nullptr;}void InOrder(){cout << "中序遍历:";_InOrder(_root);cout << endl;}bool Earse(const T& data){//空树：直接返回if (nullptr == _root){return false;}//非空//1.找值为data的节点Node* cur = _root;Node* parent = nullptr;while (cur){if (data == cur->_data)break;else if (data < cur->_data){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}//确认是否找到？if (nullptr == cur)return false;//2.删除该节点//1.只有右孩子&&叶子节点//2.只有左孩子//3.左右孩子都有//情况一：只有右孩子&&叶子节点if (nullptr == cur->_left){if (nullptr == parent){//cur现在就是根节点_root = cur->_right;delete cur;}else{//cur一定不是根节点//parent一定不为空if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}}//情况二：只有左孩子else if (nullptr == cur->_right){if (nullptr == parent){//cur现在就是根节点_root = cur->_left;delete cur;}else{//cur一定不是根节点//parent一定不为空if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}}//情况三：左右孩子均存在// cur不能直接被删除，需要在其子树中找到一个替代节点//将情况三变为情况一或者情况二else{//选择在右子树中找替代节点Node* del = cur->right;parent = cur;//1.找cur右子树中最小（左侧）的节点while (del->_left){parent = del;del = del->_left;}//2.使用del中的值域替换cur中的值域cur->_data = del->_data;//删除del，注意del可能是其双亲的左孩子  ||  可能是其右孩子if (del == parent->_left)parent->_left = del->_right;elseparent->_right = del->_right;delete del;}}private://中序遍历void _InOrder(Node* root){if (root){_InOrder(root->_left);cout << root->_data<<" ";_InOrder(root->_right);}}//销毁树void _DestroyBSTree(Node*& root){if (root){_DestroyBSTree(root->_left);_DestroyBSTree(root->_right);delete root;root = nullptr;}}private:BSTNode<T>* _root;
};

二叉树常见编程题：

1.二叉树的分层遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr)return ret;//层序遍历需要用到队列queue<TreeNode*> q;q.push(root);  //先把头节点（也就是第一层节点）放入到队列中去while(!q.empty())  //只要队列中元素不为空就一直遍历下去{size_t levelSize=q.size();   //定义一个levelSize表示一层中有几个节点vector<int>leveldata;   //定义一个leveldata用来放每一层的数据for(size_t i=0;i<levelSize;i++){TreeNode*cur=q.front();  //定义一个cur获取队头的元素leveldata.push_back(cur->val);  //将队头元素放入到leveldata中去if(cur->left)  //如果cur左孩子存在，让左孩子入队列{q.push(cur->left);}if(cur->right)//如果cur右孩子存在，让右孩子入队列{q.push(cur->right);}q.pop();  //最后将这个队头元素删除}//这个循环结束后出来  ，表示这一层元素已经遍历完了 并在队列中都删除了  来到下一层继续遍历。//一层节点中的值域全都在leveldata中ret.push_back(leveldata);}return ret;}
};

2.二叉搜索树与双向链表

描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 0≤n≤10000≤n≤1000，二叉树中每个节点的值 0≤val≤10000≤val≤1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

主要思路就是：对搜索二叉树来说，中序遍历得到就是有序的节点排列。

1.首先我们保存二叉树最小的节点，也就是最左侧的节点。

2.使用中序遍历在树上进行修改，将头节点传进去以后，先找到最左侧的节点，这时候第一个节点左我们需要指向空，节点的右要指向下一个节点。（但是不知道下一个节点的位置在什么地方）

但是继续递归下去，root就会到下一个节点不位置，这时候就需要定义一个prev将前一个节点保存。当root到下一个位置时，在这之前让prev=root。这时候就可以用prev->right=root;

就让上一个节点指向下一个节点了。以此类推。

class Solution
{
public://因为中序遍历搜索二叉树得到的节点是有序的，所以在中序遍历中对树上的节点进行操作void InOrder(TreeNode* root,TreeNode*& prev){if(nullptr==root)return;InOrder(root->left,prev);  //得到最小的那个节点//修改root中left和right指向root->left=prev; //此处判断目的就是，刚开始prev为空时。if(prev)prev->right=root;prev=root;//更新prev位置InOrder(root->right,prev);}TreeNode* Convert(TreeNode* root){if(nullptr==root)return nullptr;//找转换完成之后链表中的第一个节点，即BST中最左侧的节点TreeNode* PHead =root;while(PHead->left){PHead=PHead->left;}TreeNode* prev=nullptr;InOrder(root,prev);return PHead;}
};

3.二叉树的前序遍历，不用递归实现

 首先要了解二叉树前序遍历是怎么遍历的。

前序遍历就是：1，2，3，4，5，6  。先打印从根节点->左子树->右子树。

代码实现，主要就是用到栈的先进后出的原理来实现。 

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector <int> v;if(nullptr==root)return v;TreeNode*cur=root;stack<TreeNode*>s;while(cur||!s.empty())//当栈不为空 或者cur不空时一直循环{//顺着左侧路径从上往下遍历，并保存所经过路径中所遇到的节点while(cur)  {v.push_back(cur->val);//保存路过的节点值到vector中s.push(cur);  //并且将该节点放入栈中cur=cur->left;  //继续向左走}//将最左侧节点以及其左子树全部遍历完后//就剩下最左侧节点的右子树没有遍历了cur=s.top();  //用到了栈先进后出的特性，此时top 位置的节点就是最左侧的节点cur=cur->right;s.pop();}return v;}
};

 4.二叉树的中序遍历，不用递归实现

 中序遍历就是：左子树->根节点->右子树

在前序遍历的基础上 就行修改就是中序遍历。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> v;if(root==nullptr)return v;TreeNode* cur=root;stack<TreeNode*>s;while(cur||!s.empty()){//找最左侧节点，并保存所经过路径中的每个节点，目的：模拟递归的回退while(cur){s.push(cur);cur=cur->left;}//cur现在是最左侧节点的左孩子，即cur在空位置上//相当于cur对应的这颗树已经被遍历完了 cur=s.top(); //取最左侧的节点v.push_back(cur->val); //打印这一节点s.pop();  cur=cur->right; }return v;}
};

5.二叉树的后续遍历，不用递归实现

 后续遍历就是：左子树->右子树->根节点

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;if(root==nullptr)return v;TreeNode* cur=root;stack<TreeNode*>s;TreeNode* prev=nullptr;while(cur||!s.empty()){//顺着左侧路径找最左侧节点，并保存所经过路径中的所有节点.while(cur){s.push(cur);cur=cur->left;}TreeNode*top =s.top();if(top->right==nullptr || top->right==prev){v.push_back(top->val);prev=top; //标记刚刚遍历过的节点 ，如果不进行标记，当回到根节点时候，这时候 //top->right有节点存在，就会有执行/下面else的语句 ，就会重复循环。s.pop();}else{cur=top->right;}}return v;}
};

 6.根据二叉树创建字符串

 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1：

输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：

输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。

 

class Solution {
public:string tree2str(TreeNode* root,string& strRet) {if(nullptr==root)return strRet;//先遍历根节点strRet+=to_string(root->val);  //to_string 是转换为字符串形式if(root->left||root->right)  //如果有左子树 或者 右子树就进入循环  {strRet+="(";tree2str(root->left,strRet);strRet+=")";}if(root->right)  //如果没有右子树就不需要进入，因为那个括号可以省略。{strRet+="(";tree2str(root->right,strRet);strRet+=")";}return strRet;}string tree2str(TreeNode* root){string strRet;return tree2str(root,strRet);}
};

7.根据一棵树的前序遍历与中序遍历构造二叉树。

 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

 主要思路：

1.从前序遍历中获取根节点

2.在中序遍历中找到根的位置，确定根左右子树的范围

3.还原节点

递归还原根的左子树  递归还原根的右子树

class Solution {
public:TreeNode* buildTree(vector<int>& preorder,size_t& index, vector<int>& inorder,size_t left,size_t right) {if(left>=right)return nullptr;//在中序遍历中找到根的位置，确认根的左右子树的范围size_t rootIdx=left;while(rootIdx<right){if(inorder[rootIdx]==preorder[index])  //找到根节点位置停止break;rootIdx++;}//还原根节点TreeNode* root=new TreeNode(preorder[index]);++index;//递归还原根的左子树，左子树节点在中序遍历中的范围[left,rootIdx)root->left=buildTree(preorder,index,inorder,left,rootIdx);//递归还原根的右子树，右子树节点在中序遍历中的范围[rootIdx+1,right)root->right=buildTree(preorder,index,inorder,rootIdx+1,right);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {size_t index=0;return buildTree(preorder,index,inorder,0,inorder.size());}
};