开学已经倒计时，二叉树的推论还不会证明？快坐上这辆快车！

匆匆，原以为只是一次普通的过年回家，没想到变成了寒假连暑假。时间线推移，来到了八月底，很多同学已经摩拳擦掌准备开学了，然而也有同学对即将到来的线下考试惴惴不安。

多说无益，先把文章看完。

在学习数据结构的过程中，二叉树是我们绕不开的一个坎儿。关于二叉树的重要性呢，我们并不在本文中赘述，本文想要阐述的是二叉树的三个推论和两个定理。

具有n个结点的二叉树可能的形态数为C（2n，n）/（n+1）。

当n等于0，也就是空树的情形，公式成立。接着我们可以再来想一个简单的例子：比如说一个具有三个结点的二叉树，我们用穷举的方式考虑。

可能的情形有：全部倾斜向左，全部倾斜向右，根和两个孩子，根左右，根右左。总共是5种情形，代入我们的公式，没有问题。

其实在这里有个小彩蛋，看到这个公式应该是可以联想起来一些东西的。n个元素顺序入栈，所有可能的出栈序列情况数量也是这个公式。

完全二叉树中1度结点（只有一个孩子的结点）不是0个就是1个。

具有n个结点的二叉树，如果用二叉链表来存储，其二叉链表汇总空指针域的个数为n+1个。

接着我们看两个很相似的定理，很简单。

n(n>=0)个结点的二叉树，可以由它的中序序列和先序序列唯一确定。

n(n>=0)个结点的二叉树，可以由它的中序序列和后序序列唯一确定。

其实，言外之意就是说，有先序序列和后序序列是不能唯一确定一个二叉树的、当然，如果只有一种序列也无法唯一确定一个二叉树。

那么关于这两个定理怎么证明呢？这个曾经是一道考研题，证明的方法是采用数学归纳法，证明思路也并不复杂，同学们可以一起来领略一下。

证明：中序序列和先序序列可以唯一确定一棵二叉树。

当n为0的时候，可以确定，二叉树是一棵空树，结论正确。假设节点数小于n的任何二叉树都可以根据中序序列和先序序列唯一确定。所以只要可以证明对于n个结点的二叉树，也可以根据中序序列和先序序列唯一确定，就可以完事了。

对于这一棵包含n个结点的二叉树，可以假设这课二叉树的先序序列是a0 a1 a2 a3……a(n-1)，它的中序序列为b0 b(k-1) bk b(k+1)……b(n-1)。

因为在先序遍历中，二叉树访问顺序是根左右，先访问根节点，所以a0就一定是整个二叉树的根，而且a0也一定会在中序序列中出现，假设它在中序序列中出现的位置bk就是a0。

所以，在中序序列中，k号结点之前的b0到b(k-1)就是根的左子树的中序序列，而k号结点之后的b(k+1)到bn就是根的右子树的中序序列。

与之对应的，在先序序列中，紧跟在a0之后的k个结点a1到ak就一定是左子树的先序序列，其余的a(k+1)到a（n-1）就一定是右子树的先序序列。

结合假设2，结点数少于n的二叉树可以由中序序列和先序序列唯一确定，所以我们谈及的左子树和右子树可以分别根据它们的先序序列和中序序列唯一确定。

综上所述，这棵二叉树的左右子树可以被唯一确定，所以整个二叉树也就可以被唯一确定了。

开学之际，分不清兴奋还是紧张；

各在一方，皆是为梦奔忙；

负重前行，我已学会眼里带光。

感谢阅读，学习使人强大。