数据结构--二叉搜索树的实现

目录

1.二叉搜索树的概念

2.二叉搜索树的操作

二叉搜索树的插入

中序遍历(常用于排序)

二叉搜索树的查找

二叉搜索树的删除

完整二叉树代码：

二叉搜索树的应用

key/value搜索模型整体代码

---

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树 ，或者是具有以下性质的二叉树 :

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别 为二叉搜索树

注：搜索二叉树中没有重复值

二叉搜索树与其结点的代码实现

#include<iostream>
using namespace std;template<class K>//搜索二叉树的结点
struct BSTreeNode
{K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;BSTreeNode(const K& s = K()):_key(s), _left(nullptr), _right(nullptr){}
};template<class K>//搜索二叉树
class BSTree
{
public:BSTree():_root(nullptr){}//...各种操作二叉搜索树方法的实现//...
private:typedef BSTreeNode<K> Node;Node* _root;
};

2.二叉搜索树的操作

二叉搜索树的插入

这里根据二叉搜索树的概念分两种情况：

a. 树为空，则直接新增节点，赋值给 root 指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

非递归

bool Insert(const K & key){if (_root == nullptr)//情况a{_root = new Node(key);}else//情况b{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  //数字重复插入失败{return false;}}cur = new Node(key);if (parent->_key > key)//判断插入结点是在parent的左子树还是右子树{parent->_left = cur;}else{parent->_right = cur;}return true;}}

为什么要定义parent变量记录cur的父节点？

这里我们要知道，cur=new Node(key)这行代码的真正意义是给cur赋值，并没有把结点插入到树中。

注：在向二叉搜索树插入时，一定要判断是在父节点的左子树还是右子树。

递归：

public: 
bool InsertR(const K& key)
{return _insertR(_root, key);
}private:
bool _insertR(Node*& root, const K& key)
{if (root == nullptr){root = new Node(key);return true;}else{if (root->_key > key){return _insertR(root->_left, key);}else if (root->_key < key){return _insertR(root->_right, key);}else{return false;}}
}

注：由于使用递归时，需要用到成员变量_root作为实参，但是在类外面无法直接调用，因此，将递归调用的函数封装到了InsertR()里面。

为什么这里不用记录父节点，就可以插入到树中。

这里我们要注意函数的第一个变量，我们使用了引用！

这里的root就是父节点的左孩子或有孩子。

那么在非递归里面可以使用引用来达到不设置parent变量来记录父节点吗？

不能，因为在C++里引用只能指向一个。之后就不能改变指向。在递归中，我们是在传参是使用的，每次引用都重新开辟了一个新的变量，而非递归中我们一直用的是一个变量。

中序遍历(常用于排序)

public:
void Inorder()
{_Inorder(_root);
}private:
void _Inorder(Node* root)
{if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << "  ";_Inorder(root->_right);
}

这里根据二叉搜索树的概念我们清楚，其中序遍历相当于将树里面的数据按从小到大排序输出。

二叉搜索树的查找

查找方法：

a 、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b 、最多查找高度次，走到到空，还没找到，这个值不存在。

注意：

为完全二叉树时间复杂度最好，为O(log n)   

树的结点全部为左孩子或右孩子时，时间复杂度最坏，为O(n)

非递归

bool Find(const K& key)
{if (_root == nullptr)//树为空return false;Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->left;// _key>key.左走}else if (cur->_key < key){cur = cur->_right;//_key<key.右走}else{return true;//相等，找到}}return false;//没有一个相等
}

递归：

public:
Node* FindR(const K& key)
{return _FindR(_root, key);
}private:
Node* _FindR(Node* root, const K& key)
{if (root == nullptr)return nullptr;if (root->_key > key){_FindR(root->_left, key);}else if (root->_key < key){_FindR(root->_right, key);}else{return root;}
}

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回 , 否则要删除的结点可能分下面四种情

况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有 4 中情况，实际情况 a 可以与情况 b 或者 c 合并起来，因此真正的删除过程

如下：

情况 b ：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除

情况 c ：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除

情况 d ：在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点

中，再来处理该结点的删除问题 -- 替换法删除

bool Erase(const K& key)
{if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = nullptr;cur = cur->_right;}else{if (cur->_left == nullptr)//情况a{if (cur == _root)//特殊条件，等于根节点{_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->right == nullptr)//情况b{if (cur == _root) //特殊条件，等于根节点{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else            //情况c{Node* parent = cur;Node* subnode = cur->_right;while (subnode->_left){parent = subnode;subnode = subnode->_left;}swap(cur->_key, subnode->_key);if (parent->_right == subnode)   //当cur->_right->left==nullptr{parent->_right = subnode->_right;}else{parent->_left = subnode->_right;}delete subnode;}return true;}}return false;
}

递归：

public:bool EraseR(const K& key)
{_EraseR(_root,key);
}private:bool _EraseR(Node*& root, const K& key)
{if (root == nullptr){return false;}if (root->_key > key){return _EraseR(root->_left, key);}else if (root->_key < key){return _EraseR(root->_right, key);}else{if (root->_left == nullptr){Node* temp = root;root = root->_right;delete temp;}else if (root->right){Node* temp = root;root = root->_left;delete temp;}else{Node* subnode = root->_right;while (subnode->left){subnode = subnode->_left;}swap(root->_key, subnode->_key);return _EraseR(root - right, key);}}
}

完整二叉树代码：

#include<iostream>
using namespace std;template<class K>//搜索二叉树的结点
struct BSTreeNode
{K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;BSTreeNode(const K& s = K()):_key(s), _left(nullptr), _right(nullptr){}
};template<class K>//搜索二叉树
class BSTree
{
public:BSTree():_root(nullptr){}bool Insert(const K & key){if (_root == nullptr)//情况a{_root = new Node(key);}else//情况b{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  //数字重复插入失败{return false;}}cur = new Node(key);if (parent->_key > key)//判断插入结点是在parent的左子树还是右子树{parent->_left = cur;}else{parent->_right = cur;}return true;}}bool Find(const K& key){if (_root == nullptr)//树为空return false;Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->left;// _key>key.左走}else if (cur->_key < key){cur = cur->_right;//_key<key.右走}else{return true;//相等，找到}}return false;//没有一个相等}Node* FindR(const K& key){return _FindR(_root, key);}void Inorder(){_Inorder(_root);}bool InsertR(const K& key){return _insertR(_root, key);cout << endl;}bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if(cur->_key<key){parent = nullptr;cur = cur->_right;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if(cur->right==nullptr){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* subnode = cur->_right;while (subnode->_left){parent = subnode;subnode = subnode->_left;}swap(cur->_key, subnode->_key);if (parent->_right == subnode){parent->_right = subnode->_right;}else{parent->_left = subnode->_right;}delete subnode;}return true;}}return false;}bool EraseR(const K& key){return _EraseR(_root, key);}private:typedef BSTreeNode<K> Node;Node* _root;bool _insertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}else{if (root->_key > key){return _insertR(root->_left, key);}else if (root->_key < key){return _insertR(root->_right, key);}else{return false;}}}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key<<"  ";_Inorder(root->_right);}Node*_FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key > key){_FindR(root->_left, key);}else if (root->_key < key){_FindR(root->_right, key);}else{return root;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key > key){return _EraseR(root->_left, key);}else if (root->_key < key){return _EraseR(root->_right, key);}else{if (root->_left == nullptr){Node* temp = root;root = root->_right;delete temp;}else if (root->right){Node* temp = root;root = root->_left;delete temp;}else{Node* subnode = root->_right;while (subnode->left){subnode = subnode->_left;}swap(root->_key, subnode->_key);return _EraseR(root - right, key);}}}
};

二叉搜索树的应用

1. K 模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到

的值 。

比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：

以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树

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

2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该方式在现实生活中非常常见：

比如 英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英

文单词与其对应的中文 <word, chinese> 就构成一种键值对；

再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出

现次数就是 <word, count> 就构成一种键值对 。

key/value搜索模型整体代码

#pragma once
// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{BSTNode(const K& key = K(), const V& value = V()): _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;K _key;V _value
};template<class K, class V>
class BSTree
{typedef BSTNode<K, V> Node;
public:bool Insert(const K& key,const V& value){if (_root == nullptr)//情况a{_root = new Node(key,value);}else//情况b{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  //数字重复插入失败{return false;}}cur = new Node(key,value);if (parent->_key > key)//判断插入结点是在parent的左子树还是右子树{parent->_left = cur;}else{parent->_right = cur;}return true;}}bool Find(const K& key){if (_root == nullptr)//树为空return false;Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->left;// _key>key.左走}else if (cur->_key < key){cur = cur->_right;//_key<key.右走}else{return true;//相等，找到}}return false;//没有一个相等}bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = nullptr;cur = cur->_right;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->right == nullptr){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* subnode = cur->_right;while (subnode->_left){parent = subnode;subnode = subnode->_left;}swap(cur->_key, subnode->_key);if (parent->_right == subnode){parent->_right = subnode->_right;}else{parent->_left = subnode->_right;}delete subnode;}return true;}}return false;}void Inorder(){_Inorder(_root);}private:Node* _root;void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << ":"<<root->_value<<endl;_Inorder(root->_right);}
};