二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
template <class K>
struct BSTreeNode
{
BSTreeNode *left;
BSTreeNode *right;
K _key;
BSTreeNode(const K &key) : left(nullptr), right(nullptr), _key(key){};
};
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
private:
Node *_root = nullptr;
};
让编译器提供个默认生成的就可以了,如果不写这个,又写了拷贝构造,编译器就不会自己自动生成了。
BSTree() = default;
递归拷贝左,右,根
//拷贝构造
BSTree(const BSTree<K> &t)
{
_root = _copy(t._root);
}
Node *_copy(Node *root)
{
// TODO 拷贝构造 赋值运算符重载
if (root == nullptr)
{
return nullptr;
}
Node *node = new Node(root->_key);
node->left = _copy(root->left);
node->right = _copy(root->right);
return node;
}
写完拷贝构造之后可以直接用现在写法就OK了
BSTree<K> operator=(BSTree<K> t)
{
std::swap(_root, t._root);
return *this;
}
递归,左、右、根
void _destory(Node *&root)
{
if (root == nullptr)
return;
_destory(root->left);
_destory(root->right);
delete root;
root = nullptr;
}
比它大往右走,比他小往左走,走到空,找它父亲链接起来
bool insert(const K &key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node *cur = _root;
Node *parent = nullptr;
while (cur)
{
parent = cur;
if (cur->_key > key)
{
cur = cur->left;
}
else if (cur->_key < key)
{
cur = cur->right;
}
else
{
// key==cur->key
return false;
}
}
//这里cur走到了空 进行插入
Node *new_node = new Node(key);
if (parent->_key > key)
{
parent->left = new_node;
}
else
{
parent->right = new_node;
}
return true;
}
重点是参数列表的引用 如果走到了root为空,说明到了该插入的位置,现在的root就是上一层父亲左孩子或者右孩子那个指针的别名
bool _insert_r(Node *&root, const K &key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key > key)
{
return _insert_r(root->left, key);
}
else if (root->_key < key)
{
return _insert_r(root->right, key);
}
else
{
return false;
}
}
提供一个inorder的接口,调用_inorder()
public:
void inorder()
{
_inorder(_root);
cout << endl;
}
private:
void _inorder(Node *root)
{
if (root == nullptr)
{
return;
}
_inorder(root->left);
cout << root->_key << " ";
_inorder(root->right);
}
可以记录父亲的值,直接干掉当前节点,判断当前节点是父亲的左还是右,然后用空替代当前节点
情况1可以归为情况2的特例
删除的是根
删除的不是根,依然两种情况,主要看这个要删除的节点是父亲的左还是右
如果是父亲的左,就把cur的右给父亲的左
如果是父亲的右,就把cur的右给父亲的右
先判断特殊情况,删除的节点为根节点
其他情况与左孩子为空情况大概相同
情况1
情况2
bool erase(const K &key)
{
if (_root == nullptr)
return false;
//先找到要删除的节点,同时记录父节点的位置
Node *cur = _root;
Node *parent = nullptr;
while (cur)
{
//存一下cur
if (cur->_key > key)
{
parent = cur;
// key < 当前节点的key, 往节点的左子树找
cur = cur->left;
}
else if (cur->_key < key)
{
parent = cur;
// 当前节点的key小于要删除的key, 往右子树找
cur = cur->right;
}
else
{
//这里说明cur->_key==key 可以进行删除了
//情况有一个孩子或者一个孩子都没有
if (cur->left == nullptr)
{
// cur左孩子为空 、右孩子可能为空,可能不为空
if (cur == _root) //情况1
{
_root = cur->right;
}
else
{
if (parent->left == cur)
{
parent->left = cur->right;
}
else
{
parent->right = cur->right;
}
}
delete cur;
}
else if (cur->right == nullptr)
{
// cur右孩子为空 左孩子可能为空,也可能不为空
if (cur == _root)
{
_root = cur->left;
}
else
{
if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
}
delete cur;
}
else
{
//左右孩子都不为空
//先找当前节点右树的最小节点
Node *parent = cur;
Node *min = cur->right;
while (min->left)
{
parent = min;
min = min->left;
}
//找到了右树的最左节点
//如果是根节点、比如删除8,那么min现在是10,parent=8
std::swap(min->_key, cur->_key);
//如果删除3、
if (parent->left == min)
{
// parent的左等于min,比如删除
parent->left = min->right;
}
else
{
parent->right = min->right;
}
delete min;
}
return true;
}
}
//走到这里说明数中没有要删除的节点
return false;
}
过程:
分三种情况
bool _erase_r(Node *&root, const K &key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _erase_r(root->left, key);
}
else if (root->_key < key)
{
return _erase_r(root->right, key);
}
else
{
//就是当前节点
Node *del = root;
if (root->left == nullptr)
{
root = root->right;
}
else if (root->right == nullptr)
{
root = root->left;
}
else
{
//左右都不为空
Node *min = root->right;
while (min)
{
min = min->left;
}
std::swap(min->_key, root->_key);
//注意
return _erase_r(root->right, key);
}
delete del;
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 _find_r(Node *root, const K &key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _find_r(root->left, key);
}
else if (root->_key < key)
{
return _find_r(root->right, key);
}
else
{
return true;
}
}
孙大统的个人网站