判断完全二叉树

什么是完全二叉树？

对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

特点：所有的叶结点都出现在第k层或k-1层（层次最大的两层）。

对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1。

void LevelOrder(BiTree T)
{
	BiTree Q[MAXSIZE];
  BiTree p;
  int front,rear;
  front=rear=0;
  if(T==NULL)
    return 0;
  printf("%c",T->data);
  rear++;
  Q[rear]=T;
  while(rear!=front)
  {
    front=(front+1)%MAXSIZE;
    p=Q[front];
    if(p->lchild!=NULL)
    {
      printf("%c",p->lchild->data);
      rear=(rear+1)%MAXSIZE;
      Q[rear]=p->lchild;
    }
    if(p->rchild!=NULL)
    {
      printf("%c",p->rchild->data);
      rear=(rear+1)%MAXSIZE;
      Q[rear]=p->rchild;
    }
  }
}

如何判断层次遍历进行到了第几层？引入层次指针。

void fun2(BiTree T){
  BiTree Q[MAXSIZE],p;
  int front,rear,layer,count,n;

  //layer层指针，count每层个数计数，n层次计数
  front=rear=layer=count=0;
  if(!T) return;
  printf("%c",T->data);
  printf("layer-%d:%d\n",1,1);  
  rear++;
  Q[rear]=T;
  layer++;
  n=1;
  while(rear!=front){
    front=(front+1)%MAXSIZE;
    p=Q[front];
    if(p->lchild!=NULL){
      printf("%c",p->lchild->data);
      rear=(rear+1)%MAXSIZE;
      Q[rear]=p->lchild;
	  count++;
    }
    if(p->rchild!=NULL){
      printf("%c",p->rchild->data);
      rear=(rear+1)%MAXSIZE;
      Q[rear]=p->rchild;
	  count++;
    }
	/*若没有front!=rear会多统计一个空层*/
	if(front==layer&&front!=rear){
		n++;
		printf("layer-%d:%d\n",n,count);
		layer=rear;
		count=0;
	}
  }
  putchar('\n');
}

判断是否为完全二叉树

对于完全二叉树，在层次遍历过程中，若某结点缺失了左孩子或右孩子，则其后继一定无孩子。 

int fun(BiTree T)
{
	BiTree Q[MAXSIZE];
  BiTree p;
  int front,rear;
  front=rear=0;
  int flag=1;//标志到目前为止未发现缺失孩子的结点
  if(T==NULL)
    return 0;
  printf("%c",T->data);
  rear++;
  Q[rear]=T;
  while(rear!=front)
  {
    front=(front+1)%MAXSIZE;
    p=Q[front];
    if(p->lchild!=NULL)
    {
      printf("%c",p->lchild->data);
      rear=(rear+1)%MAXSIZE;
      Q[rear]=p->lchild;
    }
    else
      flag=0;
    if(p->rchild!=NULL)
    {
      printf("%c",p->rchild->data);
      rear=(rear+1)%MAXSIZE;
      Q[rear]=p->rchild;
    }
    else
      flag=0;
  }
  return 1;
}