秦皇岛市教育考试院网站,网络营销推广计划,济宁 做网站,wordpress不能写文章文章目录 一. 概念二. 二叉搜索树的操作1.查找2.插入3.删除#xff08;重点#xff09;4.遍历5.拷贝构造与析构 三.二叉搜索树的递归实现1.递归查找2.递归插入3.递归删除 四.二叉搜索树的性能分析五.二叉树搜索的应用六.源码 前言#xff1a; 本章我们将认识一种新的二叉树—… 文章目录 一. 概念二. 二叉搜索树的操作1.查找2.插入3.删除重点4.遍历5.拷贝构造与析构 三.二叉搜索树的递归实现1.递归查找2.递归插入3.递归删除 四.二叉搜索树的性能分析五.二叉树搜索的应用六.源码 前言 本章我们将认识一种新的二叉树——搜索二叉树。这棵树有个神奇的功能就是会对数据自动排序且有着非常高的查找效率。搜索二叉树作为set、map的基础结构同样又是接下来将要学到的AVL树以及红黑树的实现基础非常值得我们去深入学习~ 一. 概念
叉搜索树本质上也是一种二叉树只不过多了一个约束规则——
若一棵二叉树不为空则
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为搜索二叉树
所以构建一个搜索二叉树只需要在插入结点时满足约束规则即可。
二. 二叉搜索树的操作
与二叉树相同二叉搜索树由一个个结点链接而成。每个结点包含三个成员——
template class K
struct BSTreeNode
{BSTreeNodeK* _left; //左孩子BSTreeNodeK* _right; //右孩子K _key; //键值BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};所以再定义出BSTNodeBinary Search Tree简写结构体——
template class K
class BSTree
{typedef BSTreeNodeK Node;
public:// 成员函数的实现// 插入、删除、查找...
private:Node* _root nullptr;
};接着就是各种成员函数的实现了
1.查找
搜索二叉树的查找比较简单而且更容易帮助我们理解搜索二叉树的性质所以先从查找入手。
以上图为例倘若我们要查找 7具体的思路是这样的——
7 8因此去 8 的左子树去查找7 3因此去 3 的右子树去查找7 6因此去 6 的右子树去查找7 7找到了返回true
于是我们试着着手实现一个Find函数
bool Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key) // 大于则去右子树查找cur cur-_right;else if (cur-_key key) // 小于则去左子树查找cur cur-_left;elsereturn true; // 找到返回true}return false; // 未找到返回false
}2.插入
理解了如何查找插入也就非常简单。 还是以此图为例倘若我们要插入 9 具体步骤为——
首先确定cur的位置并随时更新parent最终cur走到10的左节点的位置即cur nullptr循环结束此时patent Node*(10)最后一步new一个结Node*(key)并赋值给parent-_left即可。
bool Insert(const K key)
{// 如果是第一次插入直接new一个新结点给_rootif (_root nullptr){_root new Node(key);return true;}Node* cur _root; // cur用来定位插入的位置Node* parent cur; // 记录parent的父亲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);// 插入时依旧要进行判断if (parent-_key key)parent-_right cur;elseparent-_left cur;return true;
}3.删除重点
二叉搜索树的删除是最精华的部分。对与叶子节点例如4、7、13删除非常简单只需将自身的位置替换为nullptr即可。 如果要删除14或者10也是比较简单的因为10的左右子树只有一方为nullptr10的左子树为空所以只需要载删除的时候让父结点接管自己不为空的子树即可。
倘若要删除6或者3由于它们的左右子树都不为空删除时无法将两个子树都交给父结点情况就较为复杂。
所以此种情况我们只能想办法请一个人来接替自己的位置但是并不是谁来都能胜任这个位置的。这个接替者必须满足二叉搜索树的条件——左子树都比它小右子树都比它大。那么这个接替者的人选只能有这两个——
左子树的最大最右节点或右子树的最小最左节点
例如倘若要删除3此时有两种做法都可行——
用1替换3用7替换3
综上所述删除操作共分为一下几种情况——
左子树为空右子树为空左右子树都不为空左右子树都为空其实可以归并到1或2的情况中
bool Erase(const K key)
{Node* cur _root;Node* parent cur;while (cur){// 找到值为key的结点if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else // 找到了{ // 删除if (cur-_left nullptr) // 1.左子树为空{if (cur _root) // 根节点的删除{_root cur-_right;return true;}else{if (parent-_left cur)parent-_left cur-_right;elseparent-_right cur-_right;delete cur;}}else if (cur-_right nullptr) // 2.右子树为空{if (cur _root) // 根节点的删除{_root cur-_left;return true;}else{if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;delete cur;}}else // 左右子树都不为空{// 找左子树的最大结点 或者 右子树的最小结点Node* minRight cur-_right;Node* pminRight cur;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key; // 替换if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;
}4.遍历
二叉搜索树的遍历非常简单就是之前学习过的二叉树的中序遍历。
void InOrder()
{_InOrder(_root);cout endl;
}void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}注由于调用函数时C封装的特性需设计两个函数InOrder接口对外提供_InOrder不对外提供。
5.拷贝构造与析构 //采用前序遍历拷贝构造BSTree(const BSTreeK t){_root _Copy(t._root);}Node* _Copy(Node* root){if (root nullptr){return nullptr;}Node* CopyRoot new Node(root-_key);CopyRoot-_left _Copy(root-_left);CopyRoot-_right _Copy(root-_right);return CopyRoot;}//采用后序遍历的方式来删除从下往上删。void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;root nullptr;}~BSTree(){_Destroy(_root);}
因为拷贝构造二叉搜索树时要保证树的结构与原来树的结构一致因此采用前序遍历进行拷贝构造。
但如果写了拷贝构造之后编译器就不会生成默认的构造函数了因为拷贝构造也属于构造因此可以利用一下C11的特性强制编译器生成一个默认的拷贝构造
//强制编译器生成一个默认的拷贝构造
BSTree() default;三.二叉搜索树的递归实现
对于搜索二叉树来说上面实现的非递归版本是比递归版本更优的。此处的递归实现完全属于多余了但是作为拓展内容看一看也未尝不可。
1.递归查找
bool FindR(const K key)
{return _FindR(_root, key);
}bool _FindR(Node* root, const K key)
{if (root nullptr)return false;if (root-_key key)return true;if (root-_key key)_FindR(root-_left, key);else_FindR(root-_right, key);
}2.递归插入
bool InsertR(const K key)
{return _EraseR(_root, key);
}bool _InsertR(Node* root, const K key)
{if (root nullptr){root new Node(key);return true;}if (root-_key key)return _InsertR(root-_right, key);else if (root-_key key)return _InsertR(root-_left, key);elsereturn false;
}3.递归删除
bool EraseR(const K key)
{return _EraseR(_root, key);
}bool _EraseR(Node* root, const K key)
{if (root nullptr)return false;if (root-_key key)return _EraseR(root-_right, key);else if(root-_keykey)return _EraseR(root-_left, key);else{Node* del root;//1.右为空if (root-_right nullptr)root root-_left;//2.左为空else if (root-_left)root root-_right;//3.左右都不为空else{//找左子树最大节点交换Node* maxleft root-_left;while (maxleft-_right)maxleft maxleft-_right;//找到后先交换要删除的值与左子树最大节点的值swap(root-_key, maxleft-_key);//再递归到左子树中去删除return _EraseR(root-_left, key);}delete del;return true;}
}四.二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为 l o g 2 N log_2 N log2N最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为 N 2 \frac{N}{2} 2N 如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插 入关键码二叉搜索树的性能都能达到最优 那么我们后续章节学习的AVL树和红黑树就可以上场了。 五.二叉树搜索的应用
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对
六.源码
namespace dianxia
{template class Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};template class Kclass BSTree{typedef BSTreeNodeK Node;public://强制编译器生成构造函数BSTree() default;//拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}//赋值重载BSTreek operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}//插入节点bool Insert(const K key){//直接插入根if (_root nullptr){_root new Node(key);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{returen false;}}cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{returen true;}}return false;}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{//1.左为空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;}//2.右为空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;}//3.左右都不为空找右树最小节点或左树最大节点替代curelse{Node* pminRight cur;Node* minRight cur-_right;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight}return true;}}return false;}//递归版bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_root, key);}bool Erase(const K key){return _Erase(_root, key);}bool Insorder(){_Insorder(_root);cout endl;}protected:Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}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-_right, key);else return _FindR(root-_left, key);}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key)return _EraseR(root-_right, key);else if(root-_keykey)return _EraseR(root-_left, key);else{Node* del root;//1.右为空if (root-_right nullptr)root root-_left;//2.左为空else if (root-_left)root root-_right;//3.左右都不为空else{//找左子树最大节点交换Node* maxleft root-_left;while (maxleft-_right)maxleft maxleft-_right;//找到后先交换要删除的值与左子树最大节点的值swap(root-_key, maxleft-_key);//再递归到左子树中去删除return _EraseR(root-_left, key);}delete del;return true;}}private:Node* _root;};
}本文到此结束码文不易还请多多支持
