⼆叉树公式及详解。
基本名词概念
n个有限元素的集合，该集合或者为空、或者由⼀个称为根（root）的元素及两个不相交的、被分别称为左⼦树和右⼦树的⼆叉树组成，是有序树。当集合为控时，称该⼆叉树为空⼆叉树。在⼆叉树中，⼀个元素也称为⼀个节点。（这段官话）
简单理解就是⼆叉树还是树，但是节点最多⼆个分叉。
树的度：⼀个节点有m个分叉，那么这个节点的度就为m。叶⼦节点的度为0，因为它没有分叉。
⼆叉树节点的度只有0，1，2这三种，其中为0的肯定是叶⼦节点。
⼆叉树的⾼度（深度）：max(左⼦树深度，右⼦树深度)+1。
⼆叉树节点的分类：主要就三种，不谈那些孩⼦，兄弟，祖先，⼦孙啥的。
根节点
  叶⼦节点 ：度为0
  分⽀节点 ：度不为0的节点。
⼆叉树的分类：
1. 满⼆叉树：⼀棵深度为k且有个节点的⼆叉树称为满⼆叉树。
其实就是除了叶⼦节点，每个节点都有两个分叉（两个度，两个孩⼦）。如下图深度为4（根算1，按1来算，有些根不算深度，⽐较扯），节点总数2的4次⽅减1为15个。
2. 完全⼆叉树：⼀棵深度为k的有n个结点的，对树中的结点按从上⾄下、从左到右的顺序进⾏编号，如果编号为i（1≤i≤n）的结点与中编号为i的结点在⼆叉树中的位置相同，则这棵⼆叉树称为完全⼆叉树。
其实就是很标准的⼆叉树，就是有残缺，可以理解为满⼆叉树的阉割版。
完全⼆叉树有哪些性质呢？
在⼆叉树上的第i层上之多有个节点（i>=1) ：看上图就知道了，最多也就是满的意思呢嘛。
深度为k的⼆叉树⾄多有个节点（k >= 1) : 这个也很好理解，和上⾯⼀条性质基本⼀样的意思，只不过上⼀个只是求⼀层的节点树，⽽本条性质是求所有节点。
⽐较重要的⼀条性质：n0、n1、n2分别代表节点的度数为0、1、2。n为总结点数，则有：
n0 = n2 + 1;    ① 这条可以 ，也可以 。
n = n0 + n1 + n2;  ② 这条很好理解，个类度的节点加起来不就是总节点呢嘛。
分⽀总线 = n - 1 = n1 + 2n2;  ③ 这条根据①②就能推出来。
具有n个节点的完全⼆叉树的深度为 ，也就是深度公式其实就是以2为底N的对数下取整（下取整是指⽐如9.2点，上取整就是10，下取整就是9了），然后再+1就是深度了。
二叉树公式如果对⼀棵有n个节点的完全⼆叉树的节点按层序编号，则对任意节点 i ( 1 <= i <=n ) 有：
如果i=1, 则结点i是⼆叉树的根, ⽆双亲；如果i>1, 则其双亲parent (i) 是结点（i/2)下取整.
如果2i>n, 则结点i⽆左孩⼦, 否则其左孩⼦lchild (i) 是结点2i;
如果2i+1>n, 则结点i⽆右孩⼦, 否则其右孩⼦rchild (i) 是结点2i+1.
以上三个“如果”，可以对⽐下图验证：
3. 平衡⼆叉树：⼜被称为AVL树，且具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。
其实就是每个节点下挂着的的左右⼦树可以不⼀样长，但是不⼀样长的长度差不能超过1.
4. 234树什么的，这⾥有篇博客写的很好，
5. 红⿊树什么的，这⾥提供⼀个在线画红⿊树的⽹址，可以观察其变化，。
当然也可以去B站看234树向红⿊树演变的相关视频，左旋右旋什么的代码部分混，确实有点头⼤。
⼆叉树相关⾯试题关键性公式：
n0、n1、n2分别代表节点的度数为0、1、2。n为总结点数
1.  只要是树，就都满⾜ 节点个数n = 所有节点的度之和 + 1。
2.  包括⼆叉树，节点和度关系满⾜  n = n0 + n1 + n2 = n1 + 2n2 + 1。
3.  根据上⼀条，很容易得到 n0 = n2 + 1。
4.  具有n个节点的完全⼆叉树的深度为 也就是深度公式其实就是以2为底N的对数下取整（下取整是指⽐如9.2点，上取整就是10，下取整就是9了），然后再+1就是深度了（上⾯已经写过）。
上⾯四个公式基本就够⽤了，上例题1：
例题2：
例题3：
5. 还有⼀个公式⽐较关键，按照⼆叉树的定义，n个节点的⼆叉树共有多少种？                    这是⼀个，咱也不懂，瑟瑟发抖。或者直接套公式：
⼆叉树的遍历：
前序：根结点第⼀个访问，然后访问左、右孩⼦；
后序：根结点最后访问，开始先访问左、右孩⼦；
中序：根结点第⼆个访问，最先访问左孩⼦，最后访问右孩⼦。
如这样⼀棵树：
前序序列结果：0134256
后序序列结果：3415620
中序序列结果：3140526
前序遍历java代码实现：
⼿打中。。。持续更新
中序遍历java代码实现：
⼿打中。。。持续更新
后序遍历java代码实现：
⼿打中。。。持续更新
内容并不完善，后期还会增加修改！
内容如果有错误的地⽅，欢迎各位朋友批评指针，万分感谢！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。