湖北建设厅网站临沂兰山建设局网站

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

湖北建设厅网站,临沂兰山建设局网站,企业黄页大全,查询网站建设目录 1.二叉搜索树 1.1 二叉搜索树概念 1.2 二叉搜索树操作 1.3 二叉搜索树的实现 1.4 二叉搜索树的应用 1.5 二叉搜索树的性能分析 2.二叉树进阶经典题#xff1a; 1.二叉搜索树 1.1 二叉搜索树概念 二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;…目录 1.二叉搜索树 1.1 二叉搜索树概念 1.2 二叉搜索树操作 1.3 二叉搜索树的实现 1.4 二叉搜索树的应用 1.5 二叉搜索树的性能分析 2.二叉树进阶经典题 1.二叉搜索树 1.1 二叉搜索树概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 二叉搜索树又称二叉排序树因为根据其性质我们可以知道其中序遍历是有序的。1.2 二叉搜索树操作 1. 二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 2. 二叉搜索树的插入 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 3.二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 删除方法 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除 情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题–替换法删除 1.3 二叉搜索树的实现 这里使用递归版本和非递归版本进行实现需要注意的是为了保证封装性这里大多采用子函数的形式来防止封装性被破坏。其中删除的过程最复杂 //节点类 template class K struct BSTreeNode {BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_key(key),_left(nullptr),_right(nullptr){} }; //二叉搜索树 template class K class BSTree {typedef BSTreeNodeK Node; public:BSTree():_root(nullptr){}//为了不破坏封装性采用子函数的形式不暴露根BSTree(const BSTreeK t){_root CopyTree(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 cur _root;Node* parent nullptr;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 Find(const K key){if (_root nullptr)return false;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 Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{//找到了//1.可能是左为空//2.右为空//两边都不为空if(cur-_left nullptr){//有可能删除根节点if (cur _root){_root _root-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){if (cur _root){_root _root-_right;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//都不为空//从当前节点的右子树开始找最小的值Node* minright cur-_right;Node* parent cur;while (minright-_left){parent minright;minright minright-_left;}cur-_key minright-_key;//将最小的值的节点剩下的节点链接给parentif (parent-_left minright){parent-_left minright-_right;}else{parent-_right minright-_right;}delete minright;}return true;}}return false;}//打印,为了保证其封装性可以使用子函数,采用中序遍历void Print(){PrintHelper(_root);}//递归版本的插入bool InsertR(const K key){return _InsertR(_root, key);}//递归版本的查找bool FindR(const K key){return _FindR(_root, key);}//递归版本的删除bool EraseR(const K key){return _EraseR(_root, key);} private:void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;}Node* CopyTree(Node* root){//前序建树即可if (root nullptr){return true;}Node* newRoot new Node(root-_key);newRoot-_left CopyTree(root-_left);newRoot-_right CopyTree(root-_right);return newRoot;}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;//还是分3种情况if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{//在当前节点的右子树找到最小值然后交换Node* minright root-_right;while (minright-_left){minright minright-_left;}//交换swap(minright-_key, root-_key);//在右子树中找到要删除的值return _EraseR(root-_right, key);}delete del;return true;}}bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){return _FindR(root-_left, key);}else if (root-_key key){return _FindR(root-_right, key);}else{return true;}}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;}}void PrintHelper(const Node* _root){//中序遍历if (_root nullptr)return;PrintHelper(_root-_left);cout _root-_key ;PrintHelper(_root-_right);}Node* _root nullptr; }; 1.4 二叉搜索树的应用 1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 2. KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文word, chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是word, count就构成一种键值对 KV模型代码变形这里只修改了插入和查找因为这个使用的多而且到后面的map和set会深入学习 //改造二叉搜索树变为KV模型 namespace KV {template class K, class Vstruct BSTreeNode{BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _val;BSTreeNode(const K key, const V val):_key(key), _val(val), _left(nullptr), _right(nullptr){}};template class K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public://插入bool Insert(const K key, const V val){//开始插入第一个的情况if (_root nullptr){_root new Node(key,val);return true;}Node* cur _root;Node* parent nullptr;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){if (_root nullptr)return nullptr;Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}elsereturn cur;{}}return nullptr;}private:Node* _root nullptr;}; } 下面就是KV模型的两个例子 1.在字典中查找你写的单词是否存在 void TestBSTree1(){BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(tree, 树);dict.Insert(left, 左边、剩余);dict.Insert(right, 右边);dict.Insert(sort, 排序);string str;while (cin str){//在字典中查找BSTreeNodestring,string* ret dict.Find(str);if (ret){cout ret-_val endl;}else{cout 不存在 endl;}}} 看看结果  2.统计次数常用 void TestBSTree2(){// 统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };BSTreestring, int countTree;for (const auto e : arr){//将数据插入到二叉搜索树中auto ret countTree.Find(e);if (ret nullptr){//树中没有该水果countTree.Insert(e, 1);}else{ret-_val;}}countTree.Print();} 结果  1.5 二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树   最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为logN 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N 后面我们学习了AVL树以及红黑树就可以使二叉搜索树的效率达到最高了。 2.二叉树进阶经典题 1.根据二叉树创建字符串 思路根据前序遍历我们可以通过根左子树右子树的顺序进行递归但是递归子树的时候需要注意条件如果左子树是空但是有右子树就需要保留空括号如果左子树不为空但右子树为空就不需要保留空括号。 class Solution { public:void _tree2str(TreeNode* root,string result){if(root nullptr){result ;return;}result to_string(root-val);if(root-left || root-right){result (;_tree2str(root-left,result);result );}if(root-right){result (;_tree2str(root-right,result);result );}}string tree2str(TreeNode* root) {string result;_tree2str(root,result);return result;} }; 2.二叉树的层序遍历 思路我们可以通过队列来模拟层序遍历一次输入一层的节点然后把队列中当层的元素全部弹出同时进入下一层元素我们可以通过size来控制当层元素的个数。然后把当层元素放入结果集中 class Solution { public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;if(root nullptr)return result;queueTreeNode* q;q.push(root);while(!q.empty()){vectorint tmp;int size q.size();while(size–){TreeNode* frontnode q.front();q.pop();tmp.push_back(frontnode-val);//放入左右节点if(frontnode-left){q.push(frontnode-left);}if(frontnode-right){q.push(frontnode-right);}}result.push_back(tmp);}return result;} }; 3.二叉树的最近公共祖先 思路这题可以使用回溯法来解决我们可以分别将p和q的路径存放在栈中然后通过对栈的弹出操作找到他们相同的节点。其中找路径问题就是回溯问题我们可以把每次递归的结果先保存起来如果找到就返回真就可以结束递归如果没有找到我们就继续递归当子树递归到了nullptr时我们就需要回退回退的本质就是将栈顶元素pop。 class Solution { public:bool _lowestCommonAncestor(TreeNode* root,TreeNode* p,stackTreeNode* st){if(root nullptr){return false;}st.push(root);if(root p){return true;}if(_lowestCommonAncestor(root-left,p,st)){return true;}if(_lowestCommonAncestor(root-right,p,st)){return true;}//回退st.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//回溯法stackTreeNode* pv;stackTreeNode* qv;_lowestCommonAncestor(root,p,pv);_lowestCommonAncestor(root,q,qv);while(pv.size() ! qv.size()){if(pv.size() qv.size()){pv.pop();}elseqv.pop();}while(pv.top() ! qv.top()){pv.pop();qv.pop();}return pv.top();} }; 4.二叉搜索树与双向链表 思路因为二叉搜索树的中序是有序的我们可以先递归到最小的节点然后通过中序改变它们之间的链接关系。 class Solution { public:void _Convert(TreeNode* cur,TreeNode* prev){if(cur nullptr){return;}//中序走到最小_Convert(cur-left,prev);//建立链接关系//这里是防止第一次prev为空的情况if(prev){prev-right cur;}cur-left prev;prev cur;_Convert(cur-right,prev);}TreeNode* Convert(TreeNode* root) {if(root nullptr)return nullptr;TreeNode* prev nullptr;_Convert(root,prev);//返回根while(root-left){root root-left;}return root;} };5.从前序与中序遍历序列构造二叉树 思路因为前序是可以确定根的所以我们可以在中序中找到根然后划分左右子树的区间根据前序的顺序先递归左子树再递归右子树当区间不存在时即可回退。 class Solution { public:TreeNode* _buildTree(vectorint preorder, vectorint inorder,int begin,int end,int i){if(begin end)return nullptr;//从中序中找子树区间int j begin;for(;jend;j){if(inorder[j] preorder[i])break;}TreeNode* root new TreeNode(preorder[i]);//[begin,j-1] j [j1,end]root-left _buildTree(preorder,inorder,begin,j-1,i);root-right _buildTree(preorder,inorder,j1,end,i);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {//先序找根中序找子树//采用闭区间int i 0;return _buildTree(preorder,inorder,0,inorder.size()-1,i);} }; 6.使用非递归实现二叉树的前序遍历 思路一般递归可以实现的代码使用非递归都需要使用到数据结构的栈我们可以将树分成左路节点和右树我们先迭代左路节点到空其中把每个值存放在栈中并保存到结果集中然后取栈顶元素再走右树即可。而中序遍历所需要保存的结果刚好是前序遍历栈弹出的结果代码与这个类似。 class Solution { public:vectorint preorderTraversal(TreeNode* root) {//分成两部分左路节点和右子树TreeNode* cur root;stackTreeNode* st;vectorint v;while(!st.empty() || cur){while(cur){v.push_back(cur-val);st.push(cur);cur cur-left;}//走右子树TreeNode* tmp st.top();st.pop();cur tmp-right;}return v;} }; 7.使用非递归实现二叉树的后序遍历 思路这个和前序以及中序有所不同就是在确定根的时候我们需要确定两次第一次是拿到根并走其右子树第二次拿到根的时候就可以将根从栈中弹出了。我们也可以使用结构体存放每个节点和节点被取出的次数。当然还有更巧妙的方法当我们走到右子树的最右端时我们就可以使用一个指针记录下来在当前节点回退的时候必然存在cur-right  prev这个就是用来记录的节点然后我们再把这个标记节点更新到当前节点这样就可以不断回退了。具体看代码理解 class Solution { public:vectorint postorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* st;TreeNode* cur root;TreeNode* prev nullptr;//用来记录根的右子树是否被访问while(!st.empty() || cur){while(cur){st.push(cur);cur cur-left;}TreeNode* top st.top();//如果右子树为空或者到最右端返回的时候就回收结果if(top-right nullptr || top-right prev){st.pop();v.push_back(top-val);prev top;//从最右端回来的时候起重要作用}else{//这时候要往右迭代cur top-right;}}return v;} };