建站工作室,wordpress点评系统,网站建设全域云,青岛做网站的公司排名本文旨在讲解如何编写一颗二叉搜索树#xff0c;包括基本的增删查改的操作。
目录
一、二叉搜索树的概念 编辑二、二叉搜索树的编写
2.1节点的编写
2.2节点的插入
2.3节点的查找
2.4节点的删除
三、二叉搜索树的应用
四、 二叉搜索树的性能分析
五、完整代码 一、…本文旨在讲解如何编写一颗二叉搜索树包括基本的增删查改的操作。
目录
一、二叉搜索树的概念 编辑二、二叉搜索树的编写
2.1节点的编写
2.2节点的插入
2.3节点的查找
2.4节点的删除
三、二叉搜索树的应用
四、 二叉搜索树的性能分析
五、完整代码 一、二叉搜索树的概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 1.若它的左子树不为空则左子树上所有节点的值都小于根节点的值 2.若它的右子树不为空则右子树上所有节点的值都大于根节点的值 3.它的左右子树也分别为二叉搜索树 二、二叉搜索树的编写
2.1节点的编写
作为一颗树他的节点应该包括储存的内容和找到其他节点的方式而因为它是一棵二叉树所以这里我采用左右孩子法去定义它的孩子。
template class K, class V
struct BSTreeNode
{BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _val;BSTreeNode(const K key,const V val)//可能存自定义类型所以用引用节省空间提升效率:_left(nullptr),_right(nullptr),_key(key),_val(val){}
};
这里我预计储存一个k_val两个类型的数据但是其实写多少个类型的数据都可以1。但是要明确的是只有一个数据参与了对应节点在二叉树中位置相关的代码。
2.2节点的插入
当节点的插入实现后我们就可以将这颗树建立起来。 根据二叉树的特性比当前节点小的在左边大的在右边。 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 代码如下
bool Insert(const K key, const V val){if (_root nullptr){_root new Node(key,val);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,val);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}
2.3节点的查找
这里我希望当节点找到后返回它对应的地址根据二叉搜索树代码如下
Node* Find(const K key){Node* cur _root;while (cur){if (key cur-_key){cur cur-_left;}else if(keycur-_key){cur cur-_right;}else{return cur;}}return nullptr;}
当然我们也可以使用递归的方式来判断一棵树中是否有某个节点 bool FindR(const K key){return _FindR(_root, key);}bool _FindR(Node* root,const K key)//带R表示是递归实现{if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_keykey){return _FindR(root-_left, key);}else{return true;}}
2.4节点的删除
节点的删除是二叉搜索树最困难的部分。首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下 情况 b 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除 情况 c 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除 情况 d 在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) 用它的值填补到被删除节点 中再来处理该结点的删除问题 -- 替换法删除 其中替换法删除就是用要删除节点的左边最大的节点或着右边最小的节点的值来替换当前节点然后情况d就转换成了情况b或c。
此外我们还应该考虑的时如果要删除的节点时根节点的情况。 bool Erase(const K key){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 // 找到了{if (cur-_left nullptr){if (cur _root)_root _root-_right;else{if (parent-_right cur)parent-_right cur-_right;else parent-_left cur-_right;}}if (cur-_right nullptr){if (cur _root)_root _root-_left;else{if (parent-_right cur)parent-_right cur-_left;else parent-_left cur-_left;}}else{//找替换节点左面最大或者右面最小parent cur;Node* leftMax cur-_left;while (leftMax-_right){parent leftMax;leftMax leftMax-_right;}std::swap(cur-_key, leftMax-_key);std::swap(cur-_val, leftMax-_val);if (parent-_left leftMax)parent-_left leftMax-_left;else parent-_right leftMax-_left;}delete cur;return true;}}return false;}
最终我们就将整颗二叉搜索树的基本功能实现了
三、二叉搜索树的应用 1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 1以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 2在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 2. KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文word, chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是word, count就构成一种键值对 四、 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为$log_2 N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N/2问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插 入关键码二叉搜索树的性能都能达到最优那么我们后续章节学习的AVL树和红黑树就可以上 场了。 五、完整代码
#pragma once
#includeiostream
using namespace std;template class K, class V
struct BSTreeNode
{BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _val;BSTreeNode(const K key,const V val)//可能存自定义类型所以用引用节省空间提升效率:_left(nullptr),_right(nullptr),_key(key),_val(val){}
};
templateclass K,class V
class BSTree
{typedef BSTreeNodeK,V Node;
public:BSTree():_root(nullptr){}bool Insert(const K key, const V val){if (_root nullptr){_root new Node(key,val);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,val);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (key cur-_key){cur cur-_left;}else if(keycur-_key){cur cur-_right;}else{return cur;}}return nullptr;}bool FindR(const K key){return _FindR(_root, key);}bool Erase(const K key){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 // 找到了{if (cur-_left nullptr){if (cur _root)_root _root-_right;else{if (parent-_right cur)parent-_right cur-_right;else parent-_left cur-_right;}}if (cur-_right nullptr){if (cur _root)_root _root-_left;else{if (parent-_right cur)parent-_right cur-_left;else parent-_left cur-_left;}}else{//找替换节点左面最大或者右面最小parent cur;Node* leftMax cur-_left;while (leftMax-_right){parent leftMax;leftMax leftMax-_right;}std::swap(cur-_key, leftMax-_key);std::swap(cur-_val, leftMax-_val);if (parent-_left leftMax)parent-_left leftMax-_left;else parent-_right leftMax-_left;}delete cur;return true;}}return false;}void InOrder()//中序遍历{_InOrder(_root);cout endl;}
private:bool _FindR(Node* root,const K key)//带R表示是递归实现{if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_keykey){return _FindR(root-_left, key);}else{return true;}}void _InOrder(Node* root){if (root NULL){return;}_InOrder(root-_left);cout root-_key :root-_val;_InOrder(root-_right);}
private:Node* _root;
};
