STL的六大组件 STL的重要性 在笔试中 JZ78 把二叉树打印成多行 重建二叉树 用两个栈实现队列 在面试中 在工作中 网上有句话说：“不懂STL，不要说你会C++”。...STL是C++中的优秀作品，有了它的陪伴，许多底层的数据结构 以及算法都不需要自己重新造轮子，站在前人的肩膀上，健步如飞的快速开发。...容易使你迷失的是STL中几乎每一个部分都充斥着Templat、选代器和重载的运算符，如果你对它们一无所知，在STL的海洋里就会寸步难行。...如果你仅是停留在“使用”这个层次上，那么当出现问题而问题又并非位 于表面时，你可能就会“找不着北”，甚至开始埋怨STL一点也不好用，其实问题往往出在自己这里。...C++11出 来已经相隔了13年，STL才进一步更新。 STL现在都没有支持线程安全。并发环境下需要我们自己加锁。且锁的粒度是比较大的。 STL极度的追求效率，导致内部比较复杂。
在那些需要数组无限扩展的情况下，可以使用可扩展的数组，例如C ++标准模板库（STL）中的vector类。Matlab中的数组规则具有相似的可扩展性，可扩展数组也是整个Python语言的基础。...二叉树 二叉树类似于链表，除了每个节点有两个指向后续节点的指针而不是一个。左侧子项的值总是小于父节点的值，而父节点的值又小于右侧子元素的值。因此，二叉树中的数据会自动排序。...这个顺序应用在层次结构中，但不能违背的是：父项总是大于其子项，但是更高级别的节点值不一定比它子节点同一层次的节点值大。 [9kfksk8qm9.png] 插入和检索都是通过提升进行的。...当从堆中取下一个元素时，两个子元素中越大的子元素被提升到缺失的位置，那么这两个子元素中的更大的子元素就会被提升等等，直到所有的元素都排到了正确的位置上。...自定义数据结构 当你处理更多的问题时，你肯定会遇到那些标准框架不能很好的解决你的需求。你将需要设计自己的数据结构。 考虑一个多类分类器，它将一个二元分类器推广到具有两个以上类的分类问题。
树中的常见术语 结点：包含数据项以及指向其他结点的分支，例如上图中圆 A 中，既包含数据项 A 又指向 B 和 C 两个分支 特别的，因为 A 没有前驱，且有且只有一个，所以称其为根结点 子树：由根结点以及根结点的所有后代导出的子图称为树的子树...可能大家也看到了，上面我举的例子，分支全部都在两个以内，这就是我们今天所重点介绍的一种树—— “二叉树” 二叉树 在计算机科学中，二叉树（英语：Binary tree）是每个结点最多只有两个分支（即不存在分支度大于...二叉树的分支具有左右次序，不能随意颠倒。...几种特殊的二叉树 (一) 满二叉树 通常情况下，我们见到的树都是有高有低的，层次不齐的，如果一颗二叉树中，任意一层的结点个数都达到了最大值，这样的树称为满二叉树，一颗高度为 k 的二叉树具有 2k...二叉树的链式存储结构（重点） 顺序结构显然不是很适合使用，所以在实际中，我们会选择链式存储结构，链式存储结构中，除了需要存储本身的元素，还需要设置指针，用来反映结点间的逻辑关系，二叉树中，每个结点最多有两个孩子
当存储在表中时，直接寻址使用值和键之间的一对一映射。但是，当存在大量键值对时，此方法存在问题。该表将具有很多记录，并且非常庞大，考虑到典型计算机上的可用内存，该表可能不切实际甚至无法存储。...Representation of a Hash Function · 1→1→1 · 5→5→5 · 23→23→3 · 63→63→3 从上面给出的最后两个示例中，我们可以看到，当哈希函数为多个键生成相同的索引时...· p：指向父节点的指针。 二叉搜索树具有独特的属性，可将其与其他树区分开。此属性称为binary-search-tree属性。 令x为二叉搜索树中的一个节点。...7.堆 堆是二叉树的一种特殊情况，其中将父节点与其子节点的值进行比较，并对其进行相应排列。 让我们看看如何表示堆。堆可以使用树和数组表示。图7和8显示了我们如何使用二叉树和数组来表示二叉堆。 ?...· 最小堆-父项的密钥小于或等于子项的密钥。这称为min-heap属性。根将包含堆的最小值。 · 最大堆数-父项的密钥大于或等于子项的密钥。这称为max-heap属性。根将包含堆的最大值。
文章目录 前言 系列教程一览 “看，未来”的个人简介 指针&引用 数组 链表 栈 二叉树 平衡二叉树 红黑树 跳表 哈希散列表 图论算法 前缀树 前言 在写STL的时候，我就意识到了缺少了一篇数据结构...组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。...关于数组的详尽解释可以移步：为实习准备的数据结构（1）-- 详尽数组篇 ---- 链表 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。...喏，看： 1.每个结点有零个或多个子结点； 2.没有父结点的结点为根结点； 3.每一个非根结点只有一个父结点； 4.每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树...由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。 红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。
dependencies的区别，因此这部分主要总结pom.xml文件中这两个标签的区别： 1、DepencyManagement的应用场景： 当我们的项目模块很多的时候，我们使用Maven管理项目非常方便...在我们项目顶层的POM文件中，我们会看到dependencyManagement元素。通过它元素来管理jar包的版本，让子项目中引用一个依赖而不用显示的列出版本号。...同时可以避免在每个使用的子项目中都声明一个版本号，这样想升级或者切换到另一个版本时，只需要在父类容器里更新，不需要任何一个子项目的修改；如果某个子项目需要另外一个版本号时，只需要在dependencies...如果项目中不写依赖项，则会从父项目继承（属性全部继承）声明在父项目dependencies里的依赖项。...如果不在子项目中声明依赖，是不会从父项目中继承下来的；只有在子项目中写了该依赖项，并且没有指定具体版本，才会从父项目中继承该项，并且version和scope都读取自父pom;另外如果子项目中指定了版本号
节点访问的次序,忽略打印行为 如果将打印安排在同个数字第一次被访问时,即先序遍历 第二次即中序遍历 第三次即后序遍历 现二叉树的先序、中序、后序遍历，包括递归方式和非递归 方式 二叉树结构定义...中序遍历非递归也是最难理解的! 2.3 后序遍历非递归 即要实现左右中,逆序中左右其实根据先序遍历非递归改变左右压栈顺序即可,然后该打印时不打印,而是放在辅助栈中,就成了左右中顺序,打印之!...假设有一 棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向 自己的父节点，头节点的parent指向null。...只给一个在二叉树中的某个节点 node，请实现返回node的后继节点的函数。 在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点 后继结点示例 前驱结点同理!...平衡二叉树（Self-balancing binary search tree） 又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
在非空的线性表中每个数据元素在线性表中都有唯一确定的序号,例如a0的序号是0,ai的序号是i. 在一个具有n > 0个数据元素的线性表中,数据元素序号的范围是[0,n-1]....相对的,表的另一端称为栈底(bottom) 当栈中没有数据元素时称为空栈;向一个栈插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈.由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定 先出栈....在双端队列出队时,无论前端出还是后端出,先出 的元素排列在后出的元素的前面....(树中每个节点最多只能有两个子节点) 与树的递归定义类似,二叉树的递归定义如下 : 二叉树或者是一颗空树,或者是一颗由一个根结点和两颗互不相交的分别称为根的左子树和右子树的子树所组成的非空树....在二叉树中每个结点都有两个孩子,则可以设计每个结点至少包括3个域 : 数据域,左孩子和右孩子域.
3.2.1 先序遍历 递归实现先序遍历 非递归方式实现先序遍历 （栈） 3.2.2 中序遍历 递归实现中序遍历 非递归实现中序遍历 3.2.3 后序遍历 递归实现后续遍历 非递归实现后序遍历 一、二叉树的性质...本期的 DFS 与 BFS 搜索算法，我将围绕二叉树来讲解，所以在了解什么是 BFS 与 DFS 之前，我们先来回顾一下二叉树 的基本概念 1.1 二叉树的特性 学过 数据结构与算法 的同学在接触二叉树的时候...它有且只有一个根节点，则是权值为 1 的节点 每个父节点有两个儿子节点，也可以只有一个节点 每个节点的儿子数量都是两个，这样的二叉树叫做 完全二叉树 每个节点的孩子可以分为 左孩子 和 右孩子 1.2...二叉树的遍历方式 在这里我们已二叉树为例，我们知道二叉树的遍历方式有如下四种，如果不理解前三种遍历，后面在 DFS 中，我会深入的讲解 先序遍历（先遍历根节点，然后左节点，右节点） 遍历结果 1 2...我们使用栈的后进先出，先进后出的特性 先进入的元素，就可以保存遍历的路径 元素出栈，就实现了回溯到上一个节点 栈保存的就是当前遍历过的所有节点 // 先序遍历的非递归实现 public
，而不只是相临的两个对象，而如果用联表去存储对象，由于在联表中取得对象的时间是线性的即O[n]，这样将使快速排序失去其快速的特点。...这个操作符能够在非相关的类型之间转换。操作结果只是简单的从一个指针到别的指针的值的二进制拷贝。在类型之间指向的内容不做任何类型的检查和转换。...容器 特性 所在头文件 向量vector 可以用常数时间访问和修改任意元素，在序列尾部进行插入和删除时，具有常数时间复杂度，对任意项的插入和删除就有的时间复杂度与到末尾的距离成正比，尤其对向量头的添加和删除的代价是惊人的高的... 双端队列deque 基本上与向量相同，唯一的不同是，其在序列头部插入和删除操作也具有常量时间复杂度 表list 对任意元素的访问与对两端的距离成正比，但对某个位置上插入和删除一个项的花费为常数时间...，放入容器中，最好不要对容器进行内存初始化（不要调用memset,zeromemory函数），否则如果结构体中有指针类型的变量时，就会出现问题。
现实中的树大家都见过，在数据结构中也有树，此树非彼树，不过数据结构的树和现实中的树在形态上确实有点相像。...❝什么是父节点？ ❞ 树的父子关系和现实中很相似，若一个节点含有子节点，则这个节点称为其子节点的父节点。 ❝什么是叶子节点？...树的特点 树形数据结构，具有以下的结构特点： 每个节点都只有有限个子节点或无子节点； 没有父节点的节点称为根节点； 每一个非根节点有且只有一个父节点； 除了根节点外，每个子节点可以分为多个不相交的子树；...二叉树 有了前面「树」的基础铺垫，二叉树是一种特殊的树，还记的上面我们学过「节点的度」吗？二叉树中每个节点的度不大于 2 ，即它的每个节点最多只有两个分支，通常称二叉树节点的左右两个分支为左右子树。...应用场景 红黑树在实际应用中比较广泛，有很多已经落地的实践，比如学习C++的同学都知道会接触到 STL 标准库，而STL容器中的map、set、multiset、multimap 底层实现都是基于红黑树
， 此时对列 中只有 ⇐[A] 我们将A出弹出队列，并将它的左右子树 BC加入队列，此时队列中有 ⇐[BC] ，打印出 A 我们将B出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[C]...，打印出 ABC 我们将C出弹出队列，并将它的左右子树 DE加入队列，此时队列中有 ⇐[DE] ，打印出 ABC 我们将D出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[E] ，打印出 ABCD...我们将E出弹出队列，并将它的左右子树 FG加入队列，此时队列中有 ⇐[FG] ，打印出 ABCDE 我们将F出弹出队列，它没有子树，我们不做任何操作，此时队列中有 ⇐[G] ，打印出 ABCDEF 我们将...二叉排序树或者是一颗空树，或者具有以下特例的非空二叉树： 若左子树非空，则左子树上所有结点关键字均小于根结点的关键字 若右子树非空，则右子树上所有结点关键字均大于根结点的关键字 左右子树本身也分别是一颗二叉排序树...若二叉排序树非空，将给定值与根节点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字大于给定关键字时，在根结点的左子树中查找，否则在根结点的右子树中查找。
树和二叉树 树 什么是树 在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。...根节点没有父节点；非根节点有且仅有一个父节点。 每个非根节点可以分为多个不相交的子树。 树里面没有环路。...树的术语 节点的度：一个节点含有的子树的个数称为该节点的度； 树的度：一棵树中，最大的节点度称为树的度； 叶子节点或终端节点：度为零的节点； 非终端节点或分支节点：度不为零的节点； 父节点：若一个节点含有子节点...二叉树的遍历 二叉树的遍历有三种方式： 前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。...第二，哈希表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O (logn)。
在队列中，允许入队操作的一端称为队尾，允许出队操作的一端称为队头。...在许多应用中，通常需要收集一部分数据，从中挑选具有最小或最大关键码(优先级)的记录开始处理。接着，可能会收集更多数据，并处理当前数据集中具有最小或最大关键码的记录。...假定在各个数据记录或元素中，存在一个能够标识数据记录或元素的数据项，并将依据该数据项对数据进行组织，则可称此数据项为关键码(key)。...根据完全二叉树的性质，由堆存储在下标为0开始计数的数组中，因此，在堆(数组)中给定下标为 $i$的结点时： 如 $i=0$，则结点 $i$ 为根结点，无父结点，否则结点 $i$ 的父结点为结点 $\lfloor...通常，从最小堆中删除具有最小关键码记录的操作是将最小堆的堆顶元素，即其对应完全二叉树的顺序表示的第0号元素删去。
1 引言 在工程实践中,一个工程项目往往由若干个子项目组成。这些子项目间往往有两种关系: （1） 先后关系，即必须在某个项完成后才能开始实施另一个子项目。 ...（2） 子项目间无关系，即两个子项目可以同时进行,互不影响。 例如：在工厂里产品的生产线上，一个产品由若干个零部件组成。...拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj之前，则我们称这样的顶点序列为一个拓扑序列。...若使用队列保存入度为0的顶点，则可以将这个算法复杂度将为O（V+E）。 5 DFS方法 深度优先搜索过程中，当到达出度为0的顶点时，需要进行回退。在执行回退时记录出度为0的顶点，将其入栈。...则最终出栈顺序的逆序即为拓扑排序序列。 5.1 算法流程 （1）对图执行深度优先搜索。 （2）在执行深度优先搜索时，若某个顶点不能继续前进，即顶点的出度为0，则将此顶点入栈。
1.概念 二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。...堆排序中的堆就是完全二叉树。 ? 3.二叉树的遍历 ?...nodequeue.empty()) //建立节点队列，打印父节点，入队左右子节点，出队父节点 { node* p = nodeQueue.front();...nodequeue.empty()) //建立节点队列，打印父节点，入队左右子节点，出队父节点 { node* p = nodequeue.front(...3.3 非递归法 二叉树遍历 前序（入栈root，访问stack.top(), 出栈，依次入栈右节点，左节点） void stackPreOrder() { stack*> nodeStack
树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的结构，比如文件系统中的文件；树还被用来存储有序列表。...二叉树与二叉查找树 二叉树是一种特殊的树，它的子节点个数不超过两个；一个父节点的两个子节点分别称为左节点和右节点。...二叉查找树(BST)是一种特殊的二叉树；相对较小的值保持在左节点中，较大的值保存在右节点中。...③然后pop出第二项即22，遍历右子树，得30，因为console是在先递归左子树后打印的，所以把30插到(push)56和22中间，结果为[56,30,22,10]。...⑤然后pop出第四项即56，遍历该右子树，得结果[92,81,56,30,22,10] ⑥然后pop出第五项即81，发现有左子树77，所以push进去，又因为console代码在中间，所以要放到92和81
根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。...有两个指向左右子树的指针，还有一个指向父节点的指针。 1、 思路 ? 求中序遍历的下一节点，就要分各种情况（明确中序遍历下一结点在二叉树中的位置有哪些），然后对某种情况详细分析。...从根节点开始按层遍历打印结点（自左往右），下一层的遍历是上一层的字节点，但是我们发现想要获取到上层结点的子节点时，上层的父节点已经遍历过去可，想要在获取到，必须存储父节点。...然后下层遍历的时候，自左往右取出父节点，依次打印子节点。 上方的解题思路中父节点的存储和遍历让我们想到一个熟悉的数据结构，对了，“先进先出”的思想，那就是队列。...思路二：寻找最长路径，借助遍历最长路径的设计思路记性改进。只需记录两个子树最深的结点为主。 2、 测试用例 ? ? 完全二叉树、非完全二叉树 —— 普通测试。 ?
二叉树是树结构中一种典型的结构，每个节点最多只能有两个子节点，一个是左侧子节点，一个是右侧子节点 二叉树图例 二叉树遍历的规律 前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历 中序遍历：左子树中序遍历...+ 根节点 + 右子数中序遍历 后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点 创建一棵二叉树 要求：若新节点的值比父节点小，则放到父节点的左子树上；反之放到右子树上 // 二叉树节点 class...：非递归版本（回溯算法）实现中序遍历 非递归版本的好处：避免循环递归时栈溢出的情况，效率更高 非递归版本流程 1）步骤 1 ：左孩子入栈 -> 直至左孩子为空的节点 2）步骤 2 ：节点出栈 -> 访问该节点...)); // 打印结果： [1, 2, 3, 4, 5, 6, 7, 8, 9] 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，重建出该二叉树 原理 前序遍历：根节点 + 左子树前序遍历 +...随机取m个数，有多少种组合 总结 文中列出了现在市面上比较火的一些题目，同时包含了我面试中遇到的所有算法题 算法在阿里、头条、美团的面试中，几乎是必考的 特别是二叉树，我几乎每次都会遇到，为啥大厂对二叉树这么情有独钟
系列文章(一)（基础知识篇） 作者主页： https://juejin.cn/user/2594503172831208 正文 之前我对算法的理解，仅仅是为了应付大厂的面试 但是在两个月的算法练习中，...二叉树是树结构中一种典型的结构，每个节点最多只能有两个子节点，一个是左侧子节点，一个是右侧子节点 二叉树图例 二叉树遍历的规律 前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历 中序遍历：左子树中序遍历...+ 根节点 + 右子数中序遍历 后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点 创建一棵二叉树 要求：若新节点的值比父节点小，则放到父节点的左子树上；反之放到右子树上 // 二叉树节点 class...：非递归版本（回溯算法）实现中序遍历 非递归版本的好处：避免循环递归时栈溢出的情况，效率更高 非递归版本流程 1）步骤 1 ：左孩子入栈 -> 直至左孩子为空的节点 2）步骤 2 ：节点出栈 -> 访问该节点...算法在阿里、头条、美团的面试中，几乎是必考的 特别是二叉树，我几乎每次都会遇到，为啥大厂对二叉树这么情有独钟？
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
