二叉树公式及详解。

基本名词概念

二叉树：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的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 

其实就是很标准的二叉树，就是有残缺，可以理解为满二叉树的阉割版。

完全二叉树有哪些性质呢？

              n0 = n2 + 1;    ① 这条可以 点这里，也可以 点这里。

              n = n0 + n1 + n2;   ② 这条很好理解，个类度的节点加起来不就是总节点呢嘛。

             分支总线 = n - 1 = n1 + 2n2;   ③ 这条根据①②就能推出来。

             如果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代码实现：