|
|
#2
hzh5122010-05-09 21:55
对二叉树进行层次遍历,在遍历过程中对每一个结点进行检查:
(1)如果当前结点没有右子树,则剩下的全部结点必须既没有左子树,又没有右子树; (2)如果当前结点有右子树,则它必须也有左子树. 如果同时满足(1)(2),则是完全二叉树;否则不是. 你看看你那一条不满足。 程序代码:#include <stdio.h> #include <stdlib.h> #include <conio.h> typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //////////////////////////////////////////////队列定义 typedef struct QNode { BiTree data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; ////////////////////////////////////队列的基本操作 void InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front) exit(0); Q->front->next=NULL; } void DestoryQueue(LinkQueue *Q) { while(Q->front)//******* { Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } } void EnQueue(LinkQueue *Q,BiTNode *e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(0); p->data=e;//说明这个结点的两个域1 p->next=NULL;//2 Q->rear->next=p; Q->rear=p; } void DeQueue(LinkQueue *Q,BiTree *e) { QueuePtr p; if(Q->front==Q->rear) exit(0); p=Q->front->next; *e=p->data; Q->front->next=p->next; // free(p); if(Q->rear==p) Q->rear=Q->front; free(p);// } int QueueEmpty(LinkQueue *Q) { QueuePtr tfront = Q->front; if(Q->front==Q->rear) return(1); else { while (tfront != Q->rear) { if (tfront != NULL) return 0; } return 1; } } /////////////////////////////////////////////////////////////////////////////////////////////////////// BiTree CreatBiTree()//先序建立二叉链表 { TElemType ch; BiTree T; scanf("%c",&ch); if(ch==' ') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(0); T->data=ch; T->lchild=CreatBiTree(); T->rchild=CreatBiTree(); } return T; } //判断是否为完全二叉树 int LayerTraverse(BiTree T)//通过层序遍历改编 { // 对二叉树进行层次遍历,在遍历过程中对每一个结点进行检查: // (1)如果当前结点没有右子树,则剩下的全部结点必须既没有左子树,又没有右子树; // (2)如果当前结点有右子树,则它必须也有左子树. bool flag = true; bool bcomfine = false; LinkQueue queue; InitQueue(&queue); if(T) EnQueue(&queue,T); else { printf("该树为空树!\n"); return true; } while(!QueueEmpty(&queue)) { DeQueue(&queue,&T); if (!T->lchild && T->rchild) return flag=false; if (bcomfine && (T->lchild || T->rchild)) return flag = false; if (T->lchild != NULL) EnQueue(&queue, T->lchild); if (T->rchild != NULL) EnQueue(&queue, T->rchild); else bcomfine = true; } return(flag); } void main() { BiTree t; printf("<------------先序建树--------------->\n"); printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n"); printf("<参考数据:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n"); t=CreatBiTree(); printf("\n"); printf("<------判断是否为完全二叉树操作---->\n"); if(LayerTraverse(t)) printf("该二叉树是完全二叉树!\n"); else printf("该二叉树不是完全二叉树!\n"); } |
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//////////////////////////////////////////////队列定义
typedef struct QNode
{
BiTree data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
////////////////////////////////////队列的基本操作
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front) exit(0);
Q->front->next=NULL;
}
void DestoryQueue(LinkQueue *Q)
{
while(Q->front)//*******
{
Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
}
void EnQueue(LinkQueue *Q,BiTNode *e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(0);
p->data=e;//说明这个结点的两个域1
p->next=NULL;//2
Q->rear->next=p;
Q->rear=p;
}
void DeQueue(LinkQueue *Q,BiTree *e)
{
QueuePtr p;
if(Q->front==Q->rear) exit(0);
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
// free(p);
if(Q->rear==p)
Q->rear=Q->front;
free(p);//
}
int QueueEmpty(LinkQueue *Q)
{
if(Q->front==Q->rear)
return(1);
else
return(0);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
BiTree CreatBiTree()//先序建立二叉链表
{
TElemType ch;
BiTree T;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(0);
T->data=ch;
T->lchild=CreatBiTree();
T->rchild=CreatBiTree();
}
return T;
}
//判断是否为完全二叉树
int LayerTraverse(BiTree T)//通过层序遍历改编
{
int flag=1;//默认其为完全二叉树
LinkQueue queue;
InitQueue(&queue);
if(T)
EnQueue(&queue,T);
else
{
printf("该树为空树!\n");
exit(0);
}
while(!QueueEmpty(&queue))
{
DeQueue(&queue,&T);
if((T==NULL)&&(!QueueEmpty(&queue)))//出队列元素是空指针且此时队列不为空,则可以判断该树不为完全二叉树,返回假值
{
flag=0;
break;
}
if(T->lchild||T->rchild)//T->rchild
break;
else//有一个不为空就进队列
{
EnQueue(&queue,T->lchild);//左子树进队列
EnQueue(&queue,T->rchild);//右子树进队列
}
}
return(flag);
}
void main()
{
BiTree t;
printf("<------------先序建树--------------->\n");
printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n");
printf("<参考数据:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n");
t=CreatBiTree();
printf("\n");
printf("<------判断是否为完全二叉树操作---->\n");
if(LayerTraverse(t))
printf("该二叉树是完全二叉树!\n");
else
printf("该二叉树不是完全二叉树!\n");
}
程序代码: