Question

怎么判断一个二叉树是否是完全二叉树

Answer 1

完全二叉树(complete
binarytree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1）
满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2）
在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3）
在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
利用特点进行判断

Answer 2

给你讲讲方法吧，实现就自己写了。
完全二叉树(Complete
Binary
Tree)：
若设二叉树的高度为h，除第
h
层外，其它各层
(1～h-1)
的结点数都达到最大个数，第
h
层所有的节点都连续集中在最左边，这就是完全二叉树。
判断很简单，广度优先搜索整个二叉树，一旦找一个不含有子节点或者只含有一个左子节点之后，那么后续的所有节点都必须是叶子节点。否则，该树就不是完全二叉树。
实现的时候要用到队列。

Answer 3

现在只说下原理，明天再编出来：
树的深度为K，则完全二叉树的小于k-1的层中，节点全部存在，并且，在第K层中（最后一层），到最右节点，没有存在空位置

#include

//完全二叉树
// 0
// / \
// 1 2
// / \ /
// 3 4 5

class Node
{
};

int main()
{
Node n[10];
//将节点按上面表示的顺序一个个放入数组中
//当然，这里依靠这个顺序的话，也可以用程序编出来
//假设放入了len个节点 len=5
int len=5;

//这因该是数学中的log..但我不知道怎么用..就实际代替了一下
//5比2的2次方，比2的3次方又小，所以得到二叉树深度为3,(即有三层)
int k=3;

//查找有无空的节点
for(int i=0;i<2*(k-1)-1;i++) //父节点层
{//判断出是否n[i]为空}
for(int i=2*k-1)-1;i<len;i++) //同等层
{//同上}
//在上面找到空的节点就说明不是完全二叉树
}
是模块化了的伪码，其中的细节只能依靠自己了

Answer 4