C++ 二叉搜索树
二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
·若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
·若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
·它的左右子树也分别为二叉搜索树
二叉搜索树的操作
二叉搜索树的查找
· 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
· 最多查找高度次，走到到空，还没找到，这个值不存在。
二叉搜索树的插入
插入的具体过程如下：
· 树为空，则直接新增节点，赋值给root指针
· 树不空，按二叉搜索树性质查找插入位置，插入新节点
二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
· 要删除的结点无孩子结点
· 要删除的结点只有左孩子结点
· 要删除的结点只有右孩子结点
· 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况1可以与情况2或者3合并起来，因此真正的删除过程如下：
1：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
2：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
3：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除
二叉搜索树的实现
基本框架
我们需要实现二叉搜索树的插入，查找，删除以及中序遍历，接下来将以 K 模型的结构进行代码编写：
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key)
bool Find(const K& key)
bool Erase(const K& key)
void InOrder()
private:
void _InOrder(Node* root)
private:
Node* _root = nullptr;
};元素插入
将待插入的值与当前节点进行比较：
· 比当前节点小，则移向当前节点的左子节点，。
· 比当前节点的值大，则移向当前节点的右子节点。
· 等于当前节点的值，则不能进行插入，返回false。
· 遍历到节点为空，则当前位置就是要插入位置
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}元素查找
首先将要查找的值与当前节点进行比较，根据比较结果选择路径：
· 比当前节点小，则移向当前节点的左子节点。
· 比当前节点大，则移向当前节点的右子节点。
· 等于当前节点，则查找成功，返回当前节点。
· 遍历到结点为空还没找到，则该值不存在，返回空。
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;
}
元素删除
无孩子，有一个孩子的情况处理起来容易多了，直接将父节点指向当前节点的指针指向该节点的下一节点，然后对当前节点进行销毁即可。
复杂的是有两个孩子的节点
需要在其子树中寻找一个结点替代该结点（左子树的值最大结点/右子树的值最小结点），替换后仍满足搜索树要求
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不为空,替换法
// 右子树的最左节点代替删除
Node* rightminparent = cur;
Node* rightmin = cur->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
swap(cur->_key, rightmin->_key);
if (rightminparent->_left == rightmin)
rightminparent->_left = rightmin->_right;
else
rightminparent->_right = rightmin->_right;
delete rightmin;
}
return true;
}
}
return false;
}中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}附上完整代码：
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
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;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不为空,替换法
// 右子树的最左节点代替删除
Node* rightminparent = cur;
Node* rightmin = cur->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
swap(cur->_key, rightmin->_key);
if (rightminparent->_left == rightmin)
rightminparent->_left = rightmin->_right;
else
rightminparent->_right = rightmin->_right;
delete rightmin;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
void TestBSTree1()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> t1;
for (auto e : a)
{
t1.Insert(e);
}
t1.InOrder();
//t1.Erase(3);
t1.Erase(8);
t1.InOrder();
for (auto e : a)
{
t1.Erase(e);
t1.InOrder();
}
}
void TestBSTree2()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree<int> t1;
for (auto e : a)
{
t1.Insert(e);
}
t1.InOrder();
}#include"BinarySearchTree.h"
int main()
{
TestBSTree1();
TestBSTree2();
return 0;
}