編程判斷一個樹是完全二叉樹（使用層次遍歷實現）
來源：程序員人生 發布時間：2014-09-29 16:43:59 閱讀次數：4135次
完全二叉樹：一棵具有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");
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
