王道p149 7.二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法（c语言代码实现）

采用层次遍历算法，将所有结点加入队列(包括空结点)。

如果没有左孩子，就看有没有右孩子，如果有右孩子，那么不为完全二叉树。

如果有左孩子，且之前不存在缺孩子的结点，左孩子进队，如果有右孩子，右孩子也进队，否则就是缺孩子了。之前存在缺孩子的，那么就不是完全二叉树。

有两种代码的写法

本题代码如下

int isok(tree* t)//判断完全二叉树
{squene q;q.f = q.r = q.tag = 0;int flag = false; // 标志是否遇到了空节点if (*t == NULL)return true; // 空树也是完全二叉树enquene(&q, *t);treenode* p;while (!isempty(&q)){dequene(&q, &p);if (p->lchild){if (flag) // 如果之前遇到了空节点，说明不是完全二叉树return false;enquene(&q, p->lchild);}else{flag = true;}if (p->rchild){if (flag) // 如果之前遇到了空节点，说明不是完全二叉树return false;enquene(&q, p->rchild);}else{flag = true;}}return true;
}

完整测试代码

#include <stdio.h>
#include <stdlib.h>
#define Max 15
#define true 1
#define false 0
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
} treenode, * tree;
void buildtree(tree* t)
{char ch;ch = getchar();if (ch == '#')*t = NULL;else{*t = (treenode*)malloc(sizeof(treenode));(*t)->data = ch;buildtree(&(*t)->lchild);buildtree(&(*t)->rchild);}
}
typedef struct squene
{struct treenode* data[Max];int f, r, tag;
} squene;
int isempty(squene* q)//判断队空
{if (q->f == q->r && q->tag == 0)return true;return false;
}
int isfull(squene* q)//判断队满
{if (q->f == q->r && q->tag == 1)return true;return false;
}
int enquene(squene* q, treenode* p)//进队操作
{if (isfull(q))return false;q->data[q->r] = p;q->r = (q->r + 1) % Max;q->tag = 1;return true;
}
int dequene(squene* q, treenode** p)//出队操作
{if (isempty(q))return false;*p = q->data[q->f];q->f = (q->f + 1) % Max;q->tag = 0;return true;
}
int isok(tree* t)//判断完全二叉树
{squene q;q.f = q.r = q.tag = 0;int flag = false; // 标志是否遇到了空节点if (*t == NULL)return true; // 空树也是完全二叉树enquene(&q, *t);treenode* p;while (!isempty(&q)){dequene(&q, &p);if (p->lchild){if (flag) // 如果之前遇到了空节点，说明不是完全二叉树return false;enquene(&q, p->lchild);}else{flag = true;}if (p->rchild){if (flag) // 如果之前遇到了空节点，说明不是完全二叉树return false;enquene(&q, p->rchild);}else{flag = true;}}return true;
}
int main()
{treenode* t;buildtree(&t);if (isok(&t))printf("yes");elseprintf("no");return 0;
}

用ABD##E##CF##G##测试

/* A

B C

D E F G

用ABD###CF##G##测试

/* A

B C

D F G

还可以用另外一种写法

#include <stdio.h>
#include <stdlib.h>
#define Max 15
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
} treenode, * tree;
void buildtree(tree* t)
{char ch;ch = getchar();if (ch == '#')*t = NULL;else{*t = (treenode*)malloc(sizeof(treenode));(*t)->data = ch;(*t)->lchild = NULL;(*t)->rchild = NULL;buildtree(&(*t)->lchild);buildtree(&(*t)->rchild);}
}int isok(tree* t)//判断完全二叉树
{treenode* q[Max];int f = -1, r = -1;int tag = 1;//标记是否为完全二叉树q[++r] = *t;treenode* p;int flag = 1;//标记缺孩子if (*t == NULL) {tag = 1;}if (!(*t)->lchild && !(*t)->rchild)tag = 1;while (f < r) {p = q[++f];if (!p->lchild) //没有左孩子缺孩子{flag = 0;if (p->rchild)tag = 0;}else//有左孩子{if (flag)//之前不存在缺孩子的结点{q[++r] = p->lchild;if (p->rchild)q[++r] = p->rchild;elseflag = 0;}else//之前存在缺孩子的结点tag = 0;}}if (tag)return 1;return 0;
}
int main()
{treenode* t;buildtree(&t);if (isok(&t))printf("yes");elseprintf("no");return 0;
}

用ABD##E##CF##G##

/* A

B C

D E F G

测试结果为