二叉树是一个树，但，每个节点最多有两个孩子节点，一左一右，左边的称为左孩子，右边的称为右孩子，我们看两个例子，如下所示： ?...这两棵树都是二叉树，左边的根节点为5，除了叶子节点外，每个节点都有两个孩子节点，右边的根节点为7，有的节点有两个孩子节点，有的只有一个。...比如说左边的树，根节点为5，左边的都小于5，右边的都大于5。再看右边的树，根节点为7，左边的都小于7，右边的都大于7，在以3为根的左子树中，其右子树的值都大于3。 排序二叉树有什么优点？...此外，在排序二叉树中，可以方便的查找最小最大值，最小值即为最左边的节点，从根节点一路查找左孩子即可，最大值即为最右边的节点，从根节点一路查找右孩子即可。...理解了排序二叉树的基本概念和算法，理解TreeMap和TreeSet就比较容易了，让我们在接下来的两节中探讨这两个类。
堂兄弟节点：双亲在同一层的节点互为堂兄弟，如上图：H，I互为堂兄弟节点 节点祖先：从根到该节点所经分支上的所有节点，如上图：A是所有节点的祖先 子孙：以某节点为根的子树中任一节点都称为该节点的子孙，如上图...每个目录可以看作是树中的一个节点，子目录和文件则作为其子节点。这样的结构方便用户对文件进行分组，并且能够清晰地表示出文件之间的层级关系。...兼容性与标准化：由于树结构在文件系统设计中的普遍应用，它有助于不同操作系统和应用程序之间实现更好的兼容性和标准化。...完全二叉树的性质是：除了最后一层外，其他各层的节点数都达到最大个数，并且最后一层的节点都集中在该层最左边的若干位置上。...只有左孩子的节点数： 对于完全二叉树，只有左孩子的节点出现在最后一层的左边，且其右兄弟节点不存在。
avl树即平衡树，他对二叉树做了改进，在我们每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。...如果超过了就对其进行调平衡，具体的调平衡操作就不在这里讲了，无非就是四个操作——左旋，左旋再右旋，右旋再左旋。 ? 如图所示，图中M结点就是一个二节点，M左边的EJ节点是一个三节点。...依然是大的数据放右边，小的数据放左边。此时我们向该树重如果该数可以直接放入二节点中，就直接进去，但如果正好需要放在三节点中，就像图中一样，Z正好要放在SX中。...这里节点之间的连接分为红连接和黑连接，取代了红节点和黑节点的定义（本质是一样的），将之前的黑高度相等定义为了黑连接数相等。更为直观。...而如图所示，其实红黑树的每一步操作都对应了二三树的操作，如果是二节点就是黑连接，三节点的话里面的两个数之间就是红连接。 红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。
树 无序树：任意节点的子节点之间没有任何的顺序关系，称之为无序树，也叫自由树 有序树：子节点之间由顺序关系 二叉树：每个节点最多含有两个子树的树 完全二叉树：若一棵树的深度为d，除去第d层外...，其他各层的节点数目达到了最大值，且第d层所有节点从左向右连续紧密的排列的二叉树 满二叉树：所有层的节点数达到了最大数 平衡二叉树：当且仅当任何节点之间的两颗子树的高度差不大于1的二叉树 排序二叉树：二叉搜索树...，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大 霍夫曼树：用于信息编码 B树/B^+树：在MySQL的索引中使用 应用场景 HTML文件 路由协议 mysql索引 文件目录的目录结构...对于频繁访问的表，innodb会透明建立自适应hash索引，即在B树索引基础上建立hash索引，可以显著提高查找效率，对于客户端是透明的，不可控制的，隐式的。 哈希索引 基于哈希表实现。...存储引擎会对所有的列计算一个哈希码， Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针 B+ Tree B树是一种多路搜索树，每个节点可以拥有多于两个子节点。
空树中没有结点。 补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能有交集。...对于上图1来说，1 结点在第一层，2,3,4 为第二层，5,6,7,8,9,10在第三层，11,12,13在第四层。 一棵树的深度（高度） 是树中结点所在的最大的层次。...有序树和无序树 如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。 ...在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。...二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。 二叉树还可以继续分类，衍生出满二叉树和完全二叉树。
而中序遍历的形式总是 [ 左子树的中序遍历结果, 根节点, 右子树的中序遍历结果 ] 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。...对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。...// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root->right = myBuildTree...而中序遍历的形式总是 [ 左子树的中序遍历结果, 根节点, 右子树的中序遍历结果 ] 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。...二叉搜索树的节点放置规则是：任何节点的键值一定大于去其左子树中的每一个节点的键值，并小于其右子树的每一个节点的键值。 所以在二叉树中找到最大值和最小值是很简单的，比较麻烦的是元素的插入和移除。
； 堂兄弟节点：双亲在同一层的节点互为堂兄弟； 节点的祖先：从根到该节点所经分支上的所有节点； 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。...完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。 ...二叉树的性质： 1) 在非空二叉树中，第i层的结点总数不超过2i-1, i>=1; 2) 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点; 3) 对于任意一棵二叉树，如果其叶结点数为...平衡二叉树 上面提到，普通的二叉树在极端的情况会退化成线性结构，比如出现所有的节点都在左边，或者所有的节点都在右边，这样没法发挥树形结构的威力了。...红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求： 节点是红色或黑色。 根是黑色。
在二叉树中，如果节点没有子树，则左子树和右子树都为空，如果节点只有一个子树，要根据子树的左右来区分子树是左子树还是右子树，如果节点有两个子树，则左子树和右子树都有。...如下图中的二叉树，对于根节点A，左子树是以节点B为根的子树，高度为4，右子树是以节点C为根的子树，高为2，A的左子树与右子树的高度差为2(高度差大于1)，所以这不是一棵平衡二叉树。...如下图，左边的树中，除了叶节点D，所有节点都只有左子树，这是一棵左斜树，同理，右边的树是一棵右斜树。 三、二叉树的特点和性质 通过对二叉树的介绍和对几种特殊二叉树的了解，可知二叉树有以下特点： 1....每个节点最多有两颗子树，所以二叉树中节点的度不大于2，二叉树的度也不会大于2。 2. 左子树和右子树的次序不能颠倒。 3. 即使某节点只有一棵子树，也要根据左右来区分它是左子树还是右子树。...对于任意一棵二叉树，如果其叶节点数为M，度为2的节点总数为N，则 M=N+1 。
首先，我们来讲讲什么是树： 树是一种非线性的数据结构，相对于线性的数据结构(链表、数组)而言，树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高) 在现实生活中，我们一般的树长这个样子的： ?...二叉树的意思就是说：每个节点不能多于有两个儿子，上面的图就是一颗二叉树。 一棵树至少会有一个节点(根节点) 树由节点组成，每个节点的数据结构是这样的： ?...有意思的是：通过先序和中序或者中序和后序我们可以还原出原始的二叉树，但是通过先序和后续是无法还原出原始的二叉树的 也就是说：通过中序和先序或者中序和后序我们就可以确定一颗二叉树了！...二叉树中还有一种特殊的二叉树：二叉查找树(binary search tree) 定义：当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。...三、查询二叉查找树相关 3.1查询树的深度 查询树的深度我们可以这样想：左边的子树和右边的字数比，谁大就返回谁，那么再接上根节点+1就可以了 ?
3、节点的子树称为节点的孩子，节点称为孩子的双亲，同一个双亲的节点称为兄弟，节点的祖先为从根到该节点所经分支上的所有节点。根的子树中任一节点称为子孙。 4、节点层次从根算起，根为第一层。...双亲在同一层节点的互为堂兄弟。节点最大的层次称为节点的深度。各子树从左到右有秩序，则成为有序树，否则为无序树。 5、森林是m(m>=0)棵互不相交的树的集合。对于树的每个节点，其子树的集合即为森林。...3、二叉树具有五个性质 1)在二叉树的第i层，至多有2i-1个节点，i>=1 2)深度为k的二叉树，至多有2k-1个节点，k>=1 3)对任一棵二叉树，假设终端节点数目为a，度为2的节点数为b，则a=b...该方式存储时，n个节点的二叉链表，有n+1个空链域。 三、线索二叉树 1、定义：在链式二叉树的基础上进行改动。当链式二叉树某个节点的左指针没有指向时，其指向该节点的前驱，相对应的右指针指向后继。...array_push($assistStack,$node); //先压左边后压右边，这样下一轮循环的时候会先弹出右边的node
，拥有同一个父节点的节点之间才是兄弟节点 以上述右边图为例 节点的度，子树的个数。...二、二叉树 二叉树的特点 每个节点的度最大为2，即最多拥有两颗子树 左子树和右子树是有顺序的，即使节点只有一颗子树也要区分左子树右子树 二叉树是有序树 这些都是二叉树 二叉树的性质 非空二叉树的第...i层最多有2i-1个节点（i >= 1） 在高度为h的二叉树上最多有2h-1个节点（h >= 1） 对于任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点的个数为n2，那么n0 = n2 + 1...T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1 => n0 = n2 + 1 真二叉树 真二叉树所有节点的度要么为0要么为2，如下图中左边是真二叉树，右边非真二叉树...2h-1 总节点的数量为n，n = 2h-1，h = {log_2{(n+1)}} 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多 满二叉树一定是真二叉树，真二叉树不一定是满二叉树 完全二叉树
名字排序说明 其中有四个术语需要说明：节点、左节点、右节点、根节点。 其中每个红色圆球都算一个节点，节点左下边相连接的节点叫做左节点，而右边相连的叫做右节点。...对于其中每个节点，左子节点的值都比它小，而右子节点的值都比它大。比如 Alice < Herry < Mike。...二叉树存在不平衡的情况，比如以根节点为中间的界限，发现右边的节点数远超左边的节点数，那么左右不平衡，查找的效率就很低了。如下图所示： 右边节点数远大于左边节点数 那有没有平衡的二叉树呢？...当然有，那就是红黑树，限于篇幅和侧重点，这个放到下篇再讲吧 二叉树中的含义 二叉树定义 大白话说二叉树就是每个节点只能有两颗子树，且有左右之分。...二叉树的遍历 二叉树的遍历：从二叉树的根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点都能被访问一次，且仅被访问一次。 二叉树的访问次序可以分为四种： 前序遍历。 中序遍历。
完全二叉树： 叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。...而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ] 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。...对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。...// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root->right = myBuildTree...而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ] 只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。
二叉树：每个节点最多含有两个子树的树 完全二叉树：若一棵树的深度为d，除去第d层外，其他各层的节点数目达到了最大值，且第d层所有节点从左向右连续紧密的排列的二叉树 满二叉树：所有层的节点数达到了最大数...平衡二叉树：当且仅当任何节点之间的两颗子树的高度差不大于1的二叉树 排序二叉树：二叉搜索树，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大 霍夫曼树：用于信息编码 B树/B^...+树：在MySQL的索引中使用 树的存储 顺序存储：将数据结构存储在固定的数组中，遍历上有一定的优势，占空间 链式存储 应用场景 HTML文件 路由协议 mysql索引 文件目录的目录结构 AI算法都是树搜索...，比如决策树 二叉树 每个节点最多只有两个子节点，左子树和右子树，性质： 第i层上最多2^(i-1)个节点 深度为k的二叉数最多有2^k-1个节点 具有n个节点的完全二叉树的深度必为log2(n+1)...的栗子根据先序和中序确定一棵树： ?
可以看到线段树不是完全二叉树，因为如果是十个元素，是不一定都集中在左边的，这时候就不一定是完全二叉树了，但是一定是平衡二叉树。平衡二叉树的定义是，最短深度和最大深度的差只能为1，也就是不能超过1。...同样是使用递归实现，首先参数要包含的就是树的边界和要求的边界，如果边界是完全一样的，直接把当前树对应的值返回即可，如果边界是在左边，那就递归左边找，右边就右边找，两边都包含还是递归相加返回即可。...第一个条件很好理解，二叉树不平衡的条件，第二个条件是因为，既然是左侧多添加了一个节点，左边肯定比右边高，而平衡因子在这里计算的是左边减去右边，所以肯定是大于等于0的了。...再添加一个37节点，按照二叉树的常规操作，应该和当前节点比较，看看添加到哪里合适，但是对于2-3树不是，它永远不会添加到一个空的节点，会添加到最后一个叶子节点上，现在只有一个根节点，所以就需要和42融合...如果一个叶子节点本来就是三节点，添加到一个新的节点变成四节点在进行拆解的时候，就需要和它的父亲节点融合。 ? 所以在整一个添加过程中，2-3树的结构是绝对平衡的。
在讲红黑树之前，我们首先来了解下下面几个概念：二叉树，排序二叉树以及平衡二叉树。 二叉树 二叉树指的是每个节点最多只能有两个字数的有序树。通常左边的子树称为左子树 ，右边的子树称为右子树 。...继续回到我们的主题上，为了解决排序二叉树在特殊情况下会退化成链表的问题（链表的检索效率是 O(n) 相对正常二叉树来说要差不少），所以有人发明了平衡二叉树和红黑树类似的平衡树。...（从每个叶子到根的路径上不会有两个连续的红色节点。） 性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。...对于性质 5，这里我们需要注意的是，这里的描述是从任一节点，从任一节点到它的子树的每个叶子节点黑色节点的数量都是相同的，这个数量被称为这个节点的黑高。...这个问题可以这样理解，我们从性质5中知道，当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的，此时假如新的黑色节点的话，必然破坏规则，但加入红色节点却不一定，除非其父节点就是红色节点，因此加入红色节点
对于其中每个节点，左子节点的值都比它小，而右子节点的值都比它大。比如 Alice < Herry < Mike。...二叉树存在不平衡的情况，比如以根节点为中间的界限，发现右边的节点数远超左边的节点数，那么左右不平衡，查找的效率就很低了。如下图所示： [右边节点数远大于左边节点数] 那有没有平衡的二叉树呢？...当然有，那就是红黑树，限于篇幅和侧重点，这个放到下篇再讲吧 二叉树中的含义 二叉树定义 大白话说二叉树就是每个节点只能有两颗子树，且有左右之分。...二叉树的遍历 二叉树的遍历：从二叉树的根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点都能被访问一次，且仅被访问一次。 二叉树的访问次序可以分为四种： 前序遍历。 中序遍历。...**前序遍历**：通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。...，不够就扩容 struct TreeNode { int val; Seqlist* childSL; }; 第三种左孩子右兄弟表示 A左边指向第一个孩子B，B右边就是B的兄弟C，C的右边指向...同理B的左边指向第一个孩子E，E右边就是E的兄弟F struct TreeNode { int val; struct TreeNode* leftChild; struct TreeNode*...若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h -1 ....通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
例如:M的祖先是F、B、A 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 如上图：所有节点都是A的子孙 森林：由m（m>0）棵互不相交的树的集合称为森林....在树的双亲表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。...孩子兄弟表示法 孩子兄弟表示法:(很不错的表示方法) 即树的左边为孩子,右边为兄弟表示法又称为二叉树表示法或二叉链表表示法。...每个结点除了data域(数据域)外，还含有两个域: ①、最左边的孩子 ②、右边的兄弟 可以用一个小故事来方便我们理解....5.在具有 2n 个结点的完全二叉树中，叶子结点个数为_____. 6.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为_____.
那么回顾完全二叉树概念 设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数， 第 h 层所有的结点都连续集中在最左边。...那么我们知道一个满二叉树的节点数，满足以下公式，h为二叉树的高度： 节点数 = 2^h - 1 所以，对于完全二叉树，其总是满足以下两种情形： 1、node的右子树，到达底部，说明node的左子树是满二叉树...node的右子树没有到达底部 那么，根据以上两个情况，我们可以递归的求每个节点的节点数 算法实现 public static int completeTreeNum(Node head) {...1; } // node的右子树高度已经到底，说明node的左树是满二叉树 // 因此该树的节点数 = 左边满二叉树(2^(h - level) - 1...// 因此该树的节点数为： // 右边满二叉树(2^(h - level - 1) - 1) + node节点 + node的左节点数
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
