如何查看一家网站是否有备案,wordpress在线朗读,网络设计工作,外贸网站建设行业发展一.树的概念
树的图#xff1a;
1.结点的度#xff1a;一个结点含有子树的个数称为该结点的度#xff1b; 如上图#xff1a;A的度为6
2.树的度#xff1a;一棵树中#xff0c;所有结点度的最大值称为树的度#xff1b; 如上图#xff1a;树的度为6
3.叶子结点或终…一.树的概念
树的图
1.结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6
2.树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6
3.叶子结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I...等节点为叶结点
4.双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点
5.孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点
6.根结点一棵树中没有双亲结点的结点如上图A
7.结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推
8.树的高度或深度树中结点的最大层次 如上图树的高度为4。
二.二叉树
一棵二叉树是结点的一个有限集合该集合
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 3. 二叉树不存在度大于2的结点
4. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
二叉树的几种情况
满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是 则它就是满二叉树。 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完比特就业课全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。完全二叉树可以简单的说为从上到下从左到右依次放就是完全二叉树
二叉树的性质
1. 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有 (i0)个结点
2. 若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 (k0)
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21推导的公式 4. 具有n个结点的完全二叉树的深度k为 上取整
5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有
若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点
若2i1n左孩子序号2i1否则无左孩子
若2i2n右孩子序号2i2否则无右孩子
6.在完全二叉树中如果节点总个数为奇数则没有度为1的节点如果节点总个数为偶数只有一个度为1的节点。
三.练习题
1.选B度为0的节点个数比度为2的节点个数多一个。
2.选A第三张图是当节点个数为奇数的时候计算的和偶数一样的计算方式只不过没有单独的一个度为0的节点。 3.选B这道题就是上图奇数个节点的情况 4.选B用性质算 四.二叉树的存储和遍历
1.顺序存储在堆的时候将
2.类似于链表的链式存储
3.二叉树的遍历
1前序遍历根 左 右
这里先从A这个根开始遍历之后再到A的左树马之后就是将B看为一个根,也要遵循根左右的规则那么此时遍历B的左树DD又成为了根此时遍历D的左树D的左树为空那么回到D这个根遍历D的右树D的右树为空此时D这个根遍历完返回到B这个根遍历B的右树B的右树也为空此时返回到B树再返回到根A此时再遍历A的右树C同理C此时当作根遍历C的左树EE此时为根遍历E的左树左树为空返回到根E遍历E的右树E的右树为空返回根EE遍历完返回到根C遍历C的右树C的右树为FF此时也当作根来遍历F的左树F的左树为空返回到根F遍历F的右树F的右树为空返回根FF遍历完F返回到根CC遍历完返回到根AA的右树也遍历完了则前序遍历完成。顺序为ABDCEF 2中序遍历左 根 右
中序遍历的法则是 左 根 右 从根A开始先进入二叉树此时是中序遍历要左边走完才打印根A所以此时没有打印根A进入A的左树BB也是根继续走B的左树DD也是根继续走D的左树D的左树为空则返回到D此时左走完了走到了根则打印D再走D的右树右树为空此时返回根DD遍历完返回BB的左树走完此时打印B走入B的右树B的右树为空B遍历完返回到根A打印A因为此时A的左树遍历完了进入A的右树C此时C也为根先走C的左树EE为根先走E的左树E的左树为空返回到E打印E再走E的右树E遍历完返回到根C打印C进入C的右树FF的左树为空返回到F打印F再走到F的右树右树为空遍历完F返回到CC遍历完返回到A遍历完二叉树。顺序DBAECF
3.后序遍历左 右 根
后序遍历规则 左 右 根此时先进入二叉树根A开始进入A的左树BB为根进入B的左树D此时D的左树为空回到D此时没有任何节点被打印当继续遍历D的右树为空返回到D的时候打印D此时返回到BB的右树为空遍历完B此时打印B返回到A遍历A的右树C为根进入C的左树EE的左树为空进入右树也为空遍历完E此时打印E回到C进入C的右树FF的情况和E相同不赘述打印了F回到了CC遍历完左右树打印C回到AA此时遍历完左右树打印A。顺序DBEFCA 4层序遍历从上到下从左到右依次遍历 4.代码
1树节点的结构
2.这里先用很low的方式创建一个树 3树的前序遍历自己画图的大致流程后面的流程都是一样的 4树的中序遍历
5树的后序遍历
6非递归的层序遍历非递归的层序遍历需要有一个临时变量cur记录当前节点并且把此时这个节点的不为空的左右子树传入队列中进行入队操作然后再通过临时变量来进行出队就可以实行层序遍历画图解释 7非递归的前序遍历通过栈来进行压栈数据先遍历每个节点的左子树当最后一个节点的左子树为空的时候再通过top通过栈内元素pop接收这个在栈顶的元素让cur来遍历这个节点的右子树依次循环往复。 8中序遍历的非递归实现中序遍历和前序遍历的代码都是一样的就是打印的位置不同中序遍历是左根右那么在遍历右子树之前打印这个节点就可以啦
9后序遍历的非递归实现(刚开始的思路和上面两种遍历的方式是一样的但是在pop栈里面的元素的时候就不一样了这里需要把这个节点的右子树走完才能进行打印所以就需要对这个节点的右子树进行判断。再进行判断的时候不是直接把这个节点直接pop出来而是需要用peek去看一下这个节点的右节点是否为null不为null就需要继续遍历这个右节点。这里需要注意的是当遍历到E的时候这里E的左子树是null的所以cur就是null这里的top直接peek 栈中的节点也就是E节点如果E节点的右子树为null的话那么直接就打印E节点并且pop但是E节点的右子树有一个H那么cur就会拿到这个节点然后再进行判断H的左右子树都为null那么就直接打印H并且弹出H此时栈中的栈顶元素是E那么此时top拿到E再进行判断E的右子树是否为null不为空那么cur又拿到了H这个节点所以这里就循环了这里也就是和上面两个循环不同的地方这里就需要哪一个prev来记录下来这个右子树的节点当回到E这个结点的时候通过prev上次拿到的是H的节点如果等于top就是E节点的右子树的话那么E的右子树走完回来了直接打印E并且pop出E的这个节点这里就是不同的地方。) 五.二叉树练习题
1.选A这就是她的层序遍历并且她是完全二叉树。 2.选A 这道题画图的话就是下一张图中的树。先序遍历的第一个为根中序遍历中间E就为根就可以进行画图了。 3.选D
4.选A
5.无法根据前序和后序来画出树的图因为前后序确定的是树的根。
六.二叉树的节点个数计算
1.一个树的节点个数等于根节点加上这个根的左树和右树的节点个数总结就是这个根的左树右树1就是这个树的节点个数也就是说每个节点都可以看成一个根然后求每个根的节点个数再通过递归传回数值的大小就可以计算出树的节点个数。 2.通过前序遍历来计算节点个数把打印数据变成size就行了原理都是一样的 3.求叶子节点个数1.子问题思路整棵树的叶子节点等于左子树的叶子节点右子树的叶子节点个树 2.遍历思路以某种方式遍历树为叶子就叶子是没有左子树和右子树的节点为叶子
第一种方法实现
第二种方法实现
3.第K层节点的个数:计算的方法就是通过递归的思想算第k-1层左树的节点和右树的节点当为第一层的时候直接返回1然后递推结束开始回归 4.算树的高度树的高度是通过递归来实现的需要注意的是这里不能直接return递归的语句也就是图三框住的return语句如果直接这样使用会导致递归的重复调用使用的时间就会更长会超出时间限制因为当你递归出HeightTree(root.left) 为5的时候并且HeightTree(root.right)为4的时候HeightTree(root.left)HeightTree(root.right)你要HeightTree(root.left)1此时你还需要你计算一次HeightTree(root.left)的大小重复计算花费的时间更多。时间复杂度为ON 5.找指定数据找到数据的时候一定要将数据保留下来而不是继续循环看图二错误写法就是没有在递归的时候把正确的数据return回来而只return回来null图三分别为正确的流程黑红线和错误流程只有红线时间复杂度是ON因为需要遍历每个节点 七.二叉树OJ题
1.两个树是否相同思路判断两个数是否相同需要从两个方面来判断首先就是判断两个数的结构是否相同第一种情况就是这两个树的一个根节点一个为空一个不为空那么肯定是不相同的第二种情况就是两个根节点都是空的话那么这个根节点就是相同的然后还需要继续判断后面的节点是否相同。第三种情况就是根节点都存在的情况下根的值不同那么也是直接返回false。递归思路就在画图时间复杂度为Op和q之间节点个数的最小值 2.这个树是否为另一棵树的子树思路如果这两棵树相同那么两棵树构成子树关系然后通过递归root的左子树和子树进行对比再通过root的右子树和子树进行对比如果上述三个条件都不满足就是不为子树关系或者root为空的时候也就是root这棵树遍历完了都不满足则这两棵树不为子树关系递归详细画图时间复杂度root的节点为m subroot的节点个数为n 那么空间复杂度为O(m*n) 因为每次在root节点上都要遍历一次subroot的节点 3.翻转二叉树思路就是通过前序遍历交换每个节点的左右子树比较简单不画图 4.判断一个二叉树是否为平衡二叉树平衡二叉树表示该树的所有节点的左右子树深度差小于等于1 方法一时间复杂度为ON^2时间为ON^2是因为在计算每个节点的深度的时候就遍历了全部节点当判断树是否平衡的时候也要遍历这个树的每个节点那么就重复了所以才是ON^2这个方法是通过计算每个节点的左右子树的节点个数然后做差算出差值的绝对值小于等于1就为平衡二叉树。HeighTree是上面计算指定根的深度。画图解释。需要注意的是图三这幅图是不为平衡二叉树的当9作为根节点的时候左子树的深度是2右子树为0左右子树的差值大于1了就不是平衡二叉树。
方法二时间复杂度为ON不重复计算。思路就是当左子树深度减去右子树的深度的绝对值大于1那么就直接返回-1如果满足平衡二叉树的条件的话也就是说左右子树的深度差值小于等于1那么就直接返回左子树和右子树之间最大的深度1 5.对称二叉树思路对称二叉树需要的是左子树和右子树对称那么也和树是否相同的思路一样先从结构考虑如果一个为空一个不为空肯定不对称两个都为空就对称最后再从值的方面考虑如果两个都不为空但是值不一样就是不对称的。最后还需要判断每一个树的左树的左节点是否等于右树的右节点画图解释 6.二叉树的创建和遍历这道题是在牛客上面写的需要注意的点有几个首先就是我们需要注意的是一开始牛客上的界面是图三这种我们这里是输入的字符串需要用到字符串的输入并且我们会使用到空格就需要使用nextLine而不是next来输入字符串因为next输入的字符串不能有空格。之后就是这道题需要通过前序遍历创建一个二叉树并且通过中序遍历输出那么中序遍历和树节点的创建就不说了这道题的思路还是比较简单这里还需要注意的是就是当我们在判断字符串中的第i个字符不是字符的时候里面进行的语句就是创建一个节点并且设置左右节点这里需要注意的是我们创建了一个结点之后就需要进行i因为当此时如果在左子树递归或者右子树递归语句的后面才施行i那么就会导致思路错误了。整体来说思路就是判断第i个字符是不是空格不是空格进行创建一个节点并且让i再进行左子树和右子树的递归如果是空格就直接i。图四是画图解释 这里i是静态变量带来的危害如果在main方法中创建两个TreeNode对象每次i就无法从0开始因为第一次遍历完之后i就在第一个字符串的末尾了。
7.非递归的层序遍历顺序表来写总体思路和非递归层序遍历差不多唯一的差别就是需要用二维数组来实现这个二叉树需要注意的是每层的创建应该在计算size大小的时候进行重新开辟而不是直接在外面创建一个数组然后一直add。图二就是错误示范 全是同一个数据的原因是当我们实现完这个层序遍历之后list的地址都是一样的那么list1 进行add三次都是同一个list那么就是这三个元素的add都是同一个地址那么就是相同的数据。
8.找到两个节点的最近公共祖先下面四种就是公共祖先的情况 方法一通过直接递归来写第一种情况如果p和q之间有一个为root那么直接返回root就可以了第二种情况p和q分别在根的左右子树那么就需要通过递归来进行找到p和q的然后再通过语句来判断是哪种情况如果都在p和q就是刚刚说的在左右子树那么就返回根节点root如果都是在左子树或者右子树就返回最先找到的那个节点就可以了。图解第二张
方法二用栈来写这种情况用堆好解释简单的说类比链表的分支思路将p和q的路径记录下来再通过像链表的相交的想法来进行两个栈的对比如果第一个元素相同那么后面的元素都是相同的直接返回第一个出栈的节点。如果第一个栈顶元素不同就一起出栈栈顶元素不断比较比较到结束完都没有那么就直接返回null说明没有公共祖宗节点。其中getPath的方法不好写因为我们需要递归的从根的左右子树来找到这个节点还需要注意的是当这个节点的左右子树都找不到p或者q的时候我们就需要把这个节点从栈里面弹出这是需要注意的地方。还有就是需要注意每次左子树遍历和右子树遍历都需要写一个判断条件不能一直往下走。 9.前序遍历和中序遍历创建树大致的思路就是先通过前序遍历和中序遍历来确定根节点确定根节点之后就可以通过中序遍历中的根节点来确定左右子树根的左边就是左子树右边的数据就是右子树然后再通过定义一个inBegin和inEnd来进行每个节点的遍历。因为inBegin和inEnd是每个节点需找自己左右子树的范围所以这样就可以确定每个节点的左右子树。这里从E开始进行遍历在中序遍历中我们可以知道E的左边数据为左子树右边数据为右子树那么此时我们需要先找左子树的数据因为先序遍历是根左右所以此时开始找E的左子树那么此时E左子树的inBegin和inEnd的范围就是0到在中序遍遍历E的下标的左边一个下标此时就是inEnd的范围所以此时我们就需要写一个语句来找到每个节点的位置这样才能在找左子树的时候确定他的inEnd的大小。此时找左子树的过程是一个递归的过程当inBegin大于inEnd的时候就是没有节点了此时就就代表递归结束了。还需要注意的是在最开始我们需要定义一个成员变量才能让先序遍历中的下标不被函数栈帧销毁因为我们再找节点的时候是通过先序遍历的顺序来找的每个节点。右子树也是如此。这里还需要注意的是我们传入根节点的inEnd的时候必须是中序遍历数组长度-1.不能直接传入中序遍历数组的大小因为在找数据的时候我们是通过inBegin和inEnd来循环找数据的如果你直接传入中序遍历数组的大小的话那么我们循环语句就是直接写的是 i inEnd 当inBegin和inEnd相等的时候就找不到这个数据了但是这个数据就是inBegin和inEnd相等的时候的位置所以就会导致我们找不到这个节点的位置也就导致无法找到这个节点子树的inEnd的大小了因为inEnd是等于这个节点下标减一。右子树则是将inBegin 等于 这个节点下表1inEnd不变 10.后序遍历和中序遍历这里和前序遍历的差不太多唯一的差别就是先递归根的右子树再左子树并且此时遍历这个后续遍历的数组的时候是通过最后一个位置的元素来进行 -- 来进行的因为根节点在最后一个位置通过 -- 来找到数据而且后序遍历是通过左 右 根来进行的那么反起来找数据那么就是根 右 左所以和前序遍历是反的其他的思路都是一样滴 11.二叉树创建字符串这里是通过StringBuilder来进行字符串的添加通过实例1我们可以知道根节点是没有括号的那么直接就可以appendroot.val然后再进行左子树的判断第一种情况就是左子树不为空通过实例1我们知道先他是先进行增加一个左括号然后通过左子树的递归来进行增加节点递归完之后在增加右括号如果左子树为空那么还需要判断右子树是否为空如果右子树也为空此时直接返回如果右子树不为空的话我们看示例二示例二中2的左子树为空右子树不为空那么这里直接增加了一个括号的那么此时也是直接增加一个括号此时左子树的情况说完来说右子树的情况如果右子树不为空的话也是和左子树一样先一个左括号然后再递归递归完之后在增加上右括号。如果右子树为空的话就直接return就好了
