网站备案 ip,自己做卖东西的网站,上海著名的网站制作公司,关于做公司官方网站域名申请目录 一、二叉搜索树的概念
二、二叉搜索树的模拟实现
1、定义节点
2、构造二叉树
3、析构二叉树
4、拷贝二叉树
5、二叉树赋值
6、插入节点
#x1f31f;【非递归方式】
#x1f31f;【递归方式】
7、打印节点 8、搜索节点
#x1f31f;【非递归方式】
…目录 一、二叉搜索树的概念
二、二叉搜索树的模拟实现
1、定义节点
2、构造二叉树
3、析构二叉树
4、拷贝二叉树
5、二叉树赋值
6、插入节点
【非递归方式】
【递归方式】
7、打印节点 8、搜索节点
【非递归方式】
【递归方式】
9、删除节点重要
【非递归方式】
【递归方式】
10、完整代码
三、二叉搜索树的应用
K模型KV模型 一、二叉搜索树的概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二、二叉搜索树的模拟实现
1、定义节点
首先需要确定二叉树的节点有左节点、和右节点以及节点的值。 2、构造二叉树 3、析构二叉树
遍历左右二叉树删除节点并将节点置为空。 4、拷贝二叉树
拷贝二叉树我们不能使用insert来一个一个插入因为inset带有筛选的功能最后结果顺序会不同的。 我们使用类似于前序遍历的方式进行拷贝遍历到哪就相当于拷贝到哪。 首先遇到空就返回。1.拷贝结点 2.递归拷贝左子树3.递归拷贝右子树。4.最后将拷贝结点返回。 5、二叉树赋值 6、插入节点
【非递归方式】 过程 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 步骤 a.当插入的结点值key要比根结点大则key需要到根的右树进行比较当key的值比根结点小则key需要到根的左树进行比较当key的值与根结点相同时则返回fasle按照这样的方式循环下去当要比较的结点为空时则就可以将结点插入到这个位置上了。每次比较中都要记录父节点的位置因为最后需要链接起来。 b.最后链接起来需要和父结点比较一下才能知道链接到父节点的左边还是右边。如果大于父节点则链接到右边如果小于父节点则连接到左边。 【递归方式】 递归实现方式的思想其实是一样的如果节点为空就创造一个节点。如果不为空就比较节点与需要插入值的大小如果比节点大就插入右边如果比节点小就插入左边遇到空就新建一个节点。当递归结束时就可以将开辟好结点链接起来。(递归的过程就是不断的在创建结点回来的过程就是不断地将结点链接起来)。这里不需要像非递归那样每次比较都需要记录父节点的位置我们这里用一个引用就可以轻松解决问题我们的指针参数使用引用即子函数的参数是递归函数参数的别名。 7、打印节点
运用递归分别打印 root 左边和右边的数值遇到空就返回。 8、搜索节点 过程 a.从根开始比较查找比根大则往右边走查找比根小则往左边走查找。如果没有找到就返回 false. b.最多查找高度次走到到空还没找到这个值不存在。 【非递归方式】 【递归方式】
当所要找的节点小于根节点时递归到左子树去找当所要找的节点大于根节点时递归到右节点去找。当等于所要找的节点时返回真。如果一直找不到则返回假。 9、删除节点重要 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下 a.当删除结点没有孩子节点时使用托孤法将父节点与空链接起来。--直接删除 b.当删除结点只有一个孩子节点时使用托孤法将父节点与孤结点链接起来。--直接删除 c.当删除结点有两个孩子节点时使用找保姆法找一个可以替代本身的结点。交换这两个结点删除这个替换结点。一般来说是将root节点和左子树的最大结点或者是右子树的最小结点相交换。--替换法删除 不管怎么删除都要遵循先查找后删除的原则当要删除的数字比root大就往右边查找当要删除的数字比root小就往左边查找。
【非递归方式】 1当只有右孩子节点时左孩子节点为空时
首先要判断父节点是不是 root然后判断要删除的节点时父节点的左孩子节点还是右孩子节点如果是左孩子节点就将删除节点的孩子节点链接上父节点的左边如果是右孩子节点就将删除节点的孩子节点链接上父节点的右边。 2当只有左孩子节点时右孩子节点为空时 3当存在两个孩子节点时
如果我们直接删除那可能需要改变树的结构这样会很复杂。我们可以找到需要删除节点的左边最大值右边最小值相交换然后再删除。 【测试运行】
【递归方式】 当key比根结点大的时候递归到右子树进行比较当key比根结点值小的时候递归到左子树进行比较当key跟结点值相同时表明找到了。找到后就要分三种情况讨论。 【当存在一个孩子结点时】 不同于非递归版本需要记录父节点递归版本不需要记录父节点因为一个引用让我们省去了很多麻烦。root 就是父节点的左指针或者右指针。托孤直接托孤给root即可。因为root就是父节点的左右指针指向。 当右子树不存在时直接将要删除结点的左子树托孤给root。当左子树不存在时直接将要删除结点的右子树托孤给root。 【当存在两个孩子结点时】 当存在两个孩子结点时还是需要使用保姆法首先找到保姆结点然后将要删除结点的值与保姆结点值交换。这样就转化成子问题了。从整棵树来看因为保姆结点和删除结点交换而改变了搜索二叉树的特性。不能使用了。 但从左子树来看还是完整的二叉搜索树并且要删除结点就只有一个孩子直接转化为上面的问题。 10、完整代码
#define _CRT_SECURE_NO_WARNINGS
#pragma oncetemplateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;//初始化BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:/*BSTree():_root(nullptr){}*/BSTree() default; // 制定强制生成默认构造BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}//~BSTree()//{// Destroy(_root);// //_root nullptr;//}//非递归方式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{return false;}}cur new Node(key);// 链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}//递归方式bool InsertR(const K key){return _InsertR(_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);}else{return false;}}//非递归方式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{return true;}}return false;}//递归方式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)return _FindR(root-_right, key);elsereturn _FindR(root-_left, key);}void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}//非递归方式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){//如果cur是根节点直接删除根节点更改root值if (cur _root){_root cur-_right;}else{//判断cur 是父节点的左孩子还是右孩子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;}else{// 找右树最小节点替代也可以是左树最大节点替代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 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-_key key){return _EraseR(root-_left, key);}else{Node* del root;// 开始准备删除if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}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;}}~BSTree(){Destroy(_root);//_root nullptr;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}BSTree(const BSTreeK t){_root Copy(t._root);}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;}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}
private:Node* _root nullptr;
};
三、二叉搜索树的应用
K模型KV模型 K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV模型每一个关键码key都有与之对应的值Value即的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是就构成一种键值对。 【测试代码】
templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public: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 (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, value);// 链接if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* 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{return cur;}}return nullptr;}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;}else{// 找右树最小节点替代也可以是左树最大节点替代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;}void InOrder(){_InOrder(_root);cout endl;}protected:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};
