企业微信邮箱登录入口福州seo推广优化

当前位置： 首页 > news >正文

企业微信邮箱登录入口,福州seo推广优化,怎么做百度搜到的网站免费的,免费的企业网站二叉搜索树的概念 二叉搜索树又称为二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树#xff1a; 若它的左子树不为空#xff0c;则左子树上所有结点的值都小于根结点的值。若它的右子树不为空#xff0c;则右子树上所有结点的值都大于根结…二叉搜索树的概念 二叉搜索树又称为二叉排序树它或者是一棵空树或者是具有以下性质的二叉树 若它的左子树不为空则左子树上所有结点的值都小于根结点的值。若它的右子树不为空则右子树上所有结点的值都大于根结点的值。它的左右子树也分别是二叉搜索树。 由于二叉搜索树中每个结点左子树上所有结点的值都小于该结点的值右子树上所有结点的值都大于该结点的值因此对二叉搜索树进行中序遍历后得到的是升序序列也就不难理解了。 二叉搜索树的操作 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到空还没找到这个值不存在。 二叉搜索树的插入 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除 情况d在被删除的结点的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题–替换法删除 二叉搜索树的实现 结点类 要实现二叉搜索树我们首先需要实现一个结点类 结点类当中包含三个成员变量结点值、左指针、右指针。结点类当中只需实现一个构造函数即可用于构造指定结点值的结点。 templateclass K // 二叉树的结构 struct BSTreeNode {BSTreeNodeK *_left; //左孩子指针BSTreeNodeK *_right;//右孩子指针K _key; //结点值//构造函数BSTreeNode(const K key 0): _left(nullptr), _right(nullptr), _key(key) {} };BSTree类 #pragma once #include iostream using namespace std;templateclass K class BSTree {typedef BSTreeNodeK Node;public:BSTree() default;//指定强制生成默认构造//默认构造BSTree();//拷贝构造BSTree(const BSTreeK t);//赋值重载BSTreeK operator(BSTreeK t);//析构函数~BSTree();//插入key值bool Insert(const K key);//查找key值bool Find(const K key);//删除key值bool Erase(const K key);//递归查找 bool FindR(const K key);//递归插入bool InsertR(const K key);//递归删除bool EraseR(const K key);//中序遍历void InOrder(); private:Node *_root nullptr;// 二叉搜索树的根 };构造函数 //构造一个空树 BSTree(): _root(nullptr) { }拷贝构造函数 拷贝构造函数也并不难拷贝一棵和所给二叉搜索树相同的树即可。 Node *Copy(Node *root) {if (root nullptr) {return nullptr;}//前序遍历copy树Node *newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot; }//构造树的深拷贝 BSTree(const BSTreeK t) {_root Copy(t._root); }赋值运算符重载函数 对于赋值运算符重载函数下面提供两种实现方法 传统写法 //传统写法 const BSTreeK operator(const BSTreeK t) {//避免自己拷贝自己if (this ! t) {_root Copy(t._root);}return *this;//为了支持连续赋值 }现代写法 //现代写法 BSTreeK operator(BSTreeK t) {swap(_root, t._root);return *this; }赋值运算符重载函数的现代写法非常精辟函数在接收右值时并没有使用引用进行接收因为这样可以间接调用BSTree的拷贝构造函数完成拷贝构造。我们只需将这个拷贝构造出来的对象的二叉搜索树与this对象的二叉搜索树进行交换就相当于完成了赋值操作而拷贝构造出来的对象t会在该赋值运算符重载函数调用结束时自动析构。 注意两种方法都是深拷贝效率并没有什么区别 析构函数 析构函数完成对象中二叉搜索树结点的释放注意释放时采用后序释放当二叉搜索树中的结点被释放完后将对象当中指向二叉搜索树的指针及时置空即可。 void Destroy(Node *root) {if (root nullptr) {return;}//后序遍历析构Destroy(root-_left);Destroy(root-_right);delete root;root nullptr; }//析构函数 ~BSTree() {Destroy(_root); }查找函数 根据二叉搜索树的特性我们在二叉搜索树当中查找指定值的结点的方式如下 若树为空树则查找失败返回nullptr。若key值小于当前结点的值则应该在该结点的左子树当中进行查找。若key值大于当前结点的值则应该在该结点的右子树当中进行查找。若key值等于当前结点的值则查找成功返回对应结点的地址。 非递归实现 // 查找 bool Find(const K key) {Node *cur _root;while (cur) {if (key cur-_key) {cur cur-_right;} else if (key cur-_key) {cur cur-_left;} else {return true;}}return false; }递归实现 bool _FindR(Node *root, const K key) {if (root nullptr) {return false;}if (root-_key key) {return true;}if (key root-_key) {return _FindR(root-_right, key);} else {return _FindR(root-_left, key);} }bool FindR(const K key) {return _FindR(_root, key); }插入函数 根据二叉搜索树的性质其插入操作非常简单 如果是空树则直接将插入结点作为二叉搜索树的根结点。 如果不是空树则按照二叉搜索树的性质进行结点的插入。 若不是空树插入结点的具体操作如下 若待插入结点的值小于根结点的值则需要将结点插入到左子树当中。若待插入结点的值大于根结点的值则需要将结点插入到右子树当中。若待插入结点的值等于根结点的值则插入结点失败。 如此进行下去直到找到与待插入结点的值相同的结点判定为插入失败或者最终插入到某叶子结点的左右子树当中即空树当中。 非递归实现 使用非递归方式实现二叉搜索树的插入函数时我们需要定义一个parent指针该指针用于标记待插入结点的父结点。这样一来当我们找到待插入结点的插入位置时才能很好的将待插入结点与其父结点连接起来。 但是需要注意在连接parent和cur时需要判断应该将cur连接到parent的左边还是右边。 bool Insert(const K key) {// 如果根一开始就为nullptr那么就直接构建初始的根if (_root nullptr) {_root new Node(key);return true;}// 如果_root不为nullptr那么就从根开始遍历找适合的位置Node *parent nullptr;// parent跟着cur遍历找到合适的位置充当插入的父亲节点Node *cur _root;while (cur) {//key cur-_key 需要走左子树//key cur-_key 需要走右子树if (key cur-_key) {parent cur; //记录父亲结点cur cur-_left;//走左树} else if (key cur-_key) {parent cur;cur cur-_right;//走右数} else {// 如果key cur-_key 那么就直接返回false二叉搜索树的值不允许相同return false;}}// 找到后就开始链接cur new Node(key);// 这里不知道cur最终走到了parent的左边还是右边所以还要进行判断// keyparent-_key 链接右树// keyparent-_key 链接左树if (key parent-_key) {parent-_right cur;//右树} else if (key parent-_key) {parent-_left cur;//左树}return true; }递归实现 递归实现二叉搜索树的插入操作也是很简单的但是要特别注意的一点就是递归插入函数的子函数接收参数root时必须采用引用接收因为只有这样我们才能将二叉树当中的各个结点连接起来。 bool _InsertR(Node *root, const K key) {if (root nullptr) {root new Node(key);return root;}if (key root-_key) {return _InsertR(root-_right, key);} else if (key root-_key) {return _InsertR(root-_left, key);} else {return false;} }删除函数 二叉搜索树的删除函数是最难实现的若是在二叉树当中没有找到待删除结点则直接返回false表示删除失败即可但若是找到了待删除结点此时就有以下三种情况 待删除结点的左子树为空待删除结点的左右子树均为空包含在内。待删除结点的右子树为空。待删除结点的左右子树均不为空。 下面我们分别对这三种情况进行分析处理 1、待删除结点的左子树为空 若待删除结点的左子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的右孩子结点然后再将该结点释放便完成了该结点的删除进行删除操作后仍保持二叉搜索树的特性。 2、待删除结点的右子树为空 若待删除结点的右子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的左孩子结点然后再将该结点释放便完成了该结点的删除进行删除操作后仍保持二叉搜索树的特性。 3、待删除结点的左右子树均不为空 若待删除结点的左右子树均不为空那么当我们在二叉搜索树当中找到该结点后可以使用替换法进行删除。 可以将让待删除结点左子树当中值最大的结点或是待删除结点右子树当中值最小的结点代替待删除结点被删除下面都以后者为例然后将待删除结点的值改为代替其被删除的结点的值即可。而代替待删除结点被删除的结点必然左右子树当中至少有一个为空树因此删除该结点的方法与前面说到的情况一和情况二的方法相同。 注意只能是待删除结点左子树当中值最大的结点或是待删除结点右子树当中值最小的结点代替待删除结点被删除因为只有这样才能使得进行删除操作后的二叉树仍保持二叉搜索树的特性。 非递归函数 // 删除 bool Erase(const K key) {Node *parent nullptr;Node *cur _root;while (cur) {if (key cur-_key) {parent cur;cur cur-_right;} else if (key cur-_key) {parent cur;cur cur-_left;} else {// 开始删除// 1.如果要删除的cur左边是nullptr那么我们就进行判断判断cur在parent的左子树还是右子树// 如果是左子树那么就由parent的left指向cur的右子树如果是右子树就由parent的right指向cur的右子树if (cur-_left nullptr) {// if (parent nullptr)if (cur _root) {_root cur-_right;} else {if (parent-_left cur) {parent-_left cur-_right;} else {parent-_right cur-_right;}}delete cur;} else if (cur-_right nullptr) {// 2.cur的右边为nullptr// if (parent nullptr)if (cur _root) {_root cur-_left;} else {if (parent-_left cur) {parent-_left cur-_left;} else {parent-_right cur-_left;}}delete cur;} else {// 都不为nullptr,替代法用被删除的cur的左子树的最大节点右子树的最大节点替换// 找cur右子树的最大节点Node *pminRight cur;Node *minRight cur-_right;// 找右子树右子树的最小位置在右子树的左边while (minRight-_left) {pminRight minRight;minRight minRight-_left;}// 找到最小的值赋值给curcur-_key minRight-_key;// pminRight-_leftminRight 那么左边已经是最小了所以minRight的左子树肯定为空了// 那么可能minRight还有右子树所以需要pinRight来领养if (pminRight-_left minRight) {pminRight-_left minRight-_right;} else {// 如果不是比如删除根节点那么就需要将pminRight-_right指向minRight-right(最小值左边一定为NULL。不需要领养)//minRight是其父结点的右孩子pminRight-_right minRight-_right;}delete minRight;}return true;}}return false; }递归函数 递归实现二叉搜索树的删除函数的思路如下 若树为空树则结点删除失败返回false。若所给key值小于树根结点的值则问题变为删除左子树当中值为key的结点。若所给key值大于树根结点的值则问题变为删除右子树当中值为key的结点。若所给key值等于树根结点的值则根据根结点左右子树的存在情况不同进行不同的处理。 bool _EraseR(Node *root, const K key) {if (root nullptr)return false;if (key root-_key) {return _EraseR(root-_right, key);} else if (key root-_key) {return _EraseR(root-_left, key);} else {Node *del root;//开始准备删除root谁上层root-_left/_right的引用if (root-_right nullptr) {//root是上层的左右子树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);//转换在子树去删除//这里不能传maxleftmaxleft是局部变量return _EraseR(root-_left, key);}delete del;return true;} }完整代码 //BSTree.h #pragma once #include iostream using namespace std;templateclass K // 二叉树的结构 struct BSTreeNode {BSTreeNodeK *_left; //左孩子指针BSTreeNodeK *_right;//右孩子指针K _key; //结点值//构造函数BSTreeNode(const K key 0): _left(nullptr), _right(nullptr), _key(key) {} };templateclass K class BSTree {typedef BSTreeNodeK Node;public:BSTree() default;//指定强制生成默认构造//默认构造,构造一个空树//构造树的深拷贝BSTree(const BSTreeK t) {_root Copy(t._root);}//传统写法const BSTreeK operator(const BSTreeK t) {//避免自己拷贝自己if (this ! t) {_root Copy(t._root);}return *this;//为了支持连续赋值}//现代写法,接收一个t的拷贝,临时对象,然后进行交换BSTreeK operator(BSTreeK t) {swap(_root, t._root);return *this;}//析构函数~BSTree() {Destroy(_root);}bool Insert(const K key) {// 如果根一开始就为nullptr那么就直接构建初始的根if (_root nullptr) {_root new Node(key);return true;}// 如果_root不为nullptr那么就从根开始遍历找适合的位置Node *parent nullptr;// parent跟着cur遍历找到合适的位置充当插入的父亲节点Node *cur _root;while (cur) {//key cur-_key 需要走左子树//key cur-_key 需要走右子树if (key cur-_key) {parent cur; //记录父亲结点cur cur-_left;//走左树} else if (key cur-_key) {parent cur;cur cur-_right;//走右数} else {// 如果key cur-_key 那么就直接返回false二叉搜索树的值不允许相同return false;}}// 找到后就开始链接cur new Node(key);// 这里不知道cur最终走到了parent的左边还是右边所以还要进行判断// keyparent-_key 链接右树// keyparent-_key 链接左树if (key parent-_key) {parent-_right cur;//右树} else if (key parent-_key) {parent-_left cur;//左树}return true;}// 查找bool Find(const K key) {Node *cur _root;while (cur) {if (key cur-_key) {cur cur-_right;} else if (key cur-_key) {cur cur-_left;} 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-_right;} else if (key cur-_key) {parent cur;cur cur-_left;} else {// 开始删除// 1.如果要删除的cur左边是nullptr那么我们就进行判断判断cur在parent的左子树还是右子树// 如果是左子树那么就由parent的left指向cur的右子树如果是右子树就由parent的right指向cur的右子树if (cur-_left nullptr) {// if (parent nullptr)if (cur _root) {_root cur-_right;} else {if (parent-_left cur) {parent-_left cur-_right;} else {parent-_right cur-_right;}}delete cur;} else if (cur-_right nullptr) {// 2.cur的右边为nullptr// if (parent nullptr)if (cur _root) {_root cur-_left;} else {if (parent-_left cur) {parent-_left cur-_left;} else {parent-_right cur-_left;}}delete cur;} else {// 都不为nullptr,替代法用被删除的cur的左子树的最大节点右子树的最大节点替换// 找cur右子树的最大节点Node *pminRight cur;Node *minRight cur-_right;// 找右子树右子树的最小位置在右子树的左边while (minRight-_left) {pminRight minRight;minRight minRight-_left;}// 找到最小的值赋值给curcur-_key minRight-_key;// pminRight-_leftminRight 那么左边已经是最小了所以minRight的左子树肯定为空了// 那么可能minRight还有右子树所以需要pinRight来领养if (pminRight-_left minRight) {pminRight-_left minRight-_right;} else {// 如果不是比如删除根节点那么就需要将pminRight-_right指向minRight-right(最小值左边一定为NULL。不需要领养)//minRight是其父结点的右孩子pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;}bool _FindR(Node *root, const K key) {if (root nullptr) {return false;}if (root-_key key) {return true;}if (key root-_key) {return _FindR(root-_right, key);} else {return _FindR(root-_left, key);}}Node *Copy(Node *root) {if (root nullptr) {return nullptr;}//前序遍历copy树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(const K key) {return _FindR(_root, key);}bool _InsertR(Node *root, const K key) {if (root nullptr) {root new Node(key);return root;}if (key root-_key) {return _InsertR(root-_right, key);} else if (key root-_key) {return _InsertR(root-_left, key);} else {return false;}}bool InsertR(const K key) {return _InsertR(_root, key);}bool _EraseR(Node *root, const K key) {if (root nullptr)return false;if (key root-_key) {return _EraseR(root-_right, key);} else if (key root-_key) {return _EraseR(root-_left, key);} else {Node *del root;//开始准备删除root谁上层root-_left/_right的引用if (root-_right nullptr) {//root是上层的左右子树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);//转换在子树去删除//这里不能传maxleftmaxleft是局部变量return _EraseR(root-_left, key);}delete del;return true;}}bool EraseR(const K key) {return _EraseR(_root, key);}// 一般调用为t.InOrder() 不传参数所以这里进行了封装void InOrder() {_InOrder(_root);cout endl;}void _InOrder(Node *root) {if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node *_root nullptr;// 二叉搜索树的根 };测试代码 #include BSTree.hvoid test_BStree1() {int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};BSTreeint t;for (auto e: a) {t.Insert(e);}t.Erase(7);t.Erase(14);t.Erase(3);t.Erase(8);t.InOrder(); }void test_BSTree2() {int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};BSTreeint t;for (auto e: a) {t.InsertR(e);}t.EraseR(7);t.EraseR(14);t.EraseR(3);t.EraseR(8);t.EraseR(6);t.InOrder(); }void test_BSTree3() {int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};BSTreeint t1;for (auto e: a) {t1.InsertR(e);}t1.InOrder();BSTreeint t2(t1);t2.InOrder(); }int main() {test_BSTree3();return 0; }二叉搜索树的应用 K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV模型每一个关键码key都有与之对应的值Value即Key,Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word,chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是就构成一种键值对。
KV结构的二叉搜索树 #include iostream #include string using namespace std; // 改造二叉搜索树为KV结构s templateclass K, class V struct BSTNode {BSTNode(const K key K(), const V value V()): _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value) {}BSTNodeK, V *_pLeft;BSTNodeK, V *_pRight;K _key;V _value };templateclass K, class V class BSTree {typedef BSTNodeK, V Node;typedef Node *PNode;public:BSTree() : _pRoot(nullptr) {}PNode Find(const K key);bool Insert(const K key, const V value);bool Erase(const K key);private:PNode _pRoot; };void TestBSTree3() {// 输入单词查找单词对应的中文翻译BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(tree, 树);dict.Insert(left, 左边、剩余);dict.Insert(right, 右边);dict.Insert(sort, 排序);// 插入词库中所有单词string str;while (cin str) {BSTNodestring, string ret dict.Find(str);if (ret nullptr) {cout 单词拼写错误词库中没有这个单词: str endl;} else {cout str 中文翻译: ret-_value endl;}} } void TestBSTree4() {// 统计水果出现的次数string arr[] {苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉};BSTreestring, int countTree;for (const auto str: arr) {// 先查找水果在不在搜索树中// 1、不在说明水果第一次出现则插入水果, 1// 2、在则查找到的节点中水果对应的次数//BSTreeNodestring, int ret countTree.Find(str);auto ret countTree.Find(str);if (ret NULL) {countTree.Insert(str, 1);} else {ret-_value;}}countTree.InOrder(); }二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为LogN 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N/2 问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优答案就是使用AVL树和红黑树