【c++】二叉搜索树的模拟实现——由浅入深2.4w字详细讲解（key结构的非递归，key结构的递归，key
小编个人主页详情 template BSTreeNode} }; template typedef BSTreeNode} private: Node* _root; }; } if (_root == nullptr) { _root = new Node(key); } else { Node* parent = nullptr; Node* cur = _root; while (cur != nullptr) { if (key cur-_key) { parent = cur; cur = cur-_right; } else if (key _key) { parent->_right = new Node(key); } else { parent->_left = new Node(key); } } return true; }
中序遍历函数
- 同时二叉搜索树还有一个很重要的性质，观察下图节点，如果小编使用中序遍历去遍历这颗二叉搜索树，那么遍历后对应就为 1 3 4 6 7 8 10 13 14 ，嘶~，这个顺序，是有序的，即升序，这也是二叉搜索树的一个重要性质，所以二叉搜索树也叫做二叉排序树也就可以理解了
- 那么由于中序遍历需要使用递归，递归需要控制变量即控制节点的指针进行递归操作，那么在中序遍历的函数的参数中就要有一个参数类型是节点的指针，那么就需要显示传入最初的根节点，可是我们知道在调用中序遍历函数的时候在类外不能访问私有成员变量最初的根节点，再去单独写一个函数获取最初的根节点有没有必要
- 这时候我们可以使用一个子遍历函数的方法进行控制变量达到递归的效果，那么这个字遍历函数的参数的类型就为节点的指针，我们在遍历函数中传最初的根节点的指针给子遍历函数，那么子遍历函数就可以进行进行递归遍历
- 当根节点为空的时候我们返回即可，中序遍历是按照左子树，根，右子树的方式进行遍历，那么我们依次调用子遍历函数并传入根节点中的左指针，访问打印当前根节点中存储的值，调用子遍历函数并传入根节点中的右指针即可完成遍历
void InOrder()
{
_InOrder(_root);
cout
if (_root == nullptr)
{
return;
}
_InOrder(_root-_left);
cout _key _right);
}
查找函数
- 这里的查找是进行判断key值是否在这个二叉搜索树中，所以其对应的返回值是bool值
- 那么我们使用一个cur指针保存根节点的指针
- 那么当cur不等于空的时候使用cur进行遍历查找
- 那么就是使用key与cur节点中的值key进行比较，如果key大，那么就需要到cur节点中的右指针指向的右子树中的节点中去找，如果key小，那么就需要到cur节点中的左指针指向的左子树中的节点中去找，如果相等，那么就说明二叉搜索树中有这个值key，那么就是找到了，返回true即可
- 如果遍历到最后cur走到的空，那么说明二叉搜索树中没有对应的这个值，这时候返回false即可
bool Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key _key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
删除函数
- 进行值为key的节点的删除面临着和插入一样的问题，如果仅仅找到了那个节点，对那个节点进行了删除释放之后，那么此时它的父亲节点仍然指向它，那么由于这个节点被释放，操作权限归还给了操作系统，那么再进行访问会进行报错，所以在进行删除节点的时候我们仍然要定义一个父亲指针用于指向删除节点的父亲节点，才能进行正确的删除
- 那么同样的这里的父亲节点的指针指向空，同时定义一个cur的节点指针指向根节点，那么当cur不为空的时候遍历寻找要删除的值key即可
- 当要删除的值key大于cur指向节点的key，那么使用父亲指针保存cur指针，再让cur指针指向cur指向节点的右指针指向的节点即可，当要删除的值key小于cur指向节点的key，那么使用父亲指针保存cur指针，再让cur指针指向cur指向节点的左指针指向的节点即可，如果 当要删除的值key等于cur指向节点的key，那么就说明找到了，此时就可以进行我们繁琐的删除操作了
- 那么对于要删除的节点对于它的子节点的情况就有四种情况的，第一种情况没有子节点，第二种情况是只有一个子节点（这个子节点可能是左子节点也可能是右子节点），第三种情况是有两个子节点
- 第一种情况可以和第二种情况归为一类情况，因为它们采取处理的方法都是托孤法，即将有子节点的节点将子节点链入当前要删除节点的父节点，没有子节点的节点情况则是将空链入删除节点的父节点，这两种情况可以归为一类进行处理，那么删除时又有两种情形，第一种情形要删除的二叉搜索树是根节点，第二种情形以及要删除的是不是二叉搜索树的根节点，此时仍然不知道这个删除节点处于父亲节点的左还是右，还需要进行判断，那么请看下图小编详解
- 第三种情况是采用替换法，因为如果直接对有两个孩子的节点直接删除，那么原二叉搜索树的结构就没有办法维持，那么这时候我们我们采用的是替换法，将当前删除节点的左子树的最大节点或当前删除节点的右子树的最小节点中存储的值和要删除节点存储的值进行替换，替换完之后那么删除当前节点就从删除两个孩子节点的情况转为了删除一个孩子或没有孩子节点的情况，因为左子树的最大节点是删除节点的左子树的最右节点，那么它一定没有右孩子，可能有左孩子或没有左孩子，那么经过它和删除节点中存储的值交换后，此时就转化为了情况一或情况二进行变相的删除
- 当cur被成功删除之后即表示删除成功，返回true成功，否则则是删除失败，返回false失败
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key _key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (key > parent->_key)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (key > parent->_key)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}
else
{
Node* parentMaxLeft = cur;
Node* MaxLeft = cur->_left;
while (MaxLeft->_right != nullptr)
{
parentMaxLeft = MaxLeft;
MaxLeft = MaxLeft->_right;
}
swap(MaxLeft->_key, cur->_key);
if (parentMaxLeft == cur)
{
parentMaxLeft->_left = MaxLeft->_left;
}
else
{
parentMaxLeft->_right = MaxLeft->_left;
}
cur = MaxLeft;
}
delete cur;
return true;
}
}
return false;
}
测试
- 小编使用如下代码进行测试
void test_BSTree1()
{
int a[] = { 3,6,55,8,9,11,24,66 };
BSTree t;
for (auto e : a)
{
t.Insert(e);
}
cout
t.Erase(e);
t.InOrder();
}
}
return _InsertR(_root, key);
}
private:
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key root-_key)
{
return _InsertR(root-_right, key);
}
else if (key _left, key);
}
else
{
return false;
}
}
查找函数
- 那么接下来就是查找函数，对于查找函数的子函数不用使用节点指针引用的作为参数，因为我们不需要找父亲节点，也就是不需要插入或删除节点，只需要查找key值是否在二叉搜索树中，那么我们呢使用常规的节点的指针作为参数即可
- 那么接下来我们递归即可，在子函数中当根节点为空的时候，这时候代表我们要找的值key不在二叉搜索树中，这时候查找失败，返回false，当key值大于根节点的_key，那么传入根节点的右指针到子查找函数中去找，当key值小于根节点的_key，那么传入根节点的左指针到子查找函数中去找，当key值等于根节点的_key，那么代表找到了，查找成功，返回true即可
- 同时注意，由于查找函数需要返回是否查找成功的bool值，那么在进行递归调用子函数的时候需要返回子函数，即将最后子函数的返回值层层return返回至查找函数进行返回
public:
bool FindR(const K& key)
{
return _FindR(_root, key);
}
private:
bool _FindR(const Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _FindR(root->_right, key);
}
else if (key _key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
删除函数
- 那么由于要在二叉搜索树中找到节点，对节点进行删除，所以就势必要找到要删除节点的父节点中的左或右指针才能进行删除，那么小编这里就使用节点指针的引用作为删除函数的子删除函数的参数，这样就天然的找到了要删除节点的父节点中的左或右指针
- 那么接下来我们递归查找要删除的节点即可，在子函数中当根节点为空的时候，这时候代表我们要删除的值key不在二叉搜索树中，那么删除失败，返回false，当key值大于根节点的_key，那么传入根节点的右指针到子查找函数中去找要删除的节点，当key值小于根节点的_key，那么传入根节点的左指针到子查找函数中去找要删除的节点，当key值等于根节点的_key，那么代表找到要删除的节点了，那么此时我们进行简单的删除的操作
- 同时情况类似于非递归的删除函数的情形，当要删除的节点的右节点的指针为空，那么我们将这个删除节点root提前使用del保存一下，避免后期想要删除的时候找不到节点，同时由于引用的作用我们找到的删除节点的指针就为对应删除节点的父节点的对应的左或右指针，所以让删除节点的指针指向删除节点的左指针指向的节点即可，同理当要删除的节点的左节点的指针为空，操作类似于当要删除的节点的左节点的指针为空的情形，将删除节点root提前使用del保存一下，只不过这里要让删除节点的指向不同，这里是让删除节点指向删除节点的右指针指向的节点，那么指向完成之后，我们释放del指针指向的应该要删除的节点即可， 此时删除完成返回true
- 那么对于要删除节点的左右指针不为空的情况，那么这里同样是为了维持二叉搜索树的性质不变，我们同样要和非递归的删除函数中删除的节点的左右指针不为空的情况一样，将当前删除节点的左子树的最大节点或当前删除节点的右子树的最小节点中存储的值和要删除节点存储的值进行替换，替换完之后那么删除当前节点就从删除两个孩子节点的情况转为了对应左子树或右子树删除一个孩子或没有孩子节点的情况，那么这里小编使用循环找到左子树的最大节点的指针LeftMax，将LeftMax指向的左子树的最大节点中存储的值_key和要删除节点中存储的值_key进行交换，交换完之后，不可以直接对LeftMax进行删除，因为此时我们没有它的父亲节点的指针，也不可以将LeftMax传入并调用子删除函数进行删除，因为LeftMax仅仅是一个局部变量，它指向的是一个节点，并没有指向对应父亲节点的左或右指针，所以它的改变不会影响二叉搜索树的链接关系，所以我们要从当前函数的根节点对应的左子树的根节点开始递归删除，即使用root->_left和key传入并调用子删除函数进行删除LeftMax这个节点，因为LeftMax上节点对应的值已经被交换成了key，所以可以找到key并删除，此时LeftMax指向的节点一定是只有一个或没有子节点，因为当初它是左子树的最大节点，最大节点仅有一个或没有子节点，那么此时对含有两个节点的节点的删除就转化为了对一个节点或没有节点的节点的删除了
- 同时这里可能还会有一个疑问，为什么不传入二叉搜索树的根节点_root调用子删除函数进行删除，那么请看下图详解，所以这里我们必须传入当前函数的根节点对应的左子树的根节点的指针开始递归删除，即使用root->_left和key传入并调用子删除函数才能找到并删除LeftMax这个节点
public:
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else if (key _key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
return true;
}
else if (root->_left == nullptr)
{
root = root->_right;
return true;
}
else
{
Node* LeftMax = root->_left;
while (LeftMax->_right)
{
LeftMax = LeftMax->_right;
}
swap(root->_key, LeftMax->_key);
return _EraseR(root->_left, key);
}
delete del;
}
}
测试
- 小编使用如下代码进行测试
void test_BSTree2()
{
int a[] = { 3,6,55,8,9,11,24,66 };
BSTree t;
for (auto e : a)
{
t.InsertR(e);
}
cout
t.EraseR(e);
t.InOrder();
}
}
_root = Copy(_root, t._root);
}
private:
Node* Copy(Node* root, const Node* copy)
{
if (copy == nullptr)
{
return nullptr;
}
root = new Node(copy-_key);
root-_left = Copy(root-_left, copy-_left);
root->_right = Copy(root->_right, copy->_right);
return root;
}
赋值运算符重载函数
- 对于赋值运算符如果我们不写，编译器默认生成的同样为浅拷贝，会导致同一块空间被析构两次，面临着和拷贝构造函数同样的问题，需要我们完成深拷贝才可以
- 那么这里直接使用现代写法即可完成我们的赋值运算符重载函数的编写即可
BSTree& operator=(BSTree t)
{
swap(_root, t._root);
return *this;
}
析构函数
- 那么默认成员函数中的析构函数我们也要去显示写，因为二叉搜索树中的节点都是new出来的，我们需要遍历二叉搜索树进行逐个节点的delete释放和置空，那么这个遍历的过程一定是先遍历到最左侧的位置开始进行逐个节点的释放和置空，那么这个过程最契合的是后序遍历，所以这里们就采用后序遍历析构节点
- 同样的和拷贝构造函数一样，析构函数没有返回值，所以同样的，它要想要使用后序遍历，那么只能使用子函数，这里我们创建一个子销毁函数Destory，使用这个函数进行后序遍历的销毁
- 那么由于是控制节点进行递归删除，那么我们采用节点的指针作为参数，并且由于我们还要对二叉搜索树中的根节点和节点中的左右指针进行置空，那么这里我们采用指针的引用作为销毁函数的参数
- 当root为空的时候，我们不需要进行delete和置空了，这时候我们直接进行返回即可
- 那么当root节点不为空，那么就是要释放和置空root节点先依次释放和置空它的左孩子和右孩子，即先释放和置空root节点的左指针指向的节点，之后我们再释放和置空root右指针指向的节点，由于是递归，那么我们传入对应的指针调用Destory函数自动递归到最左侧的节点开始逐个的释放和置空，对应的那么我们传入root的左指针，接下来传入root的右指针，使用delete释放root节点，之后我们置空root节点即可，这里的root是引用，所以我们在Destory函数中置空会影响二叉搜索树中对应节点的指针，所以可以在Destory中进行置空指针
puclic:
~BSTree()
{
Destory(_root);
}
private:
void Destory(Node*& root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
测试
- 我们使用如下代码进行测试
void test_BSTree3()
{
int a[] = { 3,6,55,8,9,11,24,66 };
BSTree t;
for (auto e : a)
{
t.InsertR(e);
}
t.InOrder();
BSTree t1(t);
t1.Insert(1);
t1.InOrder();
BSTree t2;
t2 = t1;
t2.InOrder();
}
运行结果如下，正确
- 调用析构函数前，未进行节点的释放和指针的置空
- 调用析构函数后完成了节点的释放和指针的置空
五、key模型和key_value模型的二叉搜索树的应用
key模型的二叉搜索树的应用
key模型（K模型）：即只有key作为关键码，结构中存储key即可，关键码即为需要搜索到的值
- 应用场景是快速判断在不在的场景，例如判断书写英语单词是否写错，即将所有英文词库中的英语单词放到二叉搜索树中，英语单词是字符串形式，字符串可以比较大小，将这个书写的英语单词作为key，那么就可以使用二叉搜索树进行检索这个书写的英语单词是否在二叉搜索树中，如果在那么说明这个英语单词拼写正确，如果不在那么说明这个英语单词拼写错误
key_value模型的二叉搜索树的应用
key_value模型（KV模型）：每一个key关键码都有对应的值value，即通过一个值搜索去找另一值的形式
- 应用场景是：中英词典，检票系统等
- 例如将英语单词和中文存放到二叉搜索树中，那么就是以英语单词作为关键码key去对应的二叉搜索树中查找对应的value中文
- 统计人名出现的次数，例如遍历人名数组在二叉搜索树中作为关键码key进行比对，如果没有出现，那么在二叉搜索树中插入关键码key：人名，对应的值value：1，表示这个此时出现了一次，如果出现了，那么就对对应的人名对应的value加一，表示这个人名又出现了一次，这样遍历完一次人名数组中，二叉搜索树中就存储人名对应出现的次数，那么此时就可以查找人名出现的次数了
六、key_value结构的递归的模拟实现
铺垫
- 其实key_value结构的递归的模拟实现和key结构的递归的模拟实现高度相似，只不过key_value结构的二叉搜索树中存储是两个值，一个是_key，一个是_value，那么为了和二叉搜索树的key结构进行区分，小编将key_value的结构的递归的模拟实现放在key_value的命名空间中
- 插入查找删除的时候依旧还是使用_key进行查找对应的位置，那么小编在实现这个key_value结构的递归的模拟实现的代码就使用key结构的递归模拟实现的代码进行适当改变就可以实现
- 那么由于结构中的节点存储的数据多了一个，那么模板参数列表中就需要多一个模板参数V用来表示value的类型，那么就需要改变二叉搜索树的节点中的成员变量，多添加一个V类型的_value，同时二叉搜索树的节点的类型就变为了BSTreeNode，那么对应节点的指针类型就需要进行改变，同时在构造函数也需要增加一个函数参数value用于在初始化列表中对_value进行初始化
- 同时在二叉搜索树的类模板的模板参数列表中也需要增加一个模板参数V，同时二叉搜索树的类型也改变了，变成了BSTree，同时先前在二叉搜索树中还有对节点类型的typedef，那么对应也应该进行修改节点类型为BSTreeNode
namespace key_value
{
template
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
, _value(value)
{}
};
template
class BSTree
{
typedef BSTreeNode Node;
public:
BSTree()
:_root(nullptr)
{}
private:
Node* _root;
};
}
拷贝构造函数
- 拷贝构造函数只需要在原来的基础上对二叉搜索树的类型进行修改，以及new新节点的时候传入两个被拷贝的二叉搜索树的节点copy对应的成员函数_key和_value即可
public:
BSTree(const BSTree& t)
{
_root = Copy(_root, t._root);
}
private:
Node* Copy(Node* root, const Node* copy)
{
if (copy == nullptr)
{
return nullptr;
}
root = new Node(copy->_key, copy->_value);
root->_left = Copy(root->_left, copy->_left);
root->_right = Copy(root->_right, copy->_right);
return root;
}
赋值运算符重载函数
- 这里仅需要对二叉搜索树的类型进行修改即可
BSTree& operator=(BSTree t)
{
swap(_root, t._root);
return *this;
}
析构函数不需要修改
中序遍历函数不需要修改
插入函数
- 这里需要修改插入函数及其子插入函数的函数参数，增加一个value，并且new和调用子插入函数的时候增加一个value参数作为实参进行传入函数进行调用即可
public:
bool Insert(const K& key, const V& value)
{
return _InsertR(_root, key, value);
}
private:
bool _InsertR(Node*& root, const K& key, const V& value)
{
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
if (key > root->_key)
{
return _InsertR(root->_right, key, value);
}
else if (key _key)
{
return _InsertR(root->_left, key, value);
}
else
{
return false;
}
}
查找函数
- 这里与之不同的是，这里的查找要返回节点的指针，即用户查找到有key值后要拿到节点的指针去访问其中对应的_value值，那么查找函数和其子函数的的返回值这里要设定为节点的指针类型
- 那么这里当root为空的时候就代表查找失败没有key值，那么直接返回空，当找到了key值之后返回root这个指针即可
public:
Node* Find(const K& key)
{
return _FindR(_root, key);
}
private:
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (key > root->_key)
{
return _FindR(root->_right, key);
}
else if (key _key)
{
return _FindR(root->_left, key);
}
else
{
return root;
}
}
删除函数不需要修改
测试一，查找key对应的value
- 小编使用如下代码进行测试，输入中文可以得到对应的英文
- 退出循环使用ctrl+z，空格
void test_BSTree1()
{
BSTree t;
t.Insert("hello", "你好");
t.Insert("true", "真的");
t.Insert("false", "假的");
string str;
while (cin >> str)
{
BSTreeNode* word = t.Find(str);
if (word == nullptr)
{
cout
cout
string name[] = { "听安","刘勇","听安","听安","安天帝","刘勇" };
BSTree
BSTreeNode
t.Insert(str, 1);
}
else
{
tmp-_value++;
}
}
string str;
while (cin str)
{
BSTreeNode* tmp = t.Find(str);
if (tmp == nullptr)
{
cout
cout
template
BSTreeNode
}
};
template
typedef BSTreeNode}
BSTree(const BSTree
_root = Copy(_root, t._root);
}
BSTree
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
}
else
{
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (key cur-_key)
{
parent = cur;
cur = cur-_right;
}
else if (key parent->_key)
{
parent->_right = new Node(key);
}
else
{
parent->_left = new Node(key);
}
}
return true;
}
void InOrder()
{
_InOrder(_root);
cout
if (_root == nullptr)
{
return;
}
_InOrder(_root-_left);
cout _key _right);
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key _key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key _key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (key > parent->_key)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (key > parent->_key)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}
else
{
Node* parentMaxLeft = cur;
Node* MaxLeft = cur->_left;
while (MaxLeft->_right != nullptr)
{
parentMaxLeft = MaxLeft;
MaxLeft = MaxLeft->_right;
}
swap(MaxLeft->_key, cur->_key);
if (parentMaxLeft == cur)
{
parentMaxLeft->_left = MaxLeft->_left;
}
else
{
parentMaxLeft->_right = MaxLeft->_left;
}
cur = MaxLeft;
}
delete cur;
return true;
}
}
return false;
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key > root->_key)
{
return _InsertR(root->_right, key);
}
else if (key _key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(const Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _FindR(root->_right, key);
}
else if (key _key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else if (key _key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
return true;
}
else if (root->_left == nullptr)
{
root = root->_right;
return true;
}
else
{
Node* LeftMax = root->_left;
while (LeftMax->_right)
{
LeftMax = LeftMax->_right;
}
swap(root->_key, LeftMax->_key);
return _EraseR(root->_left, key);
}
delete del;
}
}
Node* Copy(Node* root, const Node* copy)
{
if (copy == nullptr)
{
return nullptr;
}
root = new Node(copy->_key);
root->_left = Copy(root->_left, copy->_left);
root->_right = Copy(root->_right, copy->_right);
return root;
}
void Destory(Node*& root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
private:
Node* _root;
};
void test_BSTree1()
{
int a[] = { 3,6,55,8,9,11,24,66 };
BSTree t;
for (auto e : a)
{
t.Insert(e);
}
cout
t.Erase(e);
t.InOrder();
}
}
void test_BSTree2()
{
int a[] = { 3,6,55,8,9,11,24,66 };
BSTree
t.InsertR(e);
}
cout
t.EraseR(e);
t.InOrder();
}
}
void test_BSTree3()
{
int a[] = { 3,6,55,8,9,11,24,66 };
BSTree
t.InsertR(e);
}
t.InOrder();
BSTree
template
BSTreeNode}
};
template
typedef BSTreeNode}
BSTree(const BSTree
_root = Copy(_root, t._root);
}
BSTree
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
}
void InOrder()
{
_InOrder(_root);
cout
if (_root == nullptr)
{
return;
}
_InOrder(_root-_left);
cout
return _InsertR(_root, key, value);
}
Node* Find(const K& key)
{
return _FindR(_root, key);
}
bool Erase(const K& key)
{
return _EraseR(_root, key);
}
private:
bool _InsertR(Node*& root, const K& key, const V& value)
{
if (root == nullptr)
{
root = new Node(key,value);
return true;
}
if (key root-_key)
{
return _InsertR(root-_right, key, value);
}
else if (key _key)
{
return _FindR(root->_left, key);
}
else
{
return root;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else if (key _key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
return true;
}
else if (root->_left == nullptr)
{
root = root->_right;
return true;
}
else
{
Node* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _EraseR(root->_left, key);
}
delete del;
}
}
Node* Copy(Node* root, const Node* copy)
{
if (copy == nullptr)
{
return nullptr;
}
root = new Node(copy->_key, copy->_value);
root->_left = Copy(root->_left, copy->_left);
root->_right = Copy(root->_right, copy->_right);
return root;
}
void Destory(Node*& root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
private:
Node* _root;
};
void test_BSTree1()
{
BSTree t;
t.Insert("hello", "你好");
t.Insert("true", "真的");
t.Insert("false", "假的");
string str;
while (cin >> str)
{
BSTreeNode* word = t.Find(str);
if (word == nullptr)
{
cout
cout
string name[] = { "听安","刘勇","听安","听安","安天帝","刘勇" };
BSTree
BSTreeNode
t.Insert(str, 1);
}
else
{
tmp-_value++;
}
}
string str;
while (cin str)
{
BSTreeNode* tmp = t.Find(str);
if (tmp == nullptr)
{
cout
cout
//key::test_BSTree3();
key_value::test_BSTree2();
return 0;
}
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。
