判断一棵二叉树是否为完全二叉树:
(方法一:采用层次遍历法,将二叉树各结点对应编号放到数组对
应单元中,即若结点标号为 i,则左孩子为 2i,右孩子为 2i+1。由于
二叉链表的建立是对非零元素为结点进行的,故放入数组中,若为
完全二叉树,则从数组第一个单元到结点最后一个单元<建立二叉链
表时计算结点的总个数已知道最后一个单元的位置>中应该没有零元
素,否则只要存在零元素,则不是完全二叉树。完整程序为 aa.c)
#include "stdio.h"
#include "stdlib.h"
int sum=0;
int a[100];
struct btnode
{ int d;
struct btnode *lchild;
struct btnode *rchild;
};
struct btnode *creatbt(struct btnode *bt,int k)/*建立二叉链表*/
{ int b;
struct btnode *p,*t;
printf("input b:");
scanf("%d",&b);
if (b!=0)
{ sum++; /*计算结点的总个数*/
p=(struct btnode *)malloc(sizeof(struct btnode));
p->d=b; p->lchild=NULL; p->rchild=NULL;
if (k==0) t=p;
if (k==1) bt->lchild=p;
if (k==2) bt->rchild=p;
creatbt(p,1);
creatbt(p,2);
}
return(t);
}