zzz.cpp

编写算法判定给定二叉树是否为完全二叉树

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#include <string.h>
typedef char TElemType;
#define STACK_INIT_SIZE 100 
#define STACKINCREMENT 10 
#define MAXQSIZE  20 
#define OK 1
#define ERROR 0
typedef struct BiTNode
{ 
	TElemType data;
    struct BiTNode  *lchild,*rchild;  
 } BiTNode , *BiTree; 
void CreateBiTree(BiTree &T)
{   
	char ch;
	printf("请输入二叉树的结点：");
	scanf("%c",&ch);
	getchar();                               
    if (ch=='#') 
		T=NULL;            
    else 
	{ 
		if (T=(BiTNode *)malloc(sizeof(BiTNode)))
		{                 
               T->data = ch;                     
               CreateBiTree(T->lchild); 
               CreateBiTree(T->rchild); 
		}
		else exit(0); 
     }

 }
typedef struct {
    BiTNode  *base;  
    int  front;     
    int  rear;      
} SqQueue;
void InitQueue(SqQueue &Q)
{
	Q.base = (BiTNode*)malloc(MAXQSIZE *sizeof(BiTNode));
    if (!Q.base) exit (1);  
    Q.front = Q.rear = 0;
}
void EnQueue(SqQueue &Q,BiTNode *p)
{
	if ((Q.rear+1) % MAXQSIZE == Q.front) 
        exit(1); 
    Q.base[Q.rear] = *p;
    Q.rear = (Q.rear+1) % MAXQSIZE;
}
void DeQueue(SqQueue &Q,BiTNode *p)
{
   if (Q.front == Q.rear)  
	   exit(0);
   *p = Q.base[Q.front];
   Q.front = (Q.front+1) % MAXQSIZE;

}

int QueueEmpty(SqQueue Q)
{   

     if(Q.front == Q.rear)
		return OK;
     return ERROR;
}

int visit(TElemType e)
{
     printf("%c",e);
     return 1;
} 

void IsFullBitree(BiTree T)
{
	SqQueue Q;
	BiTree p;
	p = T;
	InitQueue(Q);
	int shu =1,m=1;
	EnQueue(Q,T);
	while(!QueueEmpty(Q))
	{
		DeQueue(Q,p);
		if(!p->lchild)
		{
			m=0;
			if(p->rchild)
				shu=0;
		}
		else
		{
			shu=m;
			if(!p->rchild)
				m=0;
			else
			{
				EnQueue(Q,p->lchild);
				EnQueue(Q,p->rchild);
			}
		}
	}
	if(shu)	
		printf("这是一个完全二叉树！");
	else	
		printf("这不是一个完全二叉树！！");

}
void main()
{
	BiTree T;
	CreateBiTree(T);
	printf("\n");
	IsFullBitree(T);
	printf("\n");
	
		
}