编程判断一个树是完全二叉树（使用层次遍历实现）
来源：程序员人生 发布时间：2014-09-29 16:43:59 阅读次数：3929次
完全二叉树：一棵具有N个节点的二叉树的结构与满二叉树的前N个节点的结构相同
如何判断一个树是完全二叉树
可以使用层序遍历，只需2个步骤
第一步：如果遍历到一个节点只有右子树没有左子树，则不是完全二叉树
第二部：如果遍历到一个节点只有左子树，那么后面遍历到的节点必须是叶子节点，否则也不是完全二叉树
排除以上两种情况，则树是完全二叉树
核心代码：
//层序遍历
int LayerOrder(BiTreeNode *head)
{
bool flag=0;
LQueue Q;
Initiate_Queue(&Q);
BiTreeNode *p;
if(head!=NULL) AppendQueue(&Q,head);
while(QueueNotEmpty(&Q))
{
if(flag)
{
if(p->LChild!=NULL || p->RChild!=NULL)
return 0;
}
p=QueueDelete(&Q);
if(p->LChild!=NULL) AppendQueue(&Q,p->LChild);
if(p->RChild!=NULL) AppendQueue(&Q,p->RChild);
if((p->LChild==NULL) && (p->RChild!=NULL)) return 0; //如果左子树为空，右子树存在，则不是完全2叉树
//如果左子树存在，右子树为空，设置flag为1，进行进一步判断，判断后面遍历的节点是否为叶子节点
if(p->LChild!=NULL &&p->RChild==NULL) flag=1;
//如果左子树，右子树都为空，设置flag为1，进行进一步判断，判断后面遍历的节点是否为叶子节点
if(p->LChild==NULL && p->RChild==NULL) flag=1;
}
return 1;
}
完整代码如下：
#include<iostream>
using namespace std;
typedef struct biTreeNode
{
char data;
struct biTreeNode *LChild;
struct biTreeNode *RChild;
}BiTreeNode;
void Initiate_Tree(BiTreeNode **head)
{
(*head)=(BiTreeNode *)malloc(sizeof(BiTreeNode));
(*head)->LChild=NULL;
(*head)->RChild=NULL;
}
BiTreeNode *InsertLChild(BiTreeNode *head,char x)
{
if(head==NULL) return NULL;
else
{
BiTreeNode *p1,*p2;
p1=head->LChild;
p2=(BiTreeNode*)malloc(sizeof(BiTreeNode));
p2->data=x;
p2->RChild=NULL;
head->LChild=p2;
p2->LChild=p1;
return p2;
}
}
BiTreeNode* InsertRChild(BiTreeNode *head,char x)
{
if(head==NULL) return NULL;
{
BiTreeNode *p1,*p2;
p1=head->RChild;
p2=(BiTreeNode*)malloc(sizeof(BiTreeNode));
p2->data=x;
p2->LChild=NULL;
head->RChild=p2;
p2->RChild=p1;
return p2;
}
}
void DLR(BiTreeNode *head)
{
if(head==NULL) return;
else
{
cout<<head->data<<" ";
DLR(head->LChild);
DLR(head->RChild);
}
}
//==================================================
typedef struct lNode
{
BiTreeNode *data;
struct lNode *next;
}LNode;
typedef struct lQueue
{
LNode *front;
LNode *rear;
}LQueue;
void Initiate_Queue(LQueue *Q)
{
Q->front=NULL;
Q->rear=NULL;
}
void AppendQueue(LQueue *Q,BiTreeNode *head)
{
LNode *p1;
p1=(LNode *)malloc(sizeof(LNode));
p1->next=NULL;
p1->data=head;
if(Q->front==NULL)
{
Q->front=Q->rear=p1;
}
else
{
Q->rear->next=p1;
Q->rear=p1;
}
}
BiTreeNode * QueueDelete(LQueue *Q)
{
if(Q->front==NULL) return NULL;
else
{
BiTreeNode *p;
p=Q->front->data;
Q->front=Q->front->next;
return p;
}
}
int QueueNotEmpty(LQueue *Q)
{
if(Q->front==NULL) return 0;
else return 1;
}
//层序遍历
int LayerOrder(BiTreeNode *head)
{
bool flag=0;
LQueue Q;
Initiate_Queue(&Q);
BiTreeNode *p;
if(head!=NULL) AppendQueue(&Q,head);
while(QueueNotEmpty(&Q))
{
if(flag)
{
if(p->LChild!=NULL || p->RChild!=NULL)
return 0;
}
p=QueueDelete(&Q);
if(p->LChild!=NULL) AppendQueue(&Q,p->LChild);
if(p->RChild!=NULL) AppendQueue(&Q,p->RChild);
if((p->LChild==NULL) && (p->RChild!=NULL)) return 0; //如果左子树为空，右子树存在，则不是完全2叉树
//如果左子树存在，右子树为空，设置flag为1，进行进一步判断，判断后面遍历的节点是否为叶子节点
if(p->LChild!=NULL &&p->RChild==NULL) flag=1;
//如果左子树，右子树都为空，设置flag为1，进行进一步判断，判断后面遍历的节点是否为叶子节点
if(p->LChild==NULL && p->RChild==NULL) flag=1;
}
return 1;
}
void main()
{
BiTreeNode *head,*p,*p1;
int flag;
Initiate_Tree(&head);
head->data='j';
p=InsertLChild(head,'k');
p=InsertLChild(p,'a');
InsertRChild(head,'b');
cout<<"前序遍历为："<<endl;
DLR(head);
cout<<endl;
flag=LayerOrder(head);
if(flag)
cout<<"是二叉树"<<endl;
else
cout<<"不是二叉树"<<endl;
system("pause");
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
