【数据结构】手撕二叉搜索树

二叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
• 它的左右⼦树也分别为⼆叉搜索树
• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值

例如，下面就是一棵二叉搜索树：

• 由于二叉搜索树中，每个结点左子树上所有结点的值都小于该结点的值，右子树上所有结点的值都大于该结点的值，因此对二叉搜索树进行中序遍历后，得到的是升序序列也就不难理解了。
• 至于什么是中序遍历，我在讲解二叉树的时候已经讲解过，这里还不清楚的兄弟们可以去看看我以前的文章。

二叉搜索树的实现

节点类

要实现二叉搜索树，我们首先需要实现一个结点类：

• 结点类当中包含三个成员变量：结点值、左指针、右指针。
• 结点类当中只需实现一个构造函数即可，用于构造指定结点值的结点。

template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};

构造函数

• 我们先定义一个节点对象出来

	typedef BSTNode<K> Node;Node* _root = nullptr;

• 构造函数就把这个祖宗节点初始化

	BSTree():_root(nullptr){}

拷贝构造函数

//拷贝树
Node* _Copy(Node* root)
{if (root == nullptr) //空树直接返回return nullptr;Node* copyNode = new Node(root->_key); //拷贝根结点copyNode->_left = _Copy(root->_left); //拷贝左子树copyNode->_right = _Copy(root->_right); //拷贝右子树return copyNode; //返回拷贝的树
}
//拷贝构造函数
BSTree(const BSTree<K>& t)
{_root = _Copy(t._root); //拷贝t对象的二叉搜索树
}

赋值运算符重载

对于赋值运算符重载函数，下面提供两种实现方法：

• 先把当前二叉搜索树的节点全部释放，再把另外一颗二叉搜索树的所有节点拷贝过来。

//释放树中结点
void _Destory(Node* root)
{if (root == nullptr) //空树无需释放return;_Destory(root->_left); //释放左子树中的结点_Destory(root->_right); //释放右子树中的结点delete root; //释放根结点
}
//传统写法
const BSTree<K>& operator=(const BSTree<K>& t)
{if (this != &t) //防止自己给自己赋值{_Destory(_root); //先将当前的二叉搜索树中的结点释放_root = _Copy(t._root); //拷贝t对象的二叉搜索树}return *this; //支持连续赋值
}

析构函数

析构函数完成对象中二叉搜索树结点的释放，注意释放时采用后序释放，当二叉搜索树中的结点被释放完后，将对象当中指向二叉搜索树的指针及时置空即可。

//释放树中结点
void _Destory(Node* root)
{if (root == nullptr) //空树无需释放return;_Destory(root->_left); //释放左子树中的结点_Destory(root->_right); //释放右子树中的结点delete root; //释放根结点
}
//析构函数
~BSTree()
{_Destory(_root); //释放二叉搜索树中的结点_root = nullptr; //及时置空
}

插入函数

根据二叉搜索树的性质，其插入操作非常简单：

• 如果是空树，则直接将插入结点作为二叉搜索树的根结点。
• 如果不是空树，则按照二叉搜索树的性质进行结点的插入。

若不是空树，插入结点的具体操作如下：

• 若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中。
• 若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中。
• 若待插入结点的值等于根结点的值，则插入结点失败。

如此进行下去，直到找到与待插入结点的值相同的结点判定为插入失败，或者最终插入到某叶子结点的左右子树当中（即空树当中）。

• 但是需要注意在连接parent和cur时，需要判断应该将cur连接到parent的左边还是右边。

//插入函数
bool Insert(const K& key)
{if (_root == nullptr) //空树{_root = new Node(key); //直接申请值为key的结点作为二叉搜索树的根结点return true; //插入成功，返回true}Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key) //key值小于当前结点的值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (key > cur->_key) //key值大于当前结点的值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //key值等于当前结点的值{return false; //插入失败，返回false}}cur = new Node(key); //申请值为key的结点if (key < parent->_key) //key值小于当前parent结点的值{parent->_left = cur; //将结点连接到parent的左边}else //key值大于当前parent结点的值{parent->_right = cur; //将结点连接到parent的右边}return true; //插入成功，返回true
}

查找函数

根据二叉搜索树的特性，我们在二叉搜索树当中查找指定值的结点的方式如下：

• 若树为空树，则查找失败，返回nullptr。
• 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
• 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
• 若key值等于当前结点的值，则查找成功，返回对应结点的地址。

	bool find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}

删除函数

待删除结点的左子树为空

• 待删除节点右子树节点为空也是一样的处理方法
• ？但是如果我们删除的节点是祖宗节点，那么祖宗节点没有父节点该怎么办呢

				//找到了，准备删除if (cur->_left == nullptr)	//左子树为空{if (_root == cur) //删除的节点是祖宗节点 {_root = cur->_right;	//删除祖宗节点后，让我的右孩子节点成为新的祖宗节点}else{if (parent->_right == cur) //判断删除的节点是父节点的左孩子节点还是右孩子节点{parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;}else if (cur->_right == nullptr)	//右子树为空{if (_root == cur)	//删除的节点是祖宗节点 {_root = cur->_left;//删除祖宗节点后，让我的左孩子节点成为新的祖宗节点}else{if (cur == parent->_right) //判断删除的节点是父节点的左孩子节点还是右孩子节点{parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;}

待删除的两个节点都不为空

• 这个时候其实还有一个问题，那就是删除的节点如果是祖宗节点呢？

//找个人替代我的位置
//找右子树的最小节点Node* minRight = cur->_right;Node* minRightParent = cur;	//不能写成nullptr,如果不进循环会对minRightParent->_left = minRight->_right;空指针解引用while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRightParent->_left == minRight){minRightParent->_left = minRight->_right;}else{minRightParent->_right = minRight->_right;}delete minRight;

中序遍历

• 如果想要中序遍历我们就需要提供二叉树的祖宗节点，但是我们节点是封装起来的，但是我们又要在类外用，有没有一个方法能不在类外提供祖宗节点就可以完成中序遍历呢？有的兄弟有的。
• 我们在类里面再实现一个函数用来调用中序遍历的函数，我们知道，在类外是可以使用类的成员变量的，这个时候我们就可以提供祖宗节点调用中序遍历函数，然后我们只需要调用这个调用中序遍历函数的函数即可。

	void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

二叉搜索树的应用(k和k/v模型 )