实现过程:
注意:我们实现的是k模型
#pragma once
template<class K>
struct BinartSearchTreeNode
{
typedef BinartSearchTreeNode<K> Node;
//构造函数
BinartSearchTreeNode(const K& val)
:_left(nullptr),_right(nullptr),_val(val)
{}
//成员变量:
Node* _left;
Node* _right;
K _val;
};
template<class K>
class BSTree
{
public:
typedef BinartSearchTreeNode<K> Node;
//构造函数
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
// 强制生成默认构造
BSTree() = default;
//运算符重载
BSTree<K>& operator=(BSTree<K> t)
{
std::swap(_root, t._root);
return (*this);
}
//析构函数
~BSTree()
{
Destroy(_root);
}
//二叉搜索树迭代操作
bool find(const K& x)
{
Node* root = _root;//注意:不要操作_root
while (root)
{
if (root->_val < x)
root = root->_right;
else if (root->_val > x)
root = root->_left;
else
return true;
}
return false;
}
bool insert(const K& x)
{
Node* root = _root;
Node* parent = nullptr;
//特殊;
if (root == nullptr)
{
_root = new Node(x);//注意要改变的是_root
return true;
}
while (root)
{
if (root->_val < x)
{
parent = root;
root = root->_right;
}
else if (root->_val > x)
{
parent = root;
root = root->_left;
}
else
{
//出现相等情况
return false;
}
}
//通过比较左右确定插入位置
if (parent->_val > x)
{
//插入左边
parent->_left = new Node(x);
}
else
{
//插入右边
parent->_right = new Node(x);
}
return true;
}
//erase起始版本
bool Erase_start(const K& x)
{
Node* root = _root;
Node* parent = nullptr;
while (root)
{
if (root->_val < x)
{
parent = root;
root = root->_right;
}
else if (root->_val > x)
{
parent = root;
root = root->_left;
}
else
{
//删除位置
if (parent->_val < x)
{
//说明root在parent右子树上
if (root->_left == nullptr)
{
//特殊处理
if (root == _root)
{
root = root->_right;
}
else
{
parent->_right = root->_right;
delete root;
}
return true;
}
else if (root->_right == nullptr)
{
if (root == _root)
{
root = root->_left;
}
else
{
parent->_right = root->_left;
delete root;
}
return true;
}
else
{
//替换
//左右子树都不为空
//替换法:找root右子树中最小的元素
Node* rightminparent = root;
Node* rightmin = root->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
//替换
root->_val = rightmin->_val;
if (rightmin == rightminparent->_left)
{
rightminparent->_left = rightmin->_right;//注意:不可能是左子树
}
else
{
rightminparent->_right = rightmin->_right;//注意:不可能是左子树
}
//删除
delete rightmin;
return true;
}
}
else
{
//说明root在parent左子树上
if (root->_left == nullptr)
{
if (root == _root)
{
root = root->_right;
}
else
{
parent->_left = root->_right;
delete root;
}
return true;
}
else if (root->_right == nullptr)
{
if (root == _root)
{
root = root->_left;
}
else
{
parent->_right = root->_left;
delete root;
}
return true;
}
else
{
//左右子树都不为空
//替换法:找root右子树中最小的元素
Node* rightminparent = root;
Node* rightmin = root->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
//替换
root->_val = rightmin->_val;
if (rightmin == rightminparent->_left)
{
rightminparent->_left = rightmin->_right;//注意:不可能是左子树
}
else
{
rightminparent->_right = rightmin->_right;//注意:不可能是左子树
}
//删除
delete rightmin;
return true;
}
}
}
}
return false;
}
//erase最终版本
bool Erase(const K& x)
{
Node* root = _root;
Node* parent = nullptr;
while (root)
{
if (root->_val < x)
{
parent = root;
root = root->_right;
}
else if (root->_val > x)
{
parent = root;
root = root->_left;
}
else
{
//删除位置
if (root->_left == nullptr)
{
//判断root在parent位置
if (root == _root)
{
root = root->_right;
}
else if (root = parent->_left)
{
parent->_left = root->_right;
}
else
{
parent->_right = root->_right;
}
delete root;
return true;
}
else if (root->_right == nullptr)
{
//判断root在parent位置
if (root == _root)
{
root = root->_left;
}
else if (root = parent->_left)
{
parent->_left = root->_left;
}
else
{
parent->_right = root->_left;
}
delete root;
return true;
}
else
{
//替换
//左右子树都不为空
//替换法:找root右子树中最小的元素
Node* rightminparent = root;
Node* rightmin = root->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
//替换
root->_val = rightmin->_val;
if (rightmin == rightminparent->_left)
{
rightminparent->_left = rightmin->_right;//注意:不可能是左子树
}
else
{
rightminparent->_right = rightmin->_right;//注意:不可能是左子树
}
//删除
delete rightmin;
return true;
}
}
}
return false;
}
//二叉搜索树遍历:
void preorder()
{
_preorder(_root);
cout << endl;
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void Postorder()
{
_Postorder(_root);
cout << endl;
}
void Levelorder()
{
std::queue<Node*> _st;
Node* root = _root;
if (root == nullptr)
return;
_st.push(root);
while (!_st.empty())
{
Node* tmp = _st.front();
_st.pop();
cout << tmp->_val << " ";
if (tmp->_left)
_st.push(tmp->_left);
if (tmp->_right)
_st.push(tmp->_right);
}
cout << endl;
}
//二叉搜索树递归操作
bool FindR(const K& val)
{
return _FindR(_root, val);
}
bool InsertR(const K& val)
{
return _InsertR(_root, val);
}
bool EraseR(const K& val)
{
return _EraseR(_root, val);
}
private:
bool _FindR(Node* root, const K& x)
{
//检查
if (root == nullptr)
return false;
//利用中序遍历
if (root->_val == x)
return true;
else if (root->_val < x)
{
return _FindR(root->_right, x);
}
else if (root->_val > x)
{
return _FindR(root->_left, x);
}
else
{
return false;
}
}
bool _InsertR(Node*& root, const K& x)//精髓引用
{
//检查
if (root == nullptr)
{
root = new Node(x);
return true;
}
if (root->_val > x)
{
return _InsertR(root->_left, x);
}
else if (root->_val < x)
{
return _InsertR(root->_right, x);
}
else
{
return false;
}
}
bool _EraseR(Node*& root, const K& x)//精髓引用
{
//检查
if (root == nullptr)
return false;
if (root->_val > x)
{
return _EraseR(root->_left, x);
}
else if (root->_val < x)
{
return _EraseR(root->_right, x);
}
else
{
//找到了要删除的位置
Node* tmp = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
//两边都不为空
Node* rightmin = root->_right;
while (rightmin->_left)
{
rightmin = rightmin->_left;
}
root->_val = rightmin->_val;
return _EraseR(root->_right, x);
}
//删除所要求的节点
delete tmp;
return true;
}
}
Node* Copy(Node* root)
{
//先序遍历
if (root == nullptr)
return nullptr;
Node* newroot = new Node(root->_val);
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);
return newroot;
}
void Destroy(Node* root)
{
//后序遍历
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
//遍历
void _preorder(Node* root)
{
if (root == nullptr)
return;
cout << root->_val << " ";
_preorder(root->_left);
_preorder(root->_right);
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_val << " ";
_Inorder(root->_right);
}
void _Postorder(Node* root)
{
if (root == nullptr)
return;
_Postorder(root->_left);
_Postorder(root->_right);
cout << root->_val << " ";
}
Node* _root=nullptr;
};
我的测试文件:
#include <iostream>
#include <queue>
using namespace std;
#include "BinarySearchTree.h"
//#include "test.h"
void test_1()
{
BSTree<int> b;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
b.insert(e);
}
//检查三序遍历
b.preorder();
//b.InOrder();
b.Inorder();
b.Postorder();
}
void test_2()
{
BSTree<int> b;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
b.insert(e);
}
BSTree<int> c = b;
c.Inorder();
BSTree<int> d;
d = b;
d.Postorder();
}
void test_3()
{
BSTree<int> b;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
b.insert(e);
}
b.Erase(4);
b.Inorder();
b.Levelorder();
}
void test_5()
{
BSTree<int> b;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
b.InsertR(e);
}
b.EraseR(14);
b.Inorder();
cout << b.FindR(10) << endl;
cout << b.find(3) << endl;
}
int main()
{
test_5();
return 0;
}
最后,感谢大家的支持!!!