目录

二叉搜索树

二叉搜索树实现 

非递归插入|非递归查找

删除 

推导阶段 

非递归删除代码 

递归查找 

 递归插入

递归删除 

析构函数 

拷贝构造 

赋值重载

完整代码 

 二叉搜索树的应用

Key/Value模型 

二叉搜索树

 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
    若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
    若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
    它的左右子树也分别为二叉搜索树

二叉搜索树实现 

非递归插入|非递归查找

#include
using namespace std;
template
class BStreeNode
{
public:BStreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}BStreeNode* _left;BStreeNode* _right;K _key;
};
template
class BStree
{typedef BStreeNode 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 true;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node *root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root = nullptr;
};
int main()
{BStree t;int a[] = { 1,1,2,2,3,6,165,132,4185,123 };for (auto e : a){t.Insert(e);}t.InOrder();return 0;
}

 

可去重 

删除 

推导阶段 

 1.若要删除的节点是叶子节点，直接删除即可

2.删除节点只有一个孩子

若左为空，则让父亲节点指向该节点的右子树以删除3为例

若果要删除跟节点，而且左为空，若要删除8，我们更新根节点即可，让根节点指向10

若右为空，则让父亲指向左子树，以删除14为例

  若果要删除跟节点，而且右为空，若要删除8，让根节点指向3即可

 3.要删除的节点其左右节点都不为空

我们可以采用替换法删除节点

用左子树的最大节1点或右子树的最小节点4，若采用右树的最小节点，交换3和4删除4之后，删除3，但还有一个子节点5，我们让5成为6的左节点

若要删除8，这里采用右树最左节点的替换法，右树的最左节点就是10自己，如果这样写会有错误，while循环都不会进去，minparent就是空，而后面minParent->_left = min->_right;这个语句会出错，修正方法，让minparent一开始就是cur，并且加个判断。

这样写即可

非递归删除代码 

	bool Erase(const K& key)//删除{//若有一个子节点，删除父节点后，让子节点填充//若有俩个子节点，父节点删除后//1.用左子树的最大节点替换父节点//2.或右子树的最小节点替换父节点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}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;cur = nullptr;}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;cur = nullptr;}else//左右都为空，叶子节点,这里采用用右树的最小节点进行删除{Node* minParent = cur;Node*min = cur->_right;//cur是要删除的节点while (min->_left)//寻找最小节点{minParent = min;min = min->_left;}swap(cur->_key, min->_key);if (minParent->_left == min){minParent->_left = min->_right;}elseminParent->_right = min->_right;delete min;}return true;}}return false;}

递归查找 

	bool _FindR(Node *root,const K& key){if (root == nullptr)return false;if (root->_key < key){return _FindR(root->right, key);}else if (root->_key > key){return _FindR(root->left, key);}else{return true;}}

 递归插入

这种插入写法会导致二叉树断开

 这里的Node没有跟父节点连接上，而是创建了一个空间单独在那里

 加上引用即可

	bool _InsertR(Node*& root, const K& key){if (root == nullptr)//根为空，直接插入{root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}

递归删除 

	bool _Eraser(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _Eraser(root->_right, key);}else if (root->_key > key){return _Eraser(root->_left, 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->_left){min = min->_left;}swap(root->_key, min->_key);return _Eraser(root->_right, key);}delete del;return true;}}

析构函数 

	~BStree(){
Destory(_root);}
private:void Destory(Node*& root)//采用引用可让root置空起作用{if (root ==nullptr)return;Destory(root->_left);Destory(root->right);delete root;root=nullptr}

拷贝构造 

 注：拷贝构造也是构造，如果写了构造，编译器不会生成默认构造，会报错没有合适的默认构造

	BStree(const BStree & t){_root = _Copy(t._root);}
Node* _Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyRoot = new Node(root->_key);copyRoot->_left = _Copy(root->_left);copyRoot->_right = _Copy(root->_right);return copyRoot;}

我们需加默认构造 

默认构造也可写为BSTree()=default;

这是强制编译器生成默认构造，是C++11的用法

赋值重载

	BStree& operator=(BStree t){swap(_root, t._root);return *this;}

搜索二叉树增删查的时间复杂度是：O（h），h代表高度 

完整代码 

#include
using namespace std;
template
class BStreeNode
{
public:BStreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}BStreeNode* _left;BStreeNode* _right;K _key;
};
template
class BStree
{typedef BStreeNode 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;}void InOrder()//排序{_InOrder(_root);}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 true;}bool Erase(const K& key)//删除{//若有一个子节点，删除父节点后，让子节点填充//若有俩个子节点，父节点删除后//1.用左子树的最大节点替换父节点//2.或右子树的最小节点替换父节点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}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;cur = nullptr;}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;cur = nullptr;}else//左右都为空，叶子节点,这里采用用右树的最小节点进行删除{Node* minParent = cur;Node* min = cur->_right;//cur是要删除的节点while (min->_left)//寻找最小节点{minParent = min;min = min->_left;}swap(cur->_key, min->_key);if (minParent->_left == min){minParent->_left = min->_right;}elseminParent->_right = min->_right;delete min;}return true;}}return false;}bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _Eraser(_root, key);}~BStree(){Destory(_root);}BStree(){}BStree(const BStree& t){_root = _Copy(t._root);}BStree& operator=(BStree t){swap(_root, t._root);return *this;}
private:Node* _Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyRoot = new Node(root->_key);copyRoot->_left = _Copy(root->_left);copyRoot->_right = _Copy(root->_right);return copyRoot;}void Destory(Node*& root)//采用引用可让root置空起作用{if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}bool _Eraser(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _Eraser(root->_right, key);}else if (root->_key > key){return _Eraser(root->_left, 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->_left){min = min->_left;}swap(root->_key, min->_key);return _Eraser(root->_right, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key){if (root == nullptr)//根为空，直接插入{root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}bool _FindR(Node *root,const K& key){if (root == nullptr)return false;if (root->_key < key){return _FindR(root->right, key);}else if (root->_key > key){return _FindR(root->left, key);}else{return true;}}void _InOrder(Node *root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root = nullptr;
};
int main()
{BStree t;int a[] = { 1,1,2,2,3,6,165,132,4185,123 };for (auto e : a){t.Insert(e);}BStree copy = t;copy.InOrder();t.InOrder();BStree t1;t1.Insert(2);t1.Insert(1);t1.Insert(3);copy = t1;copy.InOrder();cout << endl;t1.InOrder();cout << endl;return 0;
}

 二叉搜索树的应用

 .K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方
式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是就构成一种键值对
KV模型通过K去找V

Key/Value模型 

namespace KeyValue
{templatestruct BSTreeNode{BSTreeNode* _left;//Key和Value绑到一起BSTreeNode* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass BSTree{typedef BSTreeNode Node;public:bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);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, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key)//查找的时候以K去查找，返回的时候返回节点指针，以便于修改{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Erase(const K& key)//用K删除{//...return true;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};

英译汉

 统计水果出现的次数

 链表相交和复杂链表的赋值可用kv模型。