Question

完全二叉树的定义

Answer 1

完全二叉树的定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

如图a）所示是一棵完全二叉树，图b）由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n个结点的完全二叉树的深度为⌊log2n⌋+1。⌊log2n⌋表示取小于log2n的最大整数。例如，⌊log24⌋=2，而⌊log25⌋结果也是2。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图a）），对于任意一个结点i，完全二叉树还有以下几个结论成立：

1、当i>1时，父亲结点为结点[i/2]（i=1时，表示的是根结点，无父亲结点）。

2、如果2*i>n（总结点的个数） ，则结点i肯定没有左孩子（为叶子结点）；否则其左孩子是结点2*i 。

3、如果2*i+1>n，则结点i肯定没有右孩子；否则右孩子是结点2*i+1。

完全二叉树的应用

完全二叉树的好处在于使用完全二叉树，我们可以直击在不修改数组形态的状态下，直接将一个数组映射成一棵树，然后通过这棵树对数组操作，同时很多其他结构的树也都要求这棵树是完全二叉树，如堆就要求堆是一棵完全二叉树。