满二叉树必为完全二叉树

二叉树（Binary Tree）是由一组称为节点（Node）的元素以及这些元素间的一组二元关系所构成的树状结构。其中，每个节点最多有两个子节点。如果一个树的每个节点都满足最多有两个子节点，就称其为二叉树。

满二叉树是指一棵深度为h且每个节点都有两个子节点的二叉树。可以用递归定义来构建一棵满二叉树：以根节点为起点，构建左子树和右子树，并保证它们都是深度为h-1的满二叉树。

完全二叉树是指一棵深度为h的，包含有n个节点的二叉树，当且仅当其每个节点都与深度为h-1的满二叉树中编号为1~n的节点一一对应。也就是说，除了最后一层外，所有层的节点数都达到最大值，最后一层的节点都靠左排列。

那么，为什么满二叉树必为完全二叉树呢？下面从多个角度进行分析。

1. 从节点数量分析

考虑一棵深度为h的满二叉树，它的节点数是多少？可以用数学归纳法来证明，对于深度为h的满二叉树，其节点数为2^h-1。其中，当h=1时，节点数为1；假设当h=k时，节点数为2^k-1；则当h=k+1时，节点数为2^(k+1)-1=2^k-1+2^k+1。这里的2^k-1对应于上一层的节点数，2^k+1对应于新加的这层节点数。可以发现，只有最后一层可能不满，但是其他层的节点数都是最大值，因此满二叉树必为完全二叉树。

2. 从层次结构分析

因为满二叉树的每个节点都有两个子节点，所以如果每个节点都有两个子节点，那么该二叉树一定是满二叉树。否则，假设最后一层的叶子节点只有一个，那么它的父节点就只有一个子节点，这就破坏了满二叉树的定义。因此，如果最后一层有节点缺失，只可能缺失最右边的节点，其他节点都是满的。这样，仍然可以满足完全二叉树的定义。

3. 从二叉树的编号分析

对于深度为h的完全二叉树，它的编号是从1到2^h-1的。将它表示在一棵满二叉树上，可以发现，满二叉树上的每个节点都可以通过完全二叉树上的节点编号得到。

具体而言，将完全二叉树上的编号按层次结构排列，同一层按从左到右的顺序排列，得到一个从1开始的序列s。则深度为h的满二叉树上，从根节点开始，每当遇到1时，就往左走；每当遇到0时，就往右走。这样，就可以按照完全二叉树的编号，得到对应的满二叉树上的节点。

因为深度为h的完全二叉树的节点数为2^h-1，而深度为h的满二叉树的节点数也为2^h-1，两者的节点数是相同的，因此满二叉树必为完全二叉树。

综上所述，从节点数量、层次结构和二叉树的编号三个角度分析，满二叉树必为完全二叉树。

文章