（先序遍历和后序遍历不能确定唯一的二叉树，因为这时候没法区分左子树和右子树） 对于完全二叉树，我们可以使用顺序存储来方便的实现。...这个缺点总是无法避免的。 实际上，我们经常使用的是链式存储二叉树。下面给出链式存储二叉树的ADT。...（避免了求出二叉树的先序，中序，或者后序序列。）创建过程如下： 输入第一个数据，若不为0，则赋值，入队；若为0，则返回空树。 若队列不空，则出队一个元素，并创建该节点的左右子树。...可以在不借助堆栈的情况下使用循环语句来完成。所以前序和中序的非递归函数是几乎一致的。都是借助一个堆栈，将左子树入栈，然后弹出转右子树。...但是后序遍历的最后一句并不是“尾递归”，使得无法仅通过一个堆栈就完成。所以后序遍历的非递归版本和上面的看起来有些不一样。
二叉树也是常用的数据结构，通过使用二叉树可以快速的对数据进行排序或者查找，在常用的堆排序算法中，堆的底层实质就是一个模拟的完全二叉树！等等，什么是完全二叉树？二叉树又是什么？有哪几类？...让我们开始今天的算法课堂～ 二叉数的概念和分类 二叉树是每个树节点最多有两个子树的一种特殊的树结构，其有一些内在的性质，比如，若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个节点（i>=0）,高度为...k的二叉树最多有2^(k+1)-1个节点（空树的高度为-1）。...，对其进行中序遍历后，会得到一个有序的列表，这是我们经常用到的一种数的结构 平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，并且满足二叉搜索树的规则...（先、中、后序） 首先我们要清楚，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程！
它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。 Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。...完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树；叶节点只能出现在最下层和次下层...平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。...Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。...简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。 B-，B+，B*树 B-树（或B树）是一种平衡的多路查找(又称排序)树，在文件系统中有所应用。
二叉树性质 引理5.1：二叉树中层数为i的结点至多有 2^i 个，其中 i \geq 0 。 引理5.2：高度为k的二叉树中至多有 2^{k+1}-1 个结点，其中 k \geq 0 。...还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。 遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。...中序遍历非递归 a. 算法NIO b. 算法解读 NIO算法利用了一个辅助堆栈S来模拟递归过程中的函数调用栈。...通过在循环中不断将左子节点入栈，然后处理栈顶节点，并将指针移动到右子节点，实现了中序遍历的非递归算法。 创建一个空堆栈S，并将指针p指向树的根节点t。 进入循环，只要p不为空，执行以下步骤： a....这个非递归中序遍历算法可以应用于需要遍历二叉树并按照中序顺序访问节点的场景，例如在构建二叉树的线索化结构时，或者需要按照中序顺序遍历二叉搜索树等情况下。 c.
平衡二叉搜索树 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。...最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。...「之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构」，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。...栈与队列：总结篇！ 栈与队列：求前 K 个高频元素和队列有啥关系？ 栈与队列：滑动窗口里求最大值引出一个重要数据结构 栈与队列：有没有想过计算机是如何处理表达式的？
二叉树性质 引理5.1：二叉树中层数为i的结点至多有 2^i 个，其中 i \geq 0 。 引理5.2：高度为k的二叉树中至多有 2^{k+1}-1 个结点，其中 k \geq 0 。...还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。 遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。...中序遍历非递归 【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO） 5. 后序遍历非递归 a. 算法NPO b....算法解读 算法NPO(t)利用了一个辅助堆栈S来遍历二叉树T的所有节点。 如果t为空，则直接返回。 创建一个空堆栈S，并将根节点t和初始标记0入栈（S 堆栈，用于模拟递归调用栈 int tagStack[100]; // 标记堆栈，用于记录结点的访问状态 int top = -1;
一.了解项目功能 在本次项目中我们的目标是实现一个链式二叉树: 该链式二叉树使用动态内存分配空间,可以用来存储任意数量的同类型数据....为直观分析链式二叉树中的递归思路,在后续的功能实现部分,我会频繁使用下面这棵树画函数递归展开图,大家可以先熟悉一下这棵二叉树,我们马上就开始实现具体的功能: 1.实现链式二叉树程序菜单 菜单部分的逻辑比较简单...实现层序遍历的思路为(借助队列实现): 将根节点入队 如果队首结点不为空,将队首结点不为空的孩子入队 访问队首元素并将其出队 注:因为在之前的文章中我们已经实现过链队列程序了,所以在树部分我们不涉及讲解链队列的实现...0 : TreeSize(root->left) + TreeSize(root->right) + 1; //从这条语句里体会分治的思想 } 14.实现链式二叉树高度计算 二叉树的高度计算上我们同样采用递归分治的思想...,即 二叉树的高度为左子树和右子树高的那个高度再加上根结点自己的高度,即 二叉树的高度=左子树的高度>右子树的高度?
二叉树性质 引理5.1：二叉树中层数为i的结点至多有 2^i 个，其中 i \geq 0 。 引理5.2：高度为k的二叉树中至多有 2^{k+1}-1 个结点，其中 k \geq 0 。...还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。 遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。...中序遍历非递归 【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO） 5. 后序遍历非递归 【数据结构】树与二叉树（九）：二叉树的后序遍历（非递归算法NPO） 6....算法解读 算法NPO(t)利用了一个辅助堆栈S来遍历二叉树T的所有节点。 如果根节点t为空，则直接返回。 创建一个空堆栈S，并将根节点t和初始标记0入栈（S 的左右子树都已处理完毕，将节点p从堆栈S中弹出（S.pop()）。 跳转到步骤3，继续循环，直到堆栈S为空。 c. 复杂度分析 设二叉树有n个结点。
有没有想过它是如何工作的？其思路就是，按照最后的状态排列在先的顺序将工作的先前状态（限于特定数字）存储在内存中。这只用数组是无法实现的，因此堆栈就有了用武之地。 可以把堆栈看作一堆垂直排列的书籍。...使用堆栈计算后缀表达式 对堆栈中的值进行排序 检查表达式中的括号是否平衡 队列 与堆栈类似，队列是另一种线性数据结构，以顺序方式存储元素。...常问的队列面试问题： 使用队列来实现堆栈 颠倒队列中前 k 个元素的顺序 使用队列生成从 1 到 n 的二进制数 链表 链表是另一个重要的线性数据结构，刚一看可能看起来像数组，但在内存分配，内部结构以及如何执行插入和删除的基本操作方面有所不同...链表就像一个节点链，其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果列表是空的，那么它只指向 null 或不指向任何内容。...常问的树面试问题： 找到一个二叉树的高度 找到一个二叉搜索树中第 k 个最大值 找到距离根部“k”个距离的节点 找到一个二叉树中给定节点的祖先（ancestors） 字典树 字典树，也叫“前缀树”，是一种树形结构
在递归遍历中，递归工作栈的栈深度恰好为树的深度，最坏的情况下二叉树是有n个结点且递归深度为n的单支树，遍历算法的空间复杂度为O(n)；最好的情况下二叉树达到平衡状态，此时空间复杂度为O(log₂n)。...但在最坏的情况下，即构造二叉排序树输入序列是有序的，则会形成一个倾斜的单分支，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数N。...如果二叉排序树是一个只有右（左）孩子的单分支（类似于有序的单链表），其平均查找长度与单链表相同，为O(n) 如果二叉排序树的左、右子树的高度差的绝对值不超过1，这样的二叉排序树称为平衡二叉树。...平衡二叉树 为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差绝对值不超过1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL）。...平衡二叉树可定义为它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。 1.
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...解答 平衡树意味着我们需要对比任何在同一个根下的左右子树的高度差，还记得之前我们计算树的高度么，使用递归方式来解决，其实这道题与算高度差不多，只是两边高度需要算出一个差值。...算法的主要思想： 不断对比每两个节点的左右子树的最大高度差，注意取差的绝对值，需要小于等于1 对比完左右子树之后，需要递归左子树以及右子树进行分别判断，都满足才是平衡树 Java 代码如下： public...但是判断每个节点最大高度需要递归左右子树，需要占用 O(log2n)，所以总共占用O(Nlog2n) 空间复杂度O(n)：最差情况下，也就是树退化为链表时，递归需要使用 O(n) 的栈空间，严格意义上递归栈也需要空间...-1 : 1 + max(left, right); } }; 时间复杂度O(n)：每个节点计算一次 空间复杂度O(n)：递归需要使用额外堆栈空间 【作者简介】 秦怀，技术之路不在一时，山高水长
队列变种：优先队列(priority queue)，队列中每个元素具有优先级，新的队列进行入队时，会根据优先级进行重新排序，重新定位到特定的位置；优先队列方便使用链表进行实现； 树：树的经典结构为二叉树结构...，根为第一层，根的子节点为第二层；以此类推； 树的高度或深度：节点最大层次； 堂兄弟节点：父节点在同一层的节点为堂兄弟； 节点的祖先：从根到节点所经分支上的所有节点； 子孙：以某以节点为根的子树中任一节点都称为该节点的子孙...除d层以外，其他各层的节点数目均已达到最大值；第d层所有节点从左到右连续地紧密排列，这样的二叉树称为完全二叉树，其中满二叉树的定义是最底层的所有叶节点都在的完全二叉树； 平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于...1的二叉树； 排序二叉树（二叉查找树，binary searcg tree）： 若左子树不空，则左子树上所有节点的值都小于它的根节点的值； 若右子树不空，则右子树上所有节点的值都大于它的根节点的值；...广度优先遍历(Breadth First Search): 从树的根开始，从上到下，从左到右遍历整个树的节点； 深度优先遍历一般用递归实现，广度优先一般使用队列实现；一般情况下能用递归实现的大部分算法也能用堆栈来进行实现
，跟手动插入无异，后面会在搜索二叉树篇章讲解二叉树插入的实现 销毁 递归调用完成销毁，每棵树先释放左孩子和右孩子，再返回去销毁根，因此使用后序遍历的方法最为合适（不需要记录孩子，只需要正常遍历销毁即可...通常使用队列（Queue）来实现层序遍历。...，同样使用递归实现，只是细节略有差异: 递归调用: 对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。...二叉树的高度（或深度）是指从根节点到最远叶子节点的最长路径上的节点数。...一个空树的高度定义为0 对于非空二叉树，其高度可以通过递归的方式计算： 如果树是空的，那么高度是0。 否则，高度是左子树和右子树高度的最大值加1（加1是因为要算上根节点）。
平衡二叉搜索树 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。...最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。...之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。...而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。 这里其实我们又了解了栈与队列的一个应用场景了。
堆栈可以使用数组或链表来实现。 它们是做什么用的？ 现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。...队列可以使用固定长度的数组、循环数组或链表来实现。 它们是做什么用的？ 这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。...例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。 一种特殊且非常重要的队列类型是优先级队列。...特性 ANY自平衡BST中ANY操作的摊销时间复杂度为O(log n)； 在最坏的情况下，AVL 的最大高度是 1.44 * log2n（为什么？...SPT 是一种自平衡二叉树，但该算法可以使用堆（或优先级队列）来实现。我们将讨论堆解决方案，因为它的时间复杂度是 O(|E|*log |V|)。这个想法是使用图形的邻接列表表示。
~画图分析~ 怎么样~有没有体会到递归的暴力美学呢？...//根结点最后打印 LasOrder(root->left); LasOrder(root->right); printf("%c ", root->data); } 这里三种遍历相信问题不大，递归的魅力有没有体会到呢...接下来我们继续使用递归对二叉树进行操作~ 二叉树操作 还是以这一个二叉树为例 二叉树结点个数 这里我们来巧妙的使用递归方法求结点个数~ 原理： 总结点个数 = 1 + 左子树结点个数 +右子树结点个数.../高度 思路： 二叉树的深度/高度 = 1 + Max（左子树深度/高度、右子树深度/高度最大值） （如果为空返回0） 代码： // 二叉树的深度/高度 int BinaryTreeDepth...这里同样需要使用队列~这里我们来画图找完全二叉树和非完全二叉树的区别~ 完全二叉树： 1.根结点入队列 2.队列不为空，取队头出队头，将左右孩子结点入队列（这里结点为空也入，方便后面判断），如此循环，到取到
有没有想过它是如何工作的？其思路就是，按照最后的状态排列在先的顺序将工作的先前状态（限于特定数字）存储在内存中。这只用数组是无法实现的，因此堆栈就有了用武之地。 可以把堆栈看作一堆垂直排列的书籍。...，则返回 true Top ——返回顶部元素，但不从堆栈中删除 常见的堆栈面试问题： 使用堆栈计算后缀表达式 对堆栈中的值进行排序 检查表达式中的括号是否平衡 队列 与堆栈类似，队列是另一种线性数据结构...isEmpty() —— 如果队列为空，则返回 true Top() —— 返回队列的第一个元素 常问的队列面试问题： 使用队列来实现堆栈 颠倒队列中前 k 个元素的顺序 使用队列生成从 1 到 n 的二进制数...链表就像一个节点链，其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果列表是空的，那么它只指向 null 或不指向任何内容。...常问的树面试问题： 找到一个二叉树的高度 找到一个二叉搜索树中第 k 个最大值 找到距离根部“k”个距离的节点 找到一个二叉树中给定节点的祖先（ancestors） 字典树 字典树，也叫“前缀树”，是一种树形结构
递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。 递归的优缺点？...递归常见问题及解决方案 1.警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 2.警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。...* 2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 * 3.警惕快排的递归发生堆栈溢出，有2种解决方法，如下： ①限制递归深度，一旦递归超过了设置的阈值就停止递归。...（2）一致性哈希算法 【07-二叉树】 之前说的栈和队列都是线性表结构，树是非线性表结构。 关于树的常用概念：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。...二叉查找树的时间复杂度分析： 完全二叉树（或满二叉树），不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。
你想啊，DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对？...还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点总数为N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是O(logN)。...但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是N/2，用 Big O 表示的话也就是O(N)。...由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。...比如我们刚才讨论的二叉树最小高度的问题，你一开始根本就不知道终点在哪里，也就无法使用双向 BFS；但是第二个密码锁的问题，是可以使用双向 BFS 算法来提高效率的，代码稍加修改即可： int openLock
数据 指向左子节点的指针 指向右子节点的指针 树：与阵列，链接列表，堆栈和队列（线性数据结构）不同，树是分层数据结构。 树 词汇表：最顶层的节点称为树的根。直接位于元素下的元素称为子元素。...二叉树的类型 满二叉树（Full binary tree） 如果每个节点有0或2个子节点，则二叉树已满。 以下是满二叉树的示例。...h的完美二叉树（其中高度是从根到叶的路径上的节点数）具有2^(h - 1)个节点。...二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值； （2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值； （3）左、右子树也分别为二叉排序树...所以我们应该使用哪种遍历？ - 前序或中序或后序？答案很简单 -> 后序，因为在删除父节点之前，我们应该首先删除它的子节点。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
实时音视频
