自定义表单网站,深圳做三网合一网站,网站建设 淘宝详情,android应用商店目录
一、概念
二、实现
2.1 - BST.h
2.2 - test.cpp
三、应用
四、性能分析 一、概念
二叉搜索树#xff08;BST#xff0c;Binary Search Tree#xff09;#xff0c;又称二叉排序树或二叉查找树。
二叉搜索树是一棵二叉树#xff0c;可以为空#xff1b;如果不…目录
一、概念
二、实现
2.1 - BST.h
2.2 - test.cpp
三、应用
四、性能分析 一、概念
二叉搜索树BSTBinary Search Tree又称二叉排序树或二叉查找树。
二叉搜索树是一棵二叉树可以为空如果不为空满足以下性质 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左、右子树本身也都是二叉搜索树。 二、实现
2.1 - BST.h
#pragma once
#include stack
#include iostream
templateclass K
struct BSTNode
{BSTNodeK* _left;BSTNodeK* _right;K _key;
BSTNode(const K key K()): _left(nullptr), _right(nullptr), _key(key){ }
};
templateclass K
class BST
{typedef BSTNodeK BSTNode;
public:/*---------- 构造函数和析构函数 ----------*/// 默认构造函数BST() : _root(nullptr){ }
// 拷贝构造函数实现深拷贝BST(const BSTK t){_root Copy(t._root);}
// 析构函数~BST(){Destroy(_root);}
/*---------- 赋值运算符重载 ----------*/// 利用上面写好的拷贝构造函数实现深拷贝BSTK operator(BSTK tmp){std::swap(_root, tmp._root);return *this;}
/*---------- 插入 ----------*/// 非递归写法bool Insert(const K key){if (_root nullptr){_root new BSTNode(key);return true;}
BSTNode* parent nullptr;BSTNode* cur _root;while (cur){parent cur;if (key cur-_key)cur cur-_left;else if (key cur-_key)cur cur-_right;elsereturn false;}
cur new BSTNode(key);if (key parent-_key)parent-_left cur;elseparent-_right cur;return true;}
// 递归Recursion写法bool InsertRecursion(const K key){return _InsertRecursion(_root, key);}
/*---------- 删除 ----------*/// 非递归写法bool Erase(const K key){BSTNode* parent nullptr;BSTNode* 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 (parent nullptr) // 或者 cur _root{_root cur-_right;}else{if (parent-_left cur)parent-_left cur-_right;elseparent-_right cur-_right;}}else if (cur-_right nullptr) // 右子树为空{if (parent nullptr) // 或者 cur _root{_root cur-_left;}else{if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;}}else // 左、右子树非空{// 找到左子树中关键字最大的节点或者找到右子树中关键字最小的节点BSTNode* parentLeftMax cur;BSTNode* leftMax cur-_left;while (leftMax-_right){parentLeftMax leftMax;leftMax leftMax-_right;}// 让 leftMax 指向的节点代替 cur 指向的节点然后删除 leftMax 指向的节点// 这样就转换成了上面的情况std::swap(cur-_key, leftMax-_key);if (parentLeftMax-_left leftMax) // 或者 parentLeftMax curparentLeftMax-_left leftMax-_left;elseparentLeftMax-_right leftMax-_left;cur leftMax;}delete cur;return true;}}return false;}
// 递归写法bool EraseRecursion(const K key){return _EraseRecursion(_root, key);}
/*---------- 查找 ----------*/// 非递归写法bool Search(const K key) const{BSTNode* cur _root;while (cur){if (key cur-_key)cur cur-_left;else if (key cur-_key)cur cur-_right;elsereturn true;}return false;}
// 递归写法bool SearchRecursion(const K key) const{return _SearchRecursion(_root, key);}
/*---------- 中序遍历 ----------*/// 非递归写法void InOrder() const{std::stackBSTNode* st;BSTNode* cur _root;while (cur || !st.empty()){while (cur){st.push(cur);cur cur-_left;}BSTNode* top st.top();st.pop();std::cout top-_key ;cur top-_right;}std::cout std::endl;}
// 递归写法void InOrderRecursion() const{_InOrderRecursion(_root);std::cout std::endl;}
private:BSTNode* Copy(BSTNode* root){if (root nullptr)return nullptr;
BSTNode* copyRoot new BSTNode(root-_key);copyRoot-_left Copy(root-_left);copyRoot-_right Copy(root-_right);return copyRoot;}
void Destroy(BSTNode* root){// 【注意root 为 _root 或者某个节点的左或右指针的引用】if (root nullptr)return;
Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}
bool _InsertRecursion(BSTNode* root, const K key){// 【注意root 为 _root 或者某个节点的左或右指针的引用】if (root nullptr){root new BSTNode(key);return true;}
if (key root-_key)_InsertRecursion(root-_left, key);else if (key root-_key)_InsertRecursion(root-_right, key);elsereturn false;}
bool _EraseRecursion(BSTNode* root, const K key){// 【注意root 为 _root 或者某个节点的左或右指针的引用】if (root nullptr)return false;
if (key root-_key)_EraseRecursion(root-_left, key);else if (key root-_key)_EraseRecursion(root-_right, key);else{BSTNode* tmp root;if (root-_left nullptr)root root-_right;else if (root-_right nullptr)root root-_left;else{BSTNode* leftMax root-_left;while (leftMax-_right){leftMax leftMax-_right;}std::swap(leftMax-_key, root-_key);return _EraseRecursion(root-_left, key);}delete tmp;return true;}}
bool _SearchRecursion(BSTNode* root, const K key) const{if (root nullptr)return false;
if (key root-_key)_SearchRecursion(root-_left, key);else if (key root-_key)_SearchRecursion(root-_right, key);elsereturn true;}
void _InOrderRecursion(BSTNode* root) const{if (root nullptr)return;
_InOrderRecursion(root-_left);std::cout root-_key ;_InOrderRecursion(root-_right);}
private:BSTNode* _root;
}; 2.2 - test.cpp
#include BST.h
using namespace std;
void TestBST1()
{int arr[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTint t1;for (auto e : arr){t1.Insert(e);}t1.InOrder(); // 1 3 4 6 7 8 10 13 14
BSTint t2(t1);t2.InOrder(); // 1 3 4 6 7 8 10 13 14
BSTint t3;t3 t1;t1.InOrder(); // 1 3 4 6 7 8 10 13 14
// 左子树为空t1.Erase(4);t1.InOrder(); // 1 3 6 7 8 10 13 14t1.Erase(6);t1.InOrder(); // 1 3 7 8 10 13 14// 右子树为空t1.Erase(14);t1.InOrder(); // 1 3 7 8 10 13// 左、右子树非空t1.Erase(8);t1.InOrder(); // 1 3 7 10 13
cout t1.Search(8) endl; // 0cout t1.Search(7) endl; // 1
}
void TestBST2()
{int arr[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTint t;for (auto e : arr){t.InsertRecursion(e);}t.InOrderRecursion(); // 1 3 4 6 7 8 10 13 14
// 左子树为空t.EraseRecursion(4);t.InOrderRecursion(); // 1 3 6 7 8 10 13 14t.EraseRecursion(6);t.InOrderRecursion(); // 1 3 7 8 10 13 14// 右子树为空t.EraseRecursion(14);t.InOrderRecursion(); // 1 3 7 8 10 13// 左、右子树非空t.EraseRecursion(8);t.InOrderRecursion(); // 1 3 7 10 13
cout t.SearchRecursion(8) endl; // 0cout t.SearchRecursion(7) endl; // 1
}
int main()
{TestBST1();TestBST2();return 0;
} 三、应用 K 模型结构体中只需要存储关键码 key关键码即为需要搜索到的值。 例如要判断一个单词是否拼写正确我们首先把词库中的每个单词作为 key构建一棵二叉搜索树然后在这棵二叉搜索树中检索单词是否存在若存在则表明拼写正确不存在则表明拼写错误。 KV 模型每个关键码 key都有与之对应的值 value即 key, value 的键值对。 这种模型在现实生活中也很常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文 word, Chinese 就构成一种键值对。 再比如统计单词次数统计成功后给定单词就可以快速找到其出现的次数单词与其出现的次数 word, count 就构成一种键值对。 BST.h #pragma once
#include iostream
templateclass K, class V
struct BSTNode
{BSTNodeK, V* _left;BSTNodeK, V* _right;K _key;V _value;
BSTNode(const K key K(), const V value V()): _left(nullptr), _right(nullptr), _key(key), _value(value){ }
};
templateclass K, class V
class BST
{typedef BSTNodeK, V BSTNode;
public:BST() : _root(nullptr){ }
BST(const BSTK, V t){_root Copy(t._root);}
~BST(){Destroy(_root);}
BSTK, V operator(BSTK, V tmp){std::swap(_root, tmp._root);return *this;}
bool Insert(const K key, const V value){return _Insert(_root, key, value);}
bool Erase(const K key){return _Erase(_root, key);}
BSTNode* Search(const K key) const{return _Search(_root, key);}
void InOrder() const{_InOrder(_root);std::cout std::endl;}
private:BSTNode* Copy(BSTNode* root){if (root nullptr)return nullptr;
BSTNode* copyRoot new BSTNode(root-_key, root-_value);copyRoot-_left Copy(root-_left);copyRoot-_right Copy(root-_right);return copyRoot;}
void Destroy(BSTNode* root){// 【注意root 为 _root 或者某个节点的左或右指针的引用】if (root nullptr)return;
Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}
bool _Insert(BSTNode* root, const K key, const V value){// 【注意root 为 _root 或者某个节点的左或右指针的引用】if (root nullptr){root new BSTNode(key, value);return true;}
if (key root-_key)_Insert(root-_left, key, value);else if (key root-_key)_Insert(root-_right, key, value);elsereturn false;}
bool _Erase(BSTNode* root, const K key){// 【注意root 为 _root 或者某个节点的左或右指针的引用】if (root nullptr)return false;
if (key root-_key)_Erase(root-_left, key);else if (key root-_key)_Erase(root-_right, key);else{BSTNode* tmp root;if (root-_left nullptr)root root-_right;else if (root-_right nullptr)root root-_left;else{BSTNode* leftMax root-_left;while (leftMax-_right){leftMax leftMax-_right;}std::swap(leftMax-_key, root-_key);return _Erase(root-_left, key);}delete tmp;return true;}}
BSTNode* _Search(BSTNode* root, const K key) const{if (root nullptr)return nullptr;
if (key root-_key)_Search(root-_left, key);else if (key root-_key)_Search(root-_right, key);elsereturn root;}
void _InOrder(BSTNode* root) const{if (root nullptr)return;
_InOrder(root-_left);std::cout root-_key : root-_value std::endl;_InOrder(root-_right);}
private:BSTNode* _root;
}; test.cpp #include BST_KV.h
using namespace std;
void TestBST1()
{BSTstring, string t;t.Insert(insert, 插入);t.Insert(erase, 删除);t.Insert(search, 查找);t.Insert(left, 左边);t.Insert(right, 右边);// 输入英文单词找到对应的中文string str;while (cin str){BSTNodestring, string* ret t.Search(str);if (ret)cout str 对应的中文是 ret-_value endl;elsecout 单词拼写错误词库中没有此单词 endl;}
}
void TestBST2()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };BSTstring, int t;// 统计每种水果出现的次数for (const auto str : arr){BSTNodestring, int* ret t.Search(str);if (ret nullptr)t.Insert(str, 1);elseret-_value 1;}t.InOrder();// 苹果 : 6// 西瓜: 3// 香蕉 : 2
}
int main()
{// TestBST1();TestBST2();return 0;
} 四、性能分析
在二叉搜索树的插入和删除操作中都必须先进行查找操作所以查找的效率就代表了各个操作的性能。
对含 n 个节点的二叉搜索树若每个节点查找的概率相等则二叉搜树的平均查找长度是节点在二叉搜树树的深度的函数即节点越深比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树例如 最好情况下二叉搜索树为完全二叉树或者接近完全二叉树其平均比较次数为 。
最坏情况下二叉搜索树退化为单支树或者类似单支树其平均比较次数为 。 如果退化成单支树二叉搜树的性能就丢失了那么能否改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优 后续所要学习的 AVL 树和红黑树就可以解决上述问题。
