编程判断一个树是完全二叉树（使用层次遍历实现）

//层序遍历 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"); }