【C++】搜索二叉树

目录

1. 二叉搜索树的概念

2. 时间复杂度分析

3. 插入，查找，删除的代码实现

删除的代码实现：

4. 二叉搜索树的使用场景

1. key搜索场景

2. key / value搜索场景

5. Insert 和 Find 的递归写法（了解）

1. 二叉搜索树的概念

（1）定义

二叉搜索树（Binary Search Tree，简称 BST）是一棵二叉树，满足对任意节点：

• 左子树中所有节点的值<该节点的值

• 右子树中所有节点的值>该节点的值

• 左右子树本身也都是二叉搜索树

⚠️ 注意：是比较整棵子树，不是只比较左右孩子。

（2）核心性质

1. 中序遍历（左-根-右）结果一定是升序序列——这是 BST 最重要的性质，很多题都靠它。

2. 一般不允许插入重复值。

2. 时间复杂度分析

最优：二叉搜索树为完全二叉树，其高度为 logN 。

最差：二叉搜索树退化为单只树，其高度为 N 。

所以二叉搜索树增删查改的时间复杂度为 O(N) 。

3. 插入，查找，删除的代码实现

插入查找的代码较简单，不做赘述。

bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; // 用于最后链接到一起 Node* cur = _root; while (cur) { if (key < cur->_key) // 要插入的值小于当前结点的值，应该插入到左子树 { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else return false; // 不允许插入重复的值 } cur = new Node(key); if (parent->_key > key) { parent->_left = cur; } else parent->_right = cur; return true; } bool Find(const K& key) { 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; }

删除的代码实现：

bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if(key > cur->_key) { parent = cur; cur = cur->_right; } else { if (cur->_left == nullptr) // 左为空 { if (cur == _root) { _root = _root->_right; } else { if (key < parent->_key) parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) // 右为空 { if (cur == _root) { _root = _root->_left; } else { if (key < parent->_key) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; } else // 左右均不为空 { Node* replaceparent = cur; // 不能为nullptr，因为删除的节点是根节点时 Node* replace = cur->_left; while (replace->_right) { replaceparent = replace; replace = replace->_right; } // 找到了要替换的值 swap(replace->_key, cur->_key); if (replace == replaceparent->_left) replaceparent->_left = replace->_left; else replaceparent->_right = replace->_left; delete replace; } return true; } } return false; }

思路：

4. 二叉搜索树的使用场景

1. key搜索场景

只以key作为关键码，结构中只存储key即可。

例如：检查单词是否拼写正确：将词库中的所有单词放入二叉搜索树，读取文章中的单词，查找是否存在二叉搜索树中。

2. key / value搜索场景

每一个key，都有与之对应的value。

树的结构中需要存储关键码key和对应的value。

例如：

（1）中英互译：输入英文（key），找到了对应的英文（value）

（2）统计一篇文章中某单词的出现次数：单词（key），出现次数（value）

代码举例：

template<class K,class V> struct BSTNode { BSTNode<K,V>* _left; BSTNode<K,V>* _right; K _key; V _value; BSTNode(const K& key, const V& value) :_left(nullptr) , _right(nullptr) , _key(key) , _value(value) {} }; template<class K, class V> class BST { typedef BSTNode<K, V>Node; public: BST(){} // _Destroy 和 _Copy 最好设为私有，这里为了方便观察设为公有 void _Destroy(Node* root) { if (root == nullptr) return; _Destroy(root->_left); _Destroy(root->_right); delete root; // 最好用后序遍历删除节点，否则还需额外保存孩子指针 } Node* _Copy(Node* root) { if (root == nullptr) return root; Node* copy = new Node(root->_key, root->_value); copy->_left = _Copy(root->_left); copy->_right = _Copy(root->_right); return copy; } // 拷贝构造 BST(const BST& t) { _root = _Copy(t._root); } // 析构 ~BST() { _Destroy(_root); _root = nullptr; } // 拷贝赋值 BST& operator=(BST t) { swap(t._root, _root); return *this; } 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 (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else return false; // 不允许插入重复的值 } cur = new Node(key, value); if (parent->_key > key) { parent->_left = cur; } else parent->_right = cur; return true; } Node* Find(const K& key) { 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; } void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << "：" << root->_value << endl;; _InOrder(root->_right); } bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key) { parent = cur; cur = cur->_right; } else { if (cur->_left == nullptr) // 左为空 { if (cur == _root) { _root = _root->_right; } else { if (key < parent->_key) parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) // 右为空 { if (cur == _root) { _root = _root->_left; } else { if (key < parent->_key) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; } else // 左右均不为空 { Node* replaceparent = cur; // 不能为nullptr，如果 cur->_left 本身没有右孩子，循环一次都不执行 Node* replace = cur->_left; while (replace->_right) { replaceparent = replace; replace = replace->_right; } // 找到了要替换的值 swap(replace->_key, cur->_key); if (replace == replaceparent->_left) replaceparent->_left = replace->_left; else replaceparent->_right = replace->_left; delete replace; } return true; } } return false; } private: Node* _root = nullptr; }; } ////////////////////////////////////// int main() { keyvalue::BST<string, string> dict; dict.Insert("left", "左边"); dict.Insert("right", "右边"); dict.Insert("insert", "插入"); dict.Insert("string", "字符串"); keyvalue::BST<string, string> copy = dict; copy.InOrder(); string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; keyvalue::BST<string, int> countTree; for (auto& str : arr) { auto ret = countTree.Find(str); if (ret == nullptr) { countTree.Insert(str, 1); } else { ret->_value++; } } countTree.InOrder(); return 0; }

5. Insert 和 Find 的递归写法（了解）

bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); // 用引用，直接在当前节点上修改，不需手动链接；对它赋值 = 直接改父节点成员 = 挂上新节点。 return true; } if (root->_key > key) return _InsertR(root->_left, key); if (root->_key < key) return _InsertR(root->_right, key); else return false; } bool InsertR(const K& key) { return _InsertR(_root,key); } bool _FindR(Node* root,const K& key) { if (root == nullptr) return false; if (root->_key == key) return true; if (root->_key > key) return _FindR(root->_left, key); else return _FindR(root->_right, key); } bool FindR(const K& key) { return _FindR(_root, key); }