C++数据结构 —— 二叉搜索树

目录

1.二叉搜索树的基本概念

1.1二叉搜索树的基本特征

 2.二叉搜索树的实现

2.1数据的插入(迭代实现)

2.2数据的搜索(迭代实现)

2.3中序遍历(递归实现)

2.4数据的删除(迭代实现)

2.5数据的搜索(递归实现)

2.6数据的插入(递归实现)

2.7数据的删除(递归实现)

2.8类的完善

3.二叉搜索树的应用

4.完整代码

 二叉搜索树

1.二叉搜索树的基本概念

二叉搜索树又称二叉排序树，它可以是一颗空树。二叉搜索树的作用是搜索，排序(二叉搜索树的中序遍历是一组递增有序数据)。

1.1二叉搜索树的基本特征

如果某颗二叉树(包括空树)满足以下性质，可以作为一颗二叉搜索树：

        1.如果左子树不为空，其键值应小于根节点的键值。

        2.如果右子树不为空，其键值应大于根节点的键值。

        3.左右子树都满足上述条件。

没有二叉搜索树之前，常用的查找算法为二分查找。但是二分查找是有局限性的(必须针对有序数组)。二叉搜索树因其特性，例如我们需要查找Key值，只需要与根节点的键值做比较：若Key小于根节点的键值，则往根节点的左子树遍历；若Key值大于根节点的键值，则往根节点的右子树遍历。经计算，查找的次数等于二叉搜索树的深度。正因为如此，二叉搜索树并不是一个优秀的数据结构，因为一但碰到极端情况，二叉搜索树的搜索效率将会大打折扣。所以在往后的章节中，将会使其平衡。

 2.二叉搜索树的实现

 将二叉搜索树定义为一个类，现在将展示类的框架。往后所有的演示代码，都可以直接加入其中：

// 节点
template <class K>
struct BST_node
{BST_node<K>* _left;		//左子树BST_node<K>* _right;	//右子树K _key;BST_node(const K& _key):_key(key),_left(nullptr),_right(nullptr){}
};template <class K>		//节点键值的数据类型
class BST
{typedef BST_node<K> Node;
public:private:Node* _root;	//根节点
};

2.1数据的插入(迭代实现)

bool insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* prev = nullptr;	// cur的父节点Node* cur = _root;while (cur){if (key < cur->_key)	//如果比根节点的键值小{prev = cur;cur = cur->_left;}else if(key > cur->_key)	//如果比根节点的键值大{prev = cur;cur = cur->_right;}else{// 我们不允许插入重复的数据return false;}}// 直到遍历到空，才施行插入cur = new Node(key);if (key < prev->_key){prev->_left = cur;}else if (key > prev->_key){prev->_right = cur;}return true;
}

2.2数据的搜索(迭代实现)

bool find(const K& key)
{if (_root == nullptr){return false;}Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{// 找到了return true;}}return false;
}

2.3中序遍历(递归实现)

void MidTraval()	//此接口作公有
{__MidTraval(_root);cout << endl;
}void __MidTraval(Node* root)	//此接口做私有
{if (root == nullptr){return;}__MidTraval(root->_left);cout << root->_key << " ";__MidTraval(root->_right);
}

2.4数据的删除(迭代实现)

需要注意，要删除二叉搜索树的节点，就必须分两种情况讨论：

        1.要删除节点的左子树或右子树为空。

        2.要删除节点的左、右子树都不为空。

bool erase(const K& key)
{if (_root == nullptr){return false;}Node* prev = _root;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{// 如果左子树为空if (cur->_left == nullptr){// 假设右子树不为空，则将右子树托孤给父节点if (_root == cur){_root = _root->_right;}else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;return true;}// 如果右子树为空else if (cur->_right == nullptr){//假设左子树不为空，则将左子树托孤给父节点if (_root == cur){_root = _root->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}delete cur;return true;}// 如果左右子树都不为空else{// 假设使用右子树的最小值替代Node* prev = _root;Node* minRight = cur->_right;while (minRight->_left)		//二叉树特性，越往左越小{prev = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;// 替换好后，就要删除minRightif (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}}return false;
}

2.5数据的搜索(递归实现)

bool findR(const K& key)
{return __findR(_root, key);
}bool __findR(Node* root, const K& key)	//此接口作私有
{if (root == nullptr){return false;}if (key < root->_key){return __findR(root->_left, key);}else if (key > root->_key){return __findR(root->_right, key);}return true;
}

2.6数据的插入(递归实现)

bool insertR(const K& key)
{return __insertR(_root, key);
}bool __insertR(Node*& root, const K& key)	//此接口作私有
{if (root == nullptr){root = new Node(key);	//注意引用传参，root相当于root->left或root->right的别名return true;}if (key < root->_key){return __insertR(root->_left, key);}else if (key > root->_key){return __insertR(root->_right, key);}return false;
}

2.7数据的删除(递归实现)

bool eraseR(const K& key)
{return __eraseR(_root, key);
}bool __eraseR(Node*& root, const K& key)	//此接口作私有
{if (root == nullptr){return false;}if (key < root->_key){return __eraseR(root->_left, key);}else if (key > root->_key){return __eraseR(root->_right, key);}else{Node* del = root;if (root->_left == nullptr){// 此时root就是要删除的节点，并且是root的父节点的子节点的引用(root == root->_left...)root = root->_right;delete del;return true;}else if (root->_right == nullptr){root = root->_left;delete del;return true;}else{Node* prev = _root;Node* minRight = root->_right;while (minRight->_left)		//二叉树特性，越往左越小{prev = minRight;minRight = minRight->_left;}root->_key = minRight->_key;// 替换好后，就要删除minRightif (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}return false;
}

2.8类的完善

BST():_root(nullptr)
{}~BST()
{Destructor(_root);_root = nullptr;
}void Destructor(Node* root)	//此函数作私有
{if (root == nullptr){return;}// 后序删除Destructor(root->_left);Destructor(root->_right);delete root;
}BST(const BST<K>& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)	//此接口作私有
{if (root == nullptr){return nullptr;}Node* ret = new Node(root->_key);ret->_left = Copy(root->_left);ret->_right = Copy(root->_right);return ret;
}BST<K>& operator==(BST<K> t)	//现代写法
{swap(_root, t._root);return *this;
}

3.二叉搜索树的应用

1.K模型：

        K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。上面模拟实现的搜索就是K模型。

        例如将英文字典所有的英文单词存储二叉搜索树这个数据结构，那么可将英文单词看作关键码Key，假设我们想查找"hello"这个单词，直接去数据结构找即可。

2.KV模型：

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

        例如英汉互译，一个英文单词对应了多个汉语翻译。我们将<英文单词，中文翻译的数组>这样的键值对放入二叉搜索树中。例如查找"hello"这个单词的中文翻译，只需要查找键值对的英文单词即可。

KV模型例题：

给定下面数组，求每种水果出现的次数：

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };

第一步：先实现二叉搜索树(为了方便，这里只保留插入数据、查找和中序遍历的接口)：

namespace KV
{// 节点template <class Key,class Val>struct BST_node{BST_node<Key,Val>* _left;		//左子树BST_node<Key,Val>* _right;	//右子树Key _key;Val _val;BST_node(const Key& key,const Val& val):_key(key), _val(val),_left(nullptr), _right(nullptr){}};template <class Key,class Val>class BST{typedef BST_node<Key,Val> Node;public:bool insert(const Key& key,const Val& val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* prev = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{return false;}}cur = new Node(key,val);if (key < prev->_key){prev->_left = cur;}else if (key > prev->_key){prev->_right = cur;}return true;}Node* find(const Key& key){if (_root == nullptr){return nullptr;}Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{// 找到了return cur;}}return nullptr;}bool erase(const Key& key){if (_root == nullptr){return false;}Node* prev = _root;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (_root == cur){_root = _root->_right;}else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (_root == cur){_root = _root->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}delete cur;return true;}else{Node* prev = _root;Node* minRight = cur->_right;while (minRight->_left){prev = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}}return false;}void MidTraval()	{__MidTraval(_root);cout << endl;}private:Node* _root = nullptr;void __MidTraval(Node* root){if (root == nullptr){return;}__MidTraval(root->_left);cout << root->_key << ":" << root->_val << endl;__MidTraval(root->_right);}};
}

第二步：算法实现：

void test_count()
{KV::BST<string, int> bt;string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };for (auto& e : arr){KV::BST_node<string, int>* ret = bt.find(e);if (ret)	//不为空，证明数据结构已有{ret->_val++;	//次数++}else{bt.insert(e, 1);}}bt.MidTraval();
}

4.完整代码

 二叉搜索树