-
关于树的知识点
2019-03-03 15:47:25一颗AVL树是其每个节点的左子树和右子树的高度最多相差1的二叉查找树 懒惰删除:当一个元素要被删除时,它仍留在树中,而只时被标记为删除 红黑树遍历时间复杂度O(log n) ...- 一颗AVL树是其每个节点的左子树和右子树的高度最多相差1的二叉查找树
- 懒惰删除:当一个元素要被删除时,它仍留在树中,而只时被标记为删除
- 红黑树遍历时间复杂度O(log n)
-
算法:关于树的知识点总结
2020-10-16 21:05:04100. 相同的树(简单) 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 分析: 方法一:深度优先搜索 如果两个二叉树都为空,则两个...1、定义:
(1)树、二叉树
(2)二叉查找树
(3)DFS(Deep First Search)深度优先遍历和 BFS(Breath First Search)宽度(广度)优先搜索
二叉树的遍历:
BFS:A B C D E F G H I
DFS: A B C E F D G H I二叉树的深度优先遍历种类:前序、中序、后序遍历
图的遍历:
从A出发BFS:A B C D E F (其中一种)
DFS:A B D F E C (其中一种)
(4)BFS和DFS的实现
BFS: 队列(先进先出)
步骤:1、首先A入队列, 2、A出队列时,A的邻接结点B,C相应进入队列 3、B出队列时,B的邻接结点A,C,D中未进过队列的D进入队列 4、C出队列时,C的邻接结点A,B,D,E中未进过队列的E进入队列 5、D出队列时,D的邻接结点B,C,E,F中未进过队列的F进入队列 6、E出队列,没有结点可再进队列 7、F出队列
实例1:
用BFS(Breath First Search)的方法求二叉树的最大深度:class Solution { public: int maxDepth(TreeNode* root) { if (root == nullptr) return 0; queue<TreeNode*> Q; Q.push(root); int ans = 0; while (!Q.empty()) { int sz = Q.size(); while (sz > 0) { TreeNode* node = Q.front();Q.pop(); if (node->left) Q.push(node->left); if (node->right) Q.push(node->right); sz -= 1; } ans += 1; } return ans; } };
实例2:
接下来我们再来介绍二叉树的另一种遍历方式:层序遍历。
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(root); vector<vector<int>> result; while (!que.empty()) { int size = que.size(); vector<int> vec; // 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的 for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } result.push_back(vec); } return result; } };
DFS:栈(先进后出)
步骤:1、首先A入栈, 2、A出栈时,A的邻接结点B,C相应入栈 (这里假设C在下,B在上) 3、B出栈时,B的邻接结点A,C,D中未进过栈的D入栈 4、D出栈时,D的邻接结点B,C,E,F中未进过栈的E、F入栈(假设E在下,F在上) 5、F出栈时,F没有邻接结点可入栈 6、E出栈,E的邻接结点C,D已入过栈 7、C出栈
参考:
-
关于B树的几个知识点
2020-11-01 14:05:141.B树的所有外部结点都处于最底层,且深度完全一致,所以B树肯定是满树 2.考研考的比较多的是B树的深度h,B树的阶数m,B树的关键码个数N 1)B树的高度的范围: 2)B树各个结点所含关键码的3个要求: i.根节点至少...1.B树的所有外部结点都处于最底层,且深度完全一致,所以B树肯定是满树
2.考研考的比较多的是B树的深度h,B树的阶数m,B树的关键码个数N
1)B树的高度的范围:
2)B树各个结点所含关键码的3个要求:
i.根节点至少含有1个关键码
ii.每个结点至多含m-1个关键码
iii.除了根节点,其它分支结点至少包含-1个结点3.B树和其它普通树不同的地方在于,计算树的高度时需要把外部节点考虑进去(即使外部节点是并不包含关键码的结点)
以上3个点可以通过这道题来考察以下:
解析:最多:4×(1+5+5×5)=124;1+2×2+2×3×2=17
关于最少存放的情况:
黑色圆圈是关键码,红色框框是外部节点,即非关键码 -
python中树与树的表示知识点总结
2020-09-18 15:51:54在本篇文章里小编给大家分享的是关于python中树与树的表示的相关知识点,需要的读者们学习下吧。 -
一些关于树的知识杂项
2017-03-07 11:22:59首先从完全二叉树的定义来入手,对于一个完全树,要么他是一个叶结点,要么他一定有左孩子,我们可以遍历每一个点,如果它左孩子的深度小于右孩子,或者左孩子深度等于右孩子但是在遍历他的左孩子时发现左右不等,均...1、如何判断这个树是不是完全二叉树?
首先从完全二叉树的定义来入手,对于一个完全树,要么他是一个叶结点,要么他一定有左孩子,我们可以遍历每一个点,如果它左孩子的深度小于右孩子,或者左孩子深度等于右孩子但是在遍历他的左孩子时发现左右不等,均可以判断出它不是一个完全二叉树
-
juyter显示决策树图形_决策树学习指南:关于决策树的知识点都帮你整理好了(含代码)...
2020-12-23 00:40:37几乎整合了现在所有决策树知识,希望对大家的学习有所帮助。介绍你一生中没有哪一天不需要做出决定。从早餐吃什么到你感兴趣的职业,你的生活都被决策所包围。假设你想出去打球,出门前你会考虑哪些因素?今天会下雨... -
树的基本知识点
2015-11-24 20:58:23本文整理了关于树的一些基本知识点: 1. 树是一种非线性数据结构,编译器中可用树来表示源程序的语法结构。在任意一颗非空树中,有且仅有一个特定的称为根(root)的节点。 2. 节点拥有的子树数称为节点的度... -
关于二叉树与树(森林)的知识点详解
2016-07-08 09:26:571.二叉树的遍历及优缺点: 前序遍历用来实现目录结构的显示。 中序遍历用来做表达式,在编译底层实现的时候,可以实现加减乘数 后序遍历可以用来实现计算目录内的文件,占用的数据大小。 二叉树最复杂的还是删除... -
MySQL优化中B树索引知识点总结
2020-09-09 05:12:56在本文里我们给大家整理了关于MySQL优化中B树索引的相关知识点内容,需要的朋友们可以学习下。 -
决策树知识点总结
2018-09-20 21:25:24本章介绍关于决策树的知识,理论部分来自周老师的西瓜书,代码部分来自《机器学习实战》,有位作者对代码实现已经做了很好的介绍,有兴趣的朋友可以看一下,感谢作者。... -
关于hashmap的知识点和面试考点
2020-08-02 14:37:15HashMap是java开发中经常会被问到的知识点,下面就我搜集到的一些问题进行讲解。 最常见的问题一般是以下方面的问题: 1,它的底层数据结构是什么? 2,在java7和java8里的区别是什么? 3,线程是否安全?为什么... -
关于堆的一些知识点
2017-08-24 19:22:00关于堆的一些知识点 1.概述 堆(也叫优先队列),是一棵完全二叉树,它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆)。它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先... -
【知识总结】浅谈关于树的重心及其求法
2019-08-07 15:19:58树的重心:找到一个点,其所有的子树中最大的子树节点数最少. 二.树的重心性质 树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个距离和,他们的距离和一样。 把两棵树通过一条边相连,新的树的... -
SLAM 基本知识树(SLAM学习的所有知识点概述)
2019-12-21 09:33:102、SLAM知识树 注释: a.泰勒公式是将一个在x=x0处具有n阶导数的函数f(x)利用关于(x-x0)的n次多项式来逼近函数的方法。 若函数f(x)在包含x0的某个闭区间[a,b]上具有n阶导数,且在开区间(a,b)上具有(n+1)... -
知识点汇总:如何修改Java的抽象语法树?
2020-05-09 15:33:05在网上关于如何修改Java的抽象语法树的相关API文档并不多,于是本篇记录一下相关的知识点,以便随后查阅。 JCTree的介绍 JCTree是语法树元素的基类,包含一个重要的字段pos,该字段用于指明当前语法树节点(JCTree)... -
关于我们DOM的知识点
2016-11-11 21:10:00DOM的概念及子节点类型 前言 DOM的作用是将网页转为一个javascript对象,从而可以使用...DOM的最小组成单位叫做节点(node),文档的树形结构(DOM树)由12种类型的节点组成。 一:DOM ==> 全称: do... -
Java 关于HashMap的一点知识
2020-07-21 18:07:18HashMap 底层是通过数组进行存储的,数组存储的是Entry 键值对! 底层容量为16,默认的加载...当一个链表结构的size()大于 8 的时候,会变成红黑树的树形结构,如果进行调整后,链表的结构小于6的时候,会自动调整. -
关于二叉树应用的知识点总结
2020-08-08 18:32:481,ASL(平均查查找长度):按层来算,每一层...5,树的带权路径长度(WPL)= 所有的叶结点带权路径长度 之和 6,叶结点的带权路径 长度= 结点的权值 * 它的路径长度 **7,**哈夫曼树的三点特性: 1,每个初始结点最后都 -
关于JQuery的一些知识点
2016-11-05 08:53:001.jQuery的入口函数 1.1 语法jQuery(document).read(function(){ }); $(function(){ });// ** window.onlaod = function(){} $ === jQuery // $是jQuery...document ready: 是html文档准备就绪,也就是dom树创建... -
知识点:二叉(重量)平衡树——替罪羊树
2019-10-01 21:40:58目录 知识点概要 知识点详解 平衡因子 子树的重构 基础操作 复杂度分析 关于替罪羊树 代码(luogu3369 && BZOJ3224) 知识点概要 在各种二... -
关于C语言的易错、知识点
2019-08-03 16:30:14可以是一颗空树,也可以是一颗具有如下特性的非空二叉树: 1. 若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值; 2. 若右子树非空,则右子树上所有节点关键字值均不小于根节点的关键字值; 3. 左... -
关于知识点整理的一点想法
2006-07-25 14:25:00之前写的《程序开发的一点感悟》一文中,我曾提到软件开发中的知识点就像树叶一样多,经常碰到这种情况,就是很多知识点看了以后不久又忘了,等到再次用到的时候还得回过头来继续查资料,非常影响开发效率。... -
关于树的简单整理
2017-10-27 11:16:00先写一下关于树的许多定义。 树,父节点、子节点、子树、祖先、兄弟、根节点、叶节点、直径、路径、重心、直径、最近公共祖先、生成树、dfs序,树形dp等 1、最近公共祖先 一般用倍增求LCA(Least Common ... -
知识点整理:二叉(重量)平衡树——替罪羊树
2018-07-24 08:18:41在各种二叉平衡树中,大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质,并且尽量保证每次的查找的复杂度为logloglog的。然而说实话,各种情况的旋转很容易写挂,考场上一旦写挂掉就会心态爆炸,所以我们或许.... -
【字典树】知识点讲解 模板+例题x1
2018-05-14 21:42:44s[i][j]=k,表示编号为i的节点的第j个孩子是编号为k的节点我的理解就是觉得,如果字符串的数量一大起来,题意是关于查询“相同前缀”的,那么就用字典树了!!!模板:更多模板请见链接。例题:糟糕的Bug大致思路:... -
知识点 - 动态树(LCT)
2019-08-03 20:37:10知识点 - 动态树(LCT) 解决问题类型: 求LCA 求最小生成树 维护链上信息(最大最小,链上和等) 维护联通性 维护子树信息(需要配合AAA树) 优化单纯性算法,在O(mnlog(n))O(mnlog(n))的复杂度下求最大流(这两个是... -
关于图的应用的4个算法的知识点总结(一)
2020-08-16 10:53:423,最小生成树的性质:不是唯一的,但是当图中的所有的边的权值不相等时,最小生成树时唯一的。 最小生成树的权值之和总是唯一的 4 Prim算法:初始时从图中任取一个顶点,加入树T中,再选择一个与当前T中顶点集合... -
关于树表结构的查找算法
2019-04-03 00:43:00设计的知识点为: 二叉查找树 平衡二叉树 B树 B+树 红黑树 1、二叉查找树: 二叉查找树就是左结点小于根节点,右结点大于根节点的一种排序树,也叫二叉搜索树。也叫BST,英文Binary Sort Tre...
-
Markdown 标记语言
-
常用JVM启动参数
-
Unity ILRuntime框架设计
-
Spring学习笔记之Spring HelloWorld
-
select和epoll的过程分析与比较
-
异常色散光纤激光器中的线性耗散孤子
-
C++string容器应用举例
-
python数据分析之Pandas数据结构和操作
-
ASHRAE_Extended_Environmental_Envelope_Final_Aug_1_2008.pdf
-
解决问题:这是解决问题的仓库-源码
-
leetcode算法第四题
-
基于采用级联调制器的光电振荡器的自振荡光学频率梳状发生器
-
NFS 实现高可用(DRBD + heartbeat)
-
2019年下半年 网络工程师 上午试卷 综合知识 软考真题【含答案和答案解析】
-
电影记录-源码
-
一天学完MySQL数据库
-
2021 PHP租车系统 毕业设计 毕设源码 源代码使用教程
-
自适应极限学习机
-
2015年上半年 信息系统管理工程师 上午试卷 综合知识 软考真题【含答案和答案解析】
-
射影级双缝光子晶体光机腔设计