徐州城乡建设网站,基层医疗卫生机构本土化人才培养,贵阳网站建设报价,推广平台有哪些适用于广告文章目录 前言一、二叉搜索树1、二叉搜索树介绍2、二叉搜索树循环实现3、二叉搜索树递归实现4、二叉搜索树的性能分析5、二叉搜索树的应用6、二叉树练习题6.1 根据二叉树创建字符串6.2 二叉树的层序遍历6.3 二叉树的层序遍历 II6.4 二叉树的最近公共祖先6.5 二叉搜索树与双向链… 文章目录 前言一、二叉搜索树1、二叉搜索树介绍2、二叉搜索树循环实现3、二叉搜索树递归实现4、二叉搜索树的性能分析5、二叉搜索树的应用6、二叉树练习题6.1 根据二叉树创建字符串6.2 二叉树的层序遍历6.3 二叉树的层序遍历 II6.4 二叉树的最近公共祖先6.5 二叉搜索树与双向链表6.6 从前序与中序遍历序列构造二叉树6.7 从中序与后序遍历序列构造二叉树\6.8 二叉树的前序遍历--非递归6.9 二叉树的中序遍历--非递归6.10 二叉树的后序遍历 前言 一、二叉搜索树
1、二叉搜索树介绍
二叉搜索树BSTBinary Search Tree又称二叉排序树或二叉查找树它或者是一棵空树或者是具有以下性质的二叉树 (1). 若它的左子树不为空则左子树上所有节点的值都小于根节点的值。 (2). 若它的右子树不为空则右子树上所有节点的值都大于根节点的值。 (3). 它的左右子树也分别为二叉搜索树。
2、二叉搜索树循环实现
下面我们来实现一个二叉搜索树。 我们先定义二叉搜索树的结点和类。 下面我们来实现二叉搜索树的插入二叉搜索树的插入位置是非常确定的默认的二叉搜索树是不允许数据冗余的所以当插入相同的数据时会插入失败。 下面的实现是不行的因为我们并没有将新结点链接到二叉搜索树中。 所以我们在找到新结点的插入位置之后还需要知道这个位置的父结点然后改变父结点的孩子这样才能将新结点链接到二叉搜索树中。并且我们在创建新结点时会调用结构体BSTreeNode的构造函数所以我们需要写出BSTreeNode的构造函数。 然后我们写一个递归版的中序遍历二叉树的函数来验证我们的搜索二叉树插入是否正确。但是我们在使用BSTree类实例化的对象调用InOrder方法时发现参数没法传递因为我们需要传入二叉搜索树的根结点 _root但是根节点 _root的访问权限为private不可以在类外访问。并且因为使用递归的方法实现InOrder函数所以必须要有形参。 上面的情况我们使用缺省值的话是不行的因为缺省值必须是全局变量或者常量或者静态变量需要生命周期和程序一样即存储在静态区的变量而 _root为局部成员变量。并且在将 _ root当作缺省值时需要this指针即其实是这样的Node * root this- _ root但是在形参列表中this指针才刚定义还不能使用只有在函数内才可以使用this指针。所以实现缺省值的话是不行的。上面的情况我们一般有两种解决办法。 第一种办法可以在类中定义一个GetRoot的方法用来将 _root结点返回我们看到这种办法成功的中序遍历了二叉搜索树。但是我们一般不推荐这种写法。 第二种办法此时可以再嵌套一层这样调用中序遍历就是无参的了但是在底层调用了有参的。递归也使用的有参的。我们推荐这种写法这样当BSTree类实例化的对象调用成员函数时比较统一。 我们看到了上面中序遍历二叉搜索树打印的结果为一个升序的数组这也是二叉搜索树的特性之一所以二叉搜索树又被称为二叉排序树。下面我们来实现二叉搜索树的查找函数。 下面再来实现二叉搜索树的删除.二叉搜索树的删除的情况很多下面我们来看删除的最普遍的三种情况。 第1种情况删除的结点为叶子结点我们直接将该结点删除即可即将该结点的父结点的左孩子或右孩子指向nullptr。 第2种情况删除的结点有一个孩子结点此时可以使用托孤法即将该结点的孩子结点替代自己让该结点的父结点的左孩子或右孩子指向该结点的孩子。 第3种情况删除的结点有两个孩子结点此时删除该结点不能使用托孤法因为两个孩子没办法都托孤给父结点此时可以使用请保姆法即将该结点的左子树最大结点或右子树最小结点选为保姆然后将这两个结点的值换一下此时对保姆结点使用托孤法然后删除保姆结点这样就达到了删除指定结点的效果。可以看到我们其实并没有删除指定结点而是删除的和指定结点交换完值之后的保姆结点这就是伪删法。 当分析了删除的一些情况后下面我们就来使用代码实现。我们看到其实第1种方法和第2种方法都可以使用托孤即删除结点的左为空让父结点指向删除结点的右孩子删除结点的右为空让父节点指向删除结点的左孩子。 要删除该结点之前我们需要先找到该结点如果找不到该结点就为删除失败。 当找到要删除的结点后我们先将第1种情况和第2种情况的删除写好。因为前面我们分析了删除叶子结点也可以使用托孤法所以我们就将删除叶子结点也使用托孤法来实现。 当要删除结点的左右结点都有孩子时我们就需要使用请保姆法但是因为保姆也可能有孩子需要先进行托孤所以我们需要记录保姆的父结点。我们需要找到要删除结点的左子树的最右结点或右子树的最左结点来作为保姆。然后将要删除结点的值和保姆结点的值互换然后将保姆结点完成托孤最后删除保姆结点即可。 但是我们上面写的代码有一个情况会出错。即当cur的右孩子就是cur的右子树的最左结点时此时就不会进入while(minRight ! nullptr)的循环中那么此时pminRight就为nullptr然后执行循环后面的pminRight-left minRight时就会出现空指针错误。 所以我们不能将pminRight初始化为nullptr而应该初始化为cur。 那么我们前面将parent nullptr也会出现错误即如果出现下面的情况就会出现错误。因为当要删除的结点为根节点并且根节点的左子树或者右子树为空时那么parent nullptr就会出现空指针异常。 上面的情况我们有两种解决办法第一种解决办法就是找到根结点左子树最大值或右子树最小值来和根结点替换。 第二种解决办法就是将更新_root即让根结点不为空的孩子结点更新为新的根结点。
3、二叉搜索树递归实现
上面我们使用循环实现了二叉搜索树下面我们使用递归来实现二叉搜索树。我们先使用递归来实现FindR函数。 在类里面实现的递归函数一般都需要嵌套一层我们用递归函数实现FindR函数也是一样。 然后我们用递归实现InsertR插入函数当我们找到结点要插入的位置时我们需要将key结点与父结点链接起来但是因为适用了递归实现所以现在找不到父结点。此时我们有三种解决办法。第一种方法可以再加一个参数传递父结点。第二种方法不要判断rootnullptr而是判断root的左右孩子是否为空这样root就是父结点了。但是这两种方法都不是最好的方法。 第三种方法为最优方案在第一个参数中加一个引用即可。即将当前递归函数的root为上一个递归函数的root的左孩子或右孩子的别名那么在当前递归函数中就能通过别名来修改父结点的左孩子或右孩子的值。 下面我们再来递归实现删除。我们在实现递归删除是也将递归函数的第一个参数为Node * 类型的引用。 我们看到当删除的结点只有一个孩子或者没有孩子时我们可以很好的删除但是当删除的结点有两个孩子时我们很难将这个结点删除。 此时我们需要找到删除结点左子树的最大值或者右子树的最小值来作为保姆然后将要删除结点的值和保姆结点的值互换然后将保姆结点删除即可。删除保姆结点时我们可以再一次递归删除因为此时保姆结点只有一个结点或者没有结点所以肯定会在前面两个if语句内被删除。需要注意的是调用递归传入的值一定要为root-left或root-right不能是maxleft因为maxleft为一个临时结点指针改变maxleft的话并不会改变二叉搜索树里面的内容所以我们需要传二叉搜索树中的结点。
下面我们来看二叉搜索树的拷贝我们没有写二叉搜索树的拷贝构造函数时此时适用编译器默认生成的拷贝构造函数为浅拷贝。可以看到t1和t2指向同一棵二叉搜索树。但是我们发现程序并没有报错这是因为我们还没有写析构函数所以并不会报错。 我们先实现二叉搜索树的析构函数我们需要使用后序遍历来删除每一个结点。即先删除左孩子再删除右孩子最后删除根节点。这样才能确保每一个结点都被删除。我们适用递归来实现析构函数所以也将析构函数进行了一层嵌套其实析构函数底层调用的Destroy函数来实现结点的删除。 我们还可以将Destroy函数的参数设为Node * 这样在Destroy函数中将结点delete之后再将结点置为nullptr并且在析构函数里面就不需要将_root nullptr了。 当实现了析构函数之后适用浅拷贝的默认拷贝构造函数时就会出错因为已经delete的二叉搜索树的结点已经置为nullptr了再次delete时就会出错。 所以我们下面来实现二叉搜索树的深拷贝的拷贝构造函数。实现二叉搜索树的深拷贝就需要再创建一棵新的二叉搜索树但是我们不能复用Insert函数来创建新的二叉搜索树因为二叉搜索树顺序不一样得到的二叉搜索树也不一样。
下面我们使用递归来实现深拷贝相当于先采用前序遍历的顺序创建结点然后采用后序遍历的顺序链接结点。 当我们实现了拷贝构造函数后因为拷贝构造函数也为构造函数所以编译器就不会自动生成默认的构造函数了此时我们创建t1对象时就会因为没有默认的构造函数而报错此时我们可以写一个无参的默认构造函数也可以使用default强制生成默认构造函数。 在下面测试拷贝构造函数中我们看到t1和t2两棵二叉搜索树的根节点不同则说明此时t1和t2为两棵二叉搜索树即我们实现了深拷贝的拷贝构造函数。 下面为BSTree类的赋值运算符重载函数。这样我们就基本实现了BSTree类。
4、二叉搜索树的性能分析
二叉搜索树的插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树。我们可以看到如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插 入关键码二叉搜索树的性能都能达到最优其实我们后面要学习的AVL树和红黑树就可以上场了。
5、二叉搜索树的应用
1.K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树。 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2.KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对。 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
上面我们实现的二叉搜索树就是K模型版的下面我们简单实现一个KV模型的二叉搜索树。 我们在向二叉搜索树中插入、删除、寻找结点时还是按照key的值来进行寻找只不过在二叉搜索树的结点中还有一个value可以存一个与key对应的值。 此时我们可以根据key的值从二叉搜索树中查找结点然后打印出这个结点的value的值这就相当于我们使用英语单词在二叉搜索树中查找然后二叉搜索树的结点中存的有这个英语单词对应的中文意思我们可以根据英语单词找到中文意思。 我们也可以创建一个二叉搜索树来存水果的个数然后我们根据水果的名字就可以在二叉搜索树中找到水果的个数。并且因为我们将水果的名称作为key值了所以二叉搜索树中的排序就是按照字符串的ASCII码来进行比较的。
6、二叉树练习题
6.1 根据二叉树创建字符串
题目链接 我们可以分析出共有下面的4种情况 如果当前节点有两个孩子那我们在递归时需要在两个孩子的结果外都加上一层括号 如果当前节点没有孩子那我们不需要在节点后面加上任何括号 如果当前节点只有左孩子那我们在递归时只需要在左孩子的结果外加上一层括号而不需要给右孩子加上任何括号 如果当前节点只有右孩子那我们在递归时需要先加上一层空的括号 ‘()’\text{()}‘()’ 表示左孩子为空再对右孩子进行递归并在结果外加上一层括号。 通过上面的分析我们可以写出代码如下即直接按照分析的逻辑来写判断。
class Solution {
public:string tree2str(TreeNode* root) {string str;if(root nullptr){return str;}strto_string(root-val);//左右孩子都不为空则都加()if(root-left!nullptrroot-right!nullptr){str(;strtree2str(root-left);str);str(;strtree2str(root-right);str);}//左孩子为空右孩子为空那么都不加()else if(root-leftnullptrroot-rightnullptr){}//左孩子不为空右孩子为空只给左孩子加()右孩子不需要加else if(root-left!nullptrroot-rightnullptr){str(;strtree2str(root-left);str);}//左孩子为空右孩子不为空则给左右孩子都加()else{str(;strtree2str(root-left);str);str(;strtree2str(root-right);str);}return str;}
};
但是上面的判断比较多我们也可以使用下面的判断
class Solution {
public:string tree2str(TreeNode* root) {string str;if(root nullptr){return str;}strto_string(root-val);//只有左右都为空的时候左边才不加()所以我们可以使用下面的判断//只要不是左右都为空那么左边就加()if(root-left!nullptr || root-right!nullptr){str (;str tree2str(root-left);str );}//当左边不为空右边为空时右边才不加()。if(root-right!nullptr){str (;str tree2str(root-right);str );}return str;}
};
6.2 二叉树的层序遍历
题目链接 第一种方法我们使用两个队列一个队列记录层序遍历的结点另一个队列记录结点所在层数。
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint vv;//记录层序遍历结点queueTreeNode* s1;//记录结点所在的层数 queueint s2;//记录当前遍历的层数int count 1;s1.push(root);s2.push(count);while(!s1.empty() s1.front()!nullptr){vectorint v;//如果记录结点层数的队列中还有当前层数的结点那么继续遍历while(s2.front() count){TreeNode* front s1.front();v.push_back(front-val);s1.pop();s2.pop();//如果当前结点有左右孩子那么入栈并且左右孩子的层数要1.if(front-left!nullptr){s1.push(front-left);s2.push(count1);}if(front-right!nullptr){s1.push(front-right);s2.push(count1);}}count;vv.push_back(v);}return vv;}
};
第二种方法我们也可以使用一个队列来解决这一题即使用一个队列来记录层序遍历的结点然后使用levelSize记录这一层结点的个数即可。
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* s1;if(root!nullptr){s1.push(root);}int levelSize 1;vectorvectorint vv;while(!s1.empty()){vectorint v;while(levelSize){TreeNode* front s1.front();v.push_back(front-val);s1.pop();levelSize--;if(front-left!nullptr){s1.push(front-left);}if(front-right!nullptr){s1.push(front-right);}}levelSizes1.size();vv.push_back(v);}return vv;}
};
6.3 二叉树的层序遍历 II
题目链接 这一题我们可以使用一个巧的办法即将上一题的结果使用reverse函数反转以下即可。
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {
queueTreeNode* s1;if(root!nullptr){s1.push(root);}int levelSize 1;vectorvectorint vv;while(!s1.empty()){vectorint v;while(levelSize){TreeNode* front s1.front();v.push_back(front-val);s1.pop();levelSize--;if(front-left!nullptr){s1.push(front-left);}if(front-right!nullptr){s1.push(front-right);}}levelSizes1.size();vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};
6.4 二叉树的最近公共祖先
题目链接 这个题我们看到它的结点中没有记录给父结点如果是三叉链即记录父结点的话那么可以将这个题转换为链表相交问题了。但是这个题的结点没有提供父结点那么我们就需要先找一下规律。 我们看到如果一个孩子在我的左子树一个孩子在我的右子树那么我就是公共祖先。而第三种情况我们需要特殊判断如果我的右子树或者左子树包含一个结点那么我就是公共祖先。
class Solution {
public:bool IsInTree(TreeNode* node,TreeNode* key){if(node nullptr){return false;}if(node key){return true;}return IsInTree(node-left,key) || IsInTree(node-right,key);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr){return nullptr;}//p或q是根另一个是孩子root就是最近公共祖先if(p root || q root){return root;}bool pInLeft IsInTree(root-left,p);bool pInRight !pInLeft;bool qInLeft IsInTree(root-left,q);bool qInRight !qInLeft;//如果一个在左一个在右则当前结点就是公共祖先if((pInLeft qInRight) || (qInLeft pInRight)){return root;}//如果两个都在左就去当前结点的左子树找else if(pInLeft qInLeft){return lowestCommonAncestor(root-left,p,q);}//如果两个都在右就去当前结点的右子树找else{return lowestCommonAncestor(root-right,p,q);}}
};上面的写法的时间复杂度为O(N^2)因为每一次查找结点是否在左子树或右子树为O(N)因为二叉树可能为不平衡二叉树这样极端情况下就需要查N次。即向下面的情况下是效率最低的情况。 如果这个树是二叉搜索树的话上面的方法就可以改变判断做到时间复杂度为O(N)因为只需要比较p、q是否比根节点大或小如果比根小递归左树查找如果比根大递归右树查找。但是题目中的树不是二叉搜索树我们此时想要优化为O(N)的话可以使用DFS深度优先遍历然后将p和q的路径都存放到两个栈中转换为p和q的路径相交问题。
lass Solution {
public:bool GetPath(TreeNode* root, TreeNode* x, stackTreeNode* path){if(root nullptr){return false;}path.push(root);if(root x){return true;}if(GetPath(root-left,x,path)){return true;}if(GetPath(root-right,x,path)){return true;}path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* pPath,qPath;//找到p和q的路径GetPath(root,p,pPath);GetPath(root,q,qPath);while(pPath.size()!qPath.size()){if(pPath.size()qPath.size()){pPath.pop();}else{qPath.pop();}}while(pPath.top()!qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};
6.5 二叉搜索树与双向链表
题目链接 例如下面的一棵二叉树我们想要将这棵二叉树变为双向链表我们需要将每一个结点的left指向它的上一个结点上一个结点的right指向这一个结点如果我们使用递归并且将递归函数的参数为指针的话我们知道在当前的递归函数中没法改变prev结点的right和left这时我们可以将参数prev设为指针引用那么我们在当前递归函数中也可以改变当前结点的上一个结点prev的left和right的值。
class Solution {
public:void InOrderConvert(TreeNode* cur,TreeNode* prev){if(cur nullptr){return;}//二叉搜索树中序遍历为升序InOrderConvert(cur-left, prev);//当前结点的left指向上一个结点cur-left prev;//如果上一个结点不为空即cur不为链表头结点那么就将上一个结点的right指向当前结点cur。if(prev){prev-right cur;}//此时将prev变为当前结点然后再链接cur-right。prevcur;InOrderConvert(cur-right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prevnullptr;InOrderConvert(pRootOfTree, prev);TreeNode* head pRootOfTree;while(head!nullptrhead-left!nullptr){head head-left;}return head;}
};
6.6 从前序与中序遍历序列构造二叉树
题目链接 使用前序序列来确定根结点使用中序序列来分割出根结点的左右子树区间。
class Solution {
public:TreeNode* _buildTree(vectorint preorder, vectorint inorder,int prei,int inbegin,int inend){if(inbegininend){return nullptr;}TreeNode* root new TreeNode(preorder[prei]);int rooti inbegin;while(rootiinend){if(inorder[rooti]preorder[prei]){break;}else{rooti;}}prei;root-left_buildTree(preorder,inorder,prei,inbegin,rooti-1);root-right_buildTree(preorder,inorder,prei,rooti1,inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;return _buildTree(preorder,inorder,i,0,inorder.size()-1);}
};6.7 从中序与后序遍历序列构造二叉树\
题目链接 根据前序序列和中序序列生成二叉树时我们是从左子树开始链接而因为后序序列中根结点在最后一个并且倒着访问后序序列时先访问的都是右结点所以我们采用从右子树开始链接。
class Solution {
public:TreeNode* _buildTree(vectorint inorder, vectorint postorder,int posti,int inbegin,int inend){if(inbegininend){return nullptr;}TreeNode* root new TreeNode(postorder[posti]);int rooti inbegin;while(rootiinend){if(inorder[rooti]postorder[posti]){break;}else{rooti;}}posti--;root-right _buildTree(inorder,postorder,posti,rooti1,inend);root-left _buildTree(inorder,postorder,posti,inbegin,rooti-1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int i postorder.size()-1;return _buildTree(inorder,postorder,i,0,i);}
};6.8 二叉树的前序遍历–非递归
题目链接 我们使用非递归前序遍历二叉树时可以先访问这棵树的左路结点然后左路结点遇到空后开始访问这个左路结点的右子树访问右子树时就转换为子问题即访问右子树也是先从右子树的左路结点开始访问当右子树的左路结点遇到空时再重复上面的步骤。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint vv;stackTreeNode* s;TreeNode* cur root;//while(cur!nullptr || !s.empty()){//开始访问一棵树//1.先访问左路结点//2.左路结点遇到空后就开始访问左路结点的右子树while(cur!nullptr){vv.push_back(cur-val);s.push(cur);curcur-left;}//左路结点为空了开始访问右子树//访问右子树也是像上面一样先从右子树的左路结点开始访问。cur s.top()-right;s.pop();}return vv;}
};6.9 二叉树的中序遍历–非递归
题目链接 二叉树的中序遍历非递归实现和上面的前序遍历类似只不过将元素插入到容器的时机不同。而非递归遍历二叉树的方式是一样的都是先遍历这棵树的左路结点然后左路结点为空后再遍历这个左路结点的右子树。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint vv;stackTreeNode* s;TreeNode* cur root;//先访问一棵树的左路结点当左路结点为空时再访问该结点的右子树//而访问右子树时也是先访问右子树的左路结点。while(cur!nullptr || !s.empty()){while(cur!nullptr){s.push(cur);curcur-left;}//因为是中序遍历所以当左路结点没有左孩子时此时才能访问这个结点。vv.push_back(s.top()-val);cur s.top()-right;s.pop();}return vv;}
};6.10 二叉树的后序遍历
题目链接 二叉树的后序遍历的非递归实现和前序遍历、中序遍历不同。因为有左右子树的结点会有两次都在栈顶的位置我们按照上面前序遍历的写法无法区分哪一次将该结点进行出栈所以我们在代码中加了一个prev指针prev指针记录上一个栈顶结点如果当前栈顶结点的右孩子为prev结点说明当前栈顶结点的左右子树都已经遍历完毕此时就需要将栈顶元素进行出栈了。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint vv;stackTreeNode* s;TreeNode* cur root;TreeNode* prev nullptr;while(cur!nullptr || !s.empty()){while(cur!nullptr){s.push(cur);curcur-left;}TreeNode* top s.top();if((top-rightnullptr) || (top-right prev)){vv.push_back(top-val);s.pop();prev top;}else{curtop-right;}}return vv;}
};
