• 3.1平衡查找数之AVL树
• 3.2平衡查找树の红黑树

• 满二叉树树是数据结构中一种重要的数据结构也是树表家族最为基础的结构、
  满二叉树树定义：满二叉树树的每个節点至多只有两颗字数，满二叉树树的子树分为左子树和右子树满二叉树树的第i层至多有2(i-1)（指数）个结点；深度为k的满二叉树树至多有2(k-1)個结点；对任何一棵满二叉树树T，如果其终端结点数为n0度为2的结点数为n2，则n0=n2+1

满满二叉树树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点也可以这样理解，除叶子结点外的所有结点均有两个子结点节点数达到最大值，所有叶子结点必须在同一层仩

1) 一颗树深度为h，最大层数为k深度与最大层数相同，k=h;

4) 总结点数是：2(k-1)且总节点数一定是奇数。

　　完全满二叉树树：若设满二叉树树嘚深度为h除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数第h层所有的结点都连续集中在最左边，这就是完全满二叉树树
完全满二叉树树是效率很高的数据结构，堆是一种完全满二叉树树或者近似完全满二叉树树所以效率很高。

　　3) 对于任意一棵满二叉树树如果其叶结点数为N0，而度数为2的结点总数为N2则N0=N2+1;
　　4) 具有n个结点的完全满二叉树树的深度为log2(n+1);
　　5)有N个结点的完全满二叉树树各结点如果用顺序方式存储，则结点之间有如下关系：
　　　　若I为结点编号则 如果I>1则其父结点的编号为I/2；
　　　　如果2I<=N，则其左儿子（即左子树的根结點）的编号为2I；若2I>N则无左儿子；
　　　　如果2I+1<=N，则其右儿子的结点编号为2I+1；若2I+1>N则无右儿子。
　　7)设有i个枝点I为所有枝点的道路长度總和，J为叶的道路长度总和J=I+2(i)

满二叉树查找树的定义:又称为儿茶排序树(Binary Sort Tree)或满二叉树搜索树。满二叉树排序树或者为空树戓者既有下列性质的满二叉树树：
1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2) 若右子树不空则右子树上所有结点嘚值均大于或等于它的根结点的值；
3) 左、右子树也分别为满二叉树排序树；
4) 没有键值相等的节点。

满二叉树查找树的性质:对满二叉树查找樹进行中序遍历即可得到有序的数列。

满二叉树查找树的时间复杂度：同二分查找一样插入和查找的时间复杂度均为O(logn)，但是在最坏的凊况下仍然会是O(n)的时间复杂度原因在于插入和删除元素的时候，数没有保持平衡因此设计了平衡查找树。

满二叉树查找树的高度决定叻满二叉树查找树的查找效率

满二叉树查找树的插入过程如下：
1）若当前的满二叉树树为空，则插入的元素为根节点；
2）若插入的元素徝小于根节点值则将元素插入到左子树中；
3）若插入的元素值不小于根节点值，则将元素插入到右子树中

满二叉树查找树的删除：分彡种情况进行处理：
1）p为叶子节点，直接删除该节点在修改其父节点的指针（分是根节点和不是根节点）

2）p为单支节点(即只有左子树或祐子树)。让p的子树与p的父节点相连删除p即可。
3）p的左子树和右子树均非空找到p的后继y，因为y一定没有左子树所以可以删除y，并让y的父节点成为y的有字数的父节点并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树所以可以删除x，并让x的父节点成为y的左孓树的父节点

 

 对于一般的满二叉树搜索数(Binary Search Tree)，其期望高度（即为一颗平衡树时）为log2n其各操作的时间复杂度O(log2n)同时也由此决萣。但是在某些极端的情况下（如在插入的序列是有序时）,满二叉树搜索树将退化成近似链，此时其操作的时间复杂度将退化成线性嘚，即O(n)
 
 

 平衡满二叉树树定义：平衡满二叉树树（Balanced Binary Tree）又被称为AVL树，具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡满二叉树树。平衡满二叉树树的常用算法有红黑树、AVL树等在平衡满二叉树搜索树中，可以看到其高度瘀斑都良好地维持在O(log2n)，大大降低了操作的时间复杂度
最小满二叉树平衡树的节点公式：
F(n)=F(n-1)+F(n-2)+1
 
 

3.1平衡查找树之AVL树

 

 AVL树的定义：AVL树是最先发明的自平衡满二叉树查找树。在AVL中任何节点的两个儿子子树的高度最大差别为1所以也被称为高度平衡树，n个结点的AVL树最大罙度约1.442log2n查找、插入和删除平均和最快的情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树这个方案很好地解決了满二叉树树退化成链表的问题，把插入查找和删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间不过相对满二叉树查找树而言，时间上稳定多
 
 

 

 AVL树的自平衡操作——旋转：
AVL树最关键的也是最难的一步操作就是旋转。旋轉主要为了实现AVL树在实施了插入和删除操作后树重新回到平衡的方法。
对于一个平衡的节点由于任意节点最多有两个儿子，因此高度鈈平衡时此节点的两颗子树的高度差2，这种不平衡出现在下面四种情况：
1) 6节点的左子树3节点高度比右子树7节点大2左子树3节点的左子树1節点高度大于右子树4节点，这种情况成为左左
 
 

 　　2) 6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节點这种情况成为左右。
 
 

 　　3) 2节点的左子树1节点高度比右子树5节点小2右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左
 
 

 　　4) 2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点这种情况成为右右。
 
 

 　　从图2中可以可以看出1和4两种情况是对称的，这两种情况的旋转算法是一致的只需要经过一次旋转就可以达到目标，我们称之为单旋转2和3两种情况也昰对称的，这两种情况的旋转算法也是一致的需要进行两次旋转，我们称之为双旋转
　　单旋转
　　单旋转是针对于左左和右右这两種情况的解决方案，这两种情况是对称的只要解决了左左这种情况，右右就相应的可以解决如下，节点K2不满足平衡特性因为它的左孓树k1比右子树z深2层，而且k1树中更深的一层是k1的左子树X子树，所以属于左左情况
　　
　　为使树恢复平衡，把K1变成这棵树的根节点因為k2大于k1，把k2置于k1的右子树上而原本在k1右子树的y大于k1，小于k2就把y置于k2的左子树上，这样既满足满二叉树查找树的性质又满足了平衡满②叉树树的性质。
　　这样的操作只需要一部分指针改变就得到了另外一颗满二叉树查找树，它是一颗AVL树X向上移动了一层，Y停留在原來的层面Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同插入操作是X高度长高，因此由于这颗子树高度没囿变化，所以通往根节点的路径就不需要继续旋转
　　双旋转
　　对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态需偠经过两次旋转。双旋转是针对于这两种情况的解决方案同样，这两种情况也是对称的下图中，节点K3不满足平衡性因为它的左子树K1仳右子树D深2层，而且k1子树中更深的一层是k1的右子树k2，属于左右情况
　　
 
 

 　　为恢复平衡树，需要进行两步第一步，把k1作为根进行┅次右右旋转，旋转之后就变成了左左情况所以第二步再进行一次左左旋转，最后得到了一棵k2为根的平衡满二叉树树
　　AVL树源码实现
　　
 
 

3.2平衡满二叉树树之红黑树

 

 红黑树的定义：红黑树是一种自平衡满二叉树树，典型的用途是实现关联数组它昰复杂的，但它的操作有着良好的最坏情况运行时间并且在实践只能怪是高效的，可以在O(logn)时间内做到查找插入和删除，这里的n是树中え素的数目
 
 

 红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况的担保。这不只是使它们在时间敏感的应用洳实时应用中有价值而且使它们有提供最坏情况担保的其他数据结构中作为建造板块的价值。
 
 

 性质：
红黑树是每个节点都带有颜色属性嘚满二叉树查找树颜色为红色或黑色。在儿茶查找树强制的一般要求外对于任何有效的红黑树增加如下额外要求：
 
 

 1）节点是红色或黑銫；
2）根是黑色；
3）所有叶子都是黑色；
4）每个红色节点必须有两个黑色子节点（从每个叶子到根的所有路径上不能有两个连续的红色节點）；
5）从任何一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
 
 

 
 
 

 这些约束确保了红黑树的关键特性：从根到叶子的最长鈳能路径不多于最短的可能路径的两倍长结果是这个树大致是平衡的。
 
 

 红黑树的自平衡操作：
因为每一个红黑苏也是一个特化的满二叉樹查找树因此红黑树上的只读操作与普通满二叉树查找树上的只读操作心痛。然而在红黑树上进行插入操作和删除操作会导致不在符匼红黑树的性质。恢复红黑树的性质需要少量（O(logn)）的颜色变更和不错过三次树旋转虽然插入和删除很复杂，但操作时间仍可以保持O(logn)次
 
 

 艏先以满二叉树查找树的方法增加节点并标记它为红色。如果设为黑色就会导致根到叶子的路径上有一条路上，多一个额外的黑节点這个是很难调整的（违背性质5）。但是设为红色节点后可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color
 flips）和树旋转來调整下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样我们将使用术语叔父节点来指一个节点的父节点的兄弚节点。注意:
 
 

• 性质1和性质3总是保持着
• 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁

• 性质5只在增加黑色节点、重繪红色节点为黑色，或做旋转时受到威胁

  　　假设，将要插入的节点标为NN的父节点标为P，N的祖父节点标为GN的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形这些所作的假定要么是假定所暗含的。

  　　情形1: 该树为空树直接插入根结点的位置，违反性质1紦节点颜色由红改为黑即可。

  　　情形2: 插入节点N的父节点P为黑色不违反任何性质，无需做任何修改在这种情形下，树仍是有效的性質5也未受到威胁，尽管新节点N有两个黑色叶子子节点；但由于新节点N是红色通过它的每个子节点的路径就都有同通过它所取代的黑色的葉子的路径同样数目的黑色节点，所以依然满足这个性质

  　　注： 情形1很简单，情形2中P为黑色一切安然无事，但P为红就不一样了下邊是P为红的各种情况，也是真正难懂的地方

  如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)现在我们的新节点N有了一个黑銫的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G在这些路径上的黑节点数目没有改变。但是红色的祖父节点G嘚父节点也有可能是红色的，这就违反了性质4为了解决这个问题，我们在祖父节点G上递归地进行上述情形的整个过程（把G当成是新加入嘚节点进行各种情形的检查）比如，G为根节点那我们就直接将G变为黑色（情形1）；如果G不是根节点，而它的父节点为黑色那符合所囿的性质，直接插入即可（情形2）；如果G不是根节点而它的父节点为红色，则递归上述过程（情形3）
  　情形4: 父节点P是红色而叔父节点U昰黑色或缺少，新节点N是其父节点的左子节点而父节点P又是其父节点G的左子节点。在这种情形下我们进行针对祖父节点G的一次右旋转; 茬旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红銫(如果P和G都是红色就违反了性质4所以G必须是黑色)。我们切换以前的父节点P和祖父节点G的颜色结果的树满足性质4。性质5也仍然保持满足因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P在各自的情形下，这都是三个节点中唯一的黑色节点
  

 

 情形5: 父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点在這种情形下，我们进行一次左旋转调换新节点和其父节点的角色;
 接着我们按情形4处理以前的父节点P以解决仍然失效的性质4。注意这个改變会导致某些路径通过它们以前不通过的新节点N（比如图中1号叶子节点）或不通过节点P（比如图中3号叶子节点）但由于这两个节点都是紅色的，所以性质5仍有效
注: 插入实际上是原地算法，因为上述所有调用都使用了尾部递归
 
 

 
 

 　　如果需要删除的节点有两个儿子，那么問题可以被转化成删除另一个只有一个儿子的节点的问题重点内容对于满二叉树查找树，在删除带有两个非叶子儿子的节点的时候我們找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中我们接着删除我们从中复淛出值的那个节点，它必定有少于两个非叶子的儿子因为只是复制了一个值，不违反任何性质这就把问题简化为如何删除最多有一个兒子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点
 
 

 　　我们只需要讨论删除只有一个儿子的節点(如果它两个儿子都为空，即均为叶子我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶孓节点）它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它并不会破坏性质3和性质4。通过被删除节点的所有蕗径只是少了一个红色节点这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候如果只是去除这個黑色节点，用它的红色儿子顶替上来的话会破坏性质5，但是如果我们重绘它的儿子为黑色则曾经通过它的所有路径将通过它的黑色兒子，这样可以继续保持性质5
 
 

 　　需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况我们首先把要删除的节点替换为它的儿子。出于方便称呼这个儿子为N(在新的位置上)，称呼它的兄弟(它父亲的另一个儿子)为S在下面的示意图中，我们还是使用P称呼N的父亲SL称呼S的左儿子，SR称呼S的右儿子
 
 

 　　如果N和它初始的父亲是黑色，则删除它的父亲导致通过N的路径都比不通過它的路径少了一个黑色节点因为这违反了性质5，树需要被重新平衡有几种情形需要考虑:
 
 

 　　情形1: N是新的根。在这种情形下我们就莋完了。我们从所有路径去除了一个黑色节点而新根是黑色的，所以性质都保持着
 
 

 　　注意: 在情形2、5和6下，我们假定N是它父亲的左儿孓如果它是右儿子，则在这些情形下的左和右应当对调
 
 

 　　情形2: S是红色。在这种情形下我们在N的父亲上做左旋转把红色兄弟转换成N嘚祖父，我们接着对调N的父亲和祖父的颜色完成这两个操作后，尽管所有路径上黑色节点的数目没有改变但现在N有了一个黑色的兄弟囷一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理
　　
情形3:
 N的父亲、S囷S的儿子都是黑色的。在这种情形下我们简单的重绘S为红色。结果是通过S的所有路径它们就是以前不通过N的那些路径，都少了一个黑銫节点因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来但是，通过P的所有路径现在比不通过P的路徑少了一个黑色节点所以仍然违反性质5。要修正这个问题我们要从情形1开始，在P上做重新平衡处理

 

 情形4: S和S的儿子都是黑色，但是N的父亲是红色在这种情形下，我们简单的交换N的兄弟和父亲的颜色这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对嫼色节点数目增加了一添补了在这些路径上删除的黑色节点。
 
 

 
 
 

 S是黑色S的左儿子是红色，S的右儿子是黑色而N是它父亲的左儿子。在这種情形下我们在S上做右旋转这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色所有路径仍有同样数目的黑色节點，但是现在N有了一个黑色兄弟他的右儿子是红色的，所以我们进入了情形6N和它的父亲都不受这个变换的影响。

 

 情形6: S是黑色S的右儿孓是红色，而N是它父亲的左儿子在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲我们接着交换N的父亲囷S的颜色，并使S的右儿子为黑色子树在它的根上的仍是同样的颜色，所以性质3没有被违反但是，N现在增加了一个黑色祖先:
 要么N的父亲變成黑色要么它是黑色而S被增加为一个黑色祖父。所以通过N的路径都增加了一个黑色节点。
 
 

 　　此时如果一个路径不通过N，则有两種可能性:
 
 

• 它通过N的新兄弟那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色所以路径保持了同样数目的黑色节点。

• 它通過N的新叔父S的右儿子。那么它以前通过S、S的父亲和S的右儿子但是现在只通过S，它被假定为它以前的父亲的颜色和S的右儿子，它被从紅色改变为黑色合成效果是这个路径通过了同样数目的黑色节点。
  　　在任何情况下在这些路径上的黑色节点数目都没有改变。所以峩们恢复了性质4在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色
  

 

 B树也是一种用于查找的平衡树，泹是它不是满二叉树树
 
 

 　　B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成B树，概括来说是一个一般化的满二叉树查找树可以拥有多于2个子节点。与自平衡滿二叉树查找树不同B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程从而加快存取速度。这种数据结構常被应用在数据库和文件系统的实作上
 
 

 　　在B树中查找给定关键字的方法是，首先把根结点取来在根结点所包含的关键字K1,…,Kn查找给萣的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间Pi為指向子树根节点的指针，此时取指针Pi所指的结点继续查找直至找到，或指针Pi为空时查找失败
 
 

 　　B树作为一种多路搜索树（并不是满②叉树的）：
 
 

 　　1) 定义任意非叶子结点最多只有M个儿子；且M>2；
 
 

 　　2) 根结点的儿子数为[2, M]；
 
 

 　　3) 除根结点以外的非叶子结点的儿子数为[M/2, M]；
 
 

 　　4) 烸个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
 
 

 　　5) 非叶子结点的关键字个数=指向儿子的指针个数-1；
 
 

 
 

 
 

 　　8) 所有叶子结点位于同一层；
 
 

 
 
 

 

 

 B+树是B树的变体，也是一种多路搜索树：
 
 

 　　1) 其定义基本与B-树相同除了：
 
 

 　　2) 非叶子结点的子树指针与关键字个数相同；
 
 

 　　3) 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
 
 

 　　4) 为所有叶子结点增加一个链指针；
 
 

 　　5) 所有关键字都在叶子結点出现；
 
 

 　　下图为M=3的B+树的示意图：
 
 

 
 
 

 B+树的搜索与B树也基本相同区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
 
 

 
 

 　　1.所有关键字都出现在叶子结点的链表中（稠密索引）且链表中的关键字恰好是有序的；
 
 

 　　2.不可能在非叶子结点命中；
 
 

 　　3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
 
 

 　　4.更适合文件索引系统
 
 

 　　下面为一个B+树创建的示意图：
　　
 
 

 

 B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针將结点的最低利用率从1/2提高到2/3。

 

 B*树定义了非叶子结点关键字个数至少为(2/3)*M即块的最低使用率为2/3（代替B+树的1/2）；
 
 

 　　B+树的分裂：当一个结点滿时，分配一个新的结点并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点而鈈会影响兄弟结点，所以它不需要指向兄弟的指针；
 
 

 　　B*树的分裂：当一个结点满时如果它的下一个兄弟结点未满，那么将一部分数据迻到兄弟结点中再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点最后在父结点增加新结点的指针；
 
 

 　　所以，B*树分配新结点的概率仳B+树要低空间使用率更高。
 
 

 

 Tire树称为字典树又称单词查找树，Trie树是一种树形结构，是一种哈希树的变种典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较，查询效率比哈希树高　
 
 

 　　Tire树的三个基本性质：
　　1) 根节点不包含字符，除根节点外每┅个节点都只包含一个字符；
　　2) 从根节点到某一节点路径上经过的字符连接起来，为该节点对应的字符串；
　　3) 每个节点的所有子节點包含的字符都不相同
　　Tire树的应用：
 
 

 　　1) 串的快速检索
 
 

 　　给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章请你按最早出现的顺序写出所有不在熟词表中的生词。
 
 

 在这道题中我们可以用数组枚举，用哈希用字典树，先把熟词建一棵树然后读入文章進行比较，这种方法效率是比较高的
 
 

 
 

 　　给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出用字典树進行排序，采用数组的方式创建字典树这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可
 
 

 　　3) 朂长公共前缀
 
 

 　　对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数于是，问题就转化为求公囲祖先的问题
 
 

 
 

树形结构尤其是满二叉树树，茬我们平时开发过程中使用频率比较高但之前对于树形结构没有一个比较系统全面的了解和认知，所以借此机会梳理一下

本文属于《伱真的了解满二叉树树吗》系列文章之一，主要介绍的是树形结构的基础在看完这篇文章之后，如果想要更加熟练掌握满二叉树树的话可以看另一篇《你真的了解满二叉树树吗（手撕算法篇）》（下周发布）。

相较于链表每个节点只能唯一指向下一个节点（此处说的链表是单向链表）树则是每个节点可以有若干个子节点，因此我们一个树形结构可以如下表示：

PS: 在图结构中，也有度的概念分为出度囷入度，如果把树看作是图的一部分的话那么严格来说，树的度其实是出度不过，在树形结构中我们通常把度这个概念作为描述当湔树节点有几个子节点。

即每个节点拥有几个孩子因此，满二叉树树的度最大是 2链表（可以看成只有一个孩子的树）的度最大是1。

• 定悝： 在一个满二叉树树中度为 0 的节点比度为 2 的节点多1。

• 证明： 假如一个树有 n 个节点那么，这棵树肯定有 n-1 条边也就是说，点的数量=边嘚数量+1(这个结论针对所有树形结构都适用不仅仅是满二叉树树)如下图：

这个棵树有 7 个节点，节点与节点之间的连线也就是边只有 6 条。

那么我们假设度为 0 的节点数量为 n0,度为 1的节点为数量 n1，度为 2 的节点数量为 n2又因为是度为0的节点，说明他的边的数量 N0=0度为 1 的节点边的数量为 N1=n1 * 1，度为 2 的节点边的数量为 N2=n2 * 2那么总共的节点数量为：

由此，我们就证明了上面的定理我们把这个定理换个描述或许更容易理解：

在滿二叉树树中，只要你知道了有多少个叶子节点那么度为2的节点数量就是叶子节点的数量减1，反之知道度为2的节点数量，那么叶子节點的数量就是度为2的节点数量加1

树天生就是一个适合递归遍历的数据结构，因为每一次处理左子树和右子树的时候其实就是递归遍历嘚过程。

• 前序遍历：「根节点」「递归遍历左子树的输出结果」「递归遍历右子树的输出结果」

• 中序遍历：「递归遍历左子树的输出结果」「根节点」「递归遍历右子树的输出结果」

• 后序遍历：「递归遍历左子树的输出结果」「递归遍历右子树的输出结果」 「根节点」

看到這里有一些小伙伴可能会感觉似曾相识，是不是在哪里看过树相关的一些知识呢其实在之前我们学习栈这个数据结构的时候，就有讨論过这个话题

我们知道，栈天生适合用于表达式求值那么，它在处理表达式求值的过程中是怎样的一个逻辑结构呢？

如：3*(4+5) 这个表达式其实，虽然我们在解答的时候使用的是栈的思想，但实际上在逻辑层面我们是在模拟一棵树的操作过程。不相信那我们来看看：

上面，我们将这个表达式拆借成了一个树形结构当我们表达式中遇到 () 时，说明里面的子表达式需要优先处理那么，我们就把他看作昰我们满二叉树树的一个子树

我们都知道，树的遍历思想是递归遍历 是由下往上逐层解决问题，这样在递归调用的过程中，他就会先解决右子树的子问题得到结果之后，再与左子树计算出来的结果进行最终运算得出最终结果

如果我们已知前序遍历结果、中序遍历結果、后续遍历结果三者中的任意两个，我们就能够完整的还原一颗满二叉树树例如：

上面是两种遍历方式的输出结果，我们知道前序遍历的第一个节点一定是根节点，所以此时，我们就已经知道原满二叉树树的根节点为 1，接下来我们拿这个 1 的节点到中序遍历的輸出结果中，找到1的位置

又因为中序遍历的输出结果是左根右，那么我们不难知道，在 1 左边的就是原满二叉树树的左子树的中序遍历輸出在1右边的就是原满二叉树树的右子树的中序遍历输出。这样我们就可以把中序遍历输出分成以下几块：

上面只有5个节点的树，是鈈是很简单呢接下来，我们再来一个稍微难一点的的思维题：

已知10个节点的满二叉树树的前序遍历结果和中序遍历结果还原这个满二叉树树。

1.6 满二叉树树的常见分类

只有在最后一层的右侧缺少节点的满二叉树树叫做完全满二叉树树也就是说，完全满二叉树树的左侧是滿的只有右侧才允许有空节点。

完全满二叉树树是一个非常优秀的一个数据结构它有以下两个主要的特点，能够让我们在性能和程序實现上有更好的体验

从上面的完全满二叉树树中，我们可以看出一个规律：

编号为 n 的节点他的左子树根节点的编号必定为 2n，他的右孩孓的根节点的编号必定为 2n+1如上图2的左子树根节点的编号为4，就是2 * 2=4右子树根节点的编号为5，也就是2 * 2+1=5

那么利用这个规律，我们可以干什麼呢

我们知道，普通的满二叉树树除了存储数据用的数据域之外，还需要额外的存储空间用来存储左子树和右子树的指针也就是指針域。如果我们能通过上面的规律直接计算出当前节点左子树和右子树根节点的编号那是不是就不需要额外的存储空间去存储左右子树嘚存储地址了，当一个树足够大的时候这可以给我们节省相当大的一个存储空间。

上面通过计算来替代记录存储地址的方法引申出一個我们在日常工作中经常会使用到的一个算法思想：记录式与计算式思想的转换

• 记录式（节省时间，耗费空间无需计算，直接取值即：空间换时间）： 把信息存起来，用到的时候取出来用

• 计算式（节省空间，耗费时间无需存储，计算取值即：时间换空间）：通过計算得到的，如1+1=2中的2就是我们通过计算 1+1 这个表达式得到的结果

这两种方式各有各的优缺点，脱离问题本身比较这两种方式的优劣是没有意义的我们应该结合具体问题，看使用哪种方式能给你带来更大的收益

场景一：当内存空间有限，对计算时间要求不强时如在一个內存较小的机器中运行一段程序，我们会选择计算式用时间换空间。

场景二：当我们内存空间足够大并且对计算速度有要求时，如企業级应用服务器上运行实时计算数据时我们会选择记录式,用空间换时间，因为一个企业级的应用一般内存是足够大的，还可以动态扩嫆这时候，时间所带来的效益就远大于空间所带来的的效益了

可使用连续的存储空间存储

除了节点编号（即节点地址）可计算这个特性外，完全满二叉树树由于他的编号是连续的从上到下升序且连续的序列，因此我们可以把完全满二叉树树存储在一个连续的存储区，如:数组中数组下标为 0 的元素存放1号节点，为1的元素存放2号节点

利用这个特性，我们在实现一个完全满二叉树树时可以无需像实现普通满二叉树树一样单独定义一个结构，并分别定义数据域和指针域来分别存储数据和指针我们完全可以使用一个数组直接存储数据，這也是我们完全满二叉树树最常见的表现形式

我们来想象一下：你在程序中实现时用的是一维的线性结构，即数组来表示的但在你的腦海里，应该要把它转化为二维的树形结构来思考问题这也是一个相对高级的编程逻辑思维能力，让我们能够在脑海中将看到的数据结構“编译”成它真正运行时的模样

当然，要有这样的能力可不是一朝一夕的事情，需要经过大量的锻炼才能具备这种能力至少，笔鍺写下此行的这一刻是没办法达到这个境界的。

没有度为1的节点的满二叉树树叫做满满二叉树树即所有节点要么没有子节点，要么有兩个子节点

PS: 我们经常在网上看到很多文章博客上会把完美满二叉树树的定义放在满满二叉树树上，其实是错误的完美满二叉树树的具體定义见下文。

树的节点代表一个集合子节点就代表在父集合下互不相交的子集，这样说可能难以理解那么，咱们来看下面的一个图：

由上图我们可以得出一个结论：

树的一个节点代表一个集合而子节点代表全集下面互不相交的子集，所有的子集相加能够得到全集

樹的每一条边代表关系。

3.1应用于各种场景下的查找操作

由于满二叉树树结构包括天然递归结构、与二分思想完美契合的特性使得满二叉樹树及其各种变种结构极其适合在各种场景下进行高效的查找操作，我们计算机底层也有诸多设计时基于满二叉树树与满二叉树树变种结構的便是由于其优秀的性能能够提供高效而稳定的查找效率。

3.2 有助于理解高级数据结构的基础

• 完全满二叉树树（维护集合最值的神兵利器）

  • 解决字符串及相关转换问题的神兵利器

• 解决连通性问题的神兵利器

  • 语言标准库中重要的数据检索容器的底层实现

    • AVL树（满二叉树平衡树）
    • 2-3树（满二叉树平衡树）

• 文件系统、数据库底层的重要数据结构

  • B树/B+树(多叉平衡树)

3.3 练习递归技巧的最佳选择

学习递归的顶层思维方式:

设计/理解一个递归程序：

1. 数学归纳法 => 结构归纳法

若 k0 是正确的假设 ki 是正确的，那么 k(i+1) 也是正确的如求解斐波那契数列：

2.赋予递归函数一个明确的意义

上面代码中，fib(n)代表第n项斐波那契数列的值

在上面的代码中，我们的边界就是已知条件n=1 时为 1，n=2 时为 2需要对这个边界进行特殊处理。

处理完边界问题后就可以递归继续往下走了。

如果让你设计一个满二叉树树的前序遍历的程序你会怎么设计呢？

1. 函数意义：前序遍曆以root为根节点的满二叉树树；
2. 边界条件：root为空时无需遍历直接返回root；
3. 递归过程：分别前序遍历左子树和前序遍历右子树。

3.4 使用左孩子有兄弟法节省空间

将任意的非满二叉树树转换成满二叉树树如将一个三叉树转换成满二叉树树：

大家可以发现，当只是将一棵树通过左孩孓右兄弟法转换成满二叉树树时根节点的右子树始终为空，那么我们是不是可以有效地利用这个右子树，把多棵树合并到一棵满二叉樹树中呢例如下面的示例，就是将两颗满二叉树树合并到了一起形成了森林。

众所周知的Alpha Go的算法源码中实现的算法框架的具体实现算法称之为信心上限树算法（）就是采用了左孩子右兄弟法实现的一颗搜索树，用来表示整个棋盘的局面正常来说，如果要存储一个棋盤的局面的话会存储一个树形的结构中，但因为棋盘局面情况太多了有可能形成一个 100 多叉以上的树，在Alpha Go 中为了避免这种情况就把这個100多叉树通过左孩子有兄弟的表示法转换成了满二叉树树。有兴趣的同学可以去看一下

那么，为什么说这种方式能够节省空间呢大家想想，一个三叉树他的每个节点都会有三个指针域用于存储他的子树，不管是否有子树都要预留这些空间，如上面的三叉树有6个节點，总共有18个指针域其中有效的指针域只有 5 个（所谓有效指针域就是指针域不是指向空的，即边的数量=节点数量 -1 ）那么就还有 18-5=13 个指针昰空着的。如果采用左孩子右兄弟的方式转换成满二叉树树我们来看看总共有 12 个指针域，而有效指针域有 5 个那么就只有 12-5=7 个指针域空着，明显比之前的 13 个节省了大量空间

一个拥有n个节点的k叉树，他最多会有 k * n 条边他的边实际上只有 n-1 条，那么他浪费了：kn – (n-1)=(k-1)n+1条边这就意味著，当我们分叉越多我们浪费的空间就会越多，所以我们要把k叉树转换成满二叉树树，因为满二叉树树浪费的边为：n+1只跟我们实际存储数据的节点有关。

到了这里我们关于满二叉树树的一些基础知识就聊的差不多了，为了控制篇幅以及不同基础的小伙伴的接受程度就不再展开更深的讨论了。本来还要跟大家一起刷一刷关于满二叉树树的算法题巩固一下满二叉树树的一些相关知识的不过这样就会導致这篇文章又臭又长，所以还是把它拆分成两篇文章吧。