各位帮我看看这道“判断二叉树是否是完全二叉树”,我自己照别人算法写的 ,哪位大侠能帮我改改,然后告诉一下怎么测试
要求:
(1)用二叉链表作存储结构,写出相应的算法。
(2)要求从键盘上录入相应的二叉树的结点。
(3)利用完全二叉树的性质及树的层次遍历实现该算法,并在屏幕上输出相应的判定结果。
急用 课程设计就剩一个星期了,快点哦
#include "stdafx.h"
#include "stdlib.h"
typedef int Status;
typedef int QElemType;
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define MAX_TREE_DEGREE 10
typedef struct BTnode{//以二叉链表作为存储结构
char data;
struct BTnode* lchild;
struct BTnode* rchild;
}BTnode,*BTree;
Status CreateBiTree(BTree &T)
{ /* 按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),*/
/* 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。*/
char ch;
scanf("%c",&ch);
if(ch==' ') /* 空 */
T=NULL;
else{
if(!(T=(BTnode *)malloc(sizeof(BTnode)))) /* 生成根结点 */
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild); /* 构造左子树 */
CreateBiTree(T->rchild);/* 构造右子树 */
}
return OK;
}
/*单链队列--队列的链式存储结构 */
typedef struct QNode
{
BTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
int initqueue(LinkQueue Q)//队列初始化
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit (OVERFLOW);
Q.front->next=NULL;
return OK;
}
Status enqueue(LinkQueue Q,BTree e)//入队
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status dequeue(LinkQueue Q,BTree e)//出队
{
if(Q.front==Q.rear)
return ERROR;
QueuePtr p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
Status queueempty(LinkQueue Q)//判断队列是不是空的
{
if(Q.front==Q.rear)
return ERROR;
else
return OK;
}
Status iscompletetree(BTree T)//判断是否是完全二叉树、
{
LinkQueue Q;
BTree p;
p=T;
if(!T)
return 0;
enqueue(Q,p);
while(queueempty(Q))
{ dequeue(Q,p);
if(p)
{
enqueue(Q,p->lchild);
enqueue(Q,p->rchild);
}
if(!p)
{
while(queueempty(Q))
{
dequeue(Q,p->rchild);
if(p)
{
printf("不是完全二叉树");
return ERROR;
}
}
}
}
return OK;
}
int main(void)//简单测试
{
BTree root;
CreateBiTree(root);
iscompletetree(root);
return ERROR;
}