Question

怎么判断是否是完全二叉树 用C++或C语言

Answer 1

你可以上网先找一个用队列实现二叉树的广度优先搜索的代码，然后在代码中增加一个标志变量tag，初始化为0。然后找到代码中访问结点的那句代码，在那句代码处增加
if(tag==0)
判断该结点是否有两个孩子，如果没有两个孩子，则将tag=1
else
判断该结点是否为叶结点，如果不是叶结点，则不是完全二叉树。

Answer 2

广度优先搜索整个二叉树，一旦找一个节点只不含有子节点或者子含有一个左子节点，那么后续的所有节点都必须是叶子节点。否则，该树就不是完全二叉树。

实现的时候需要用到队列。

下面是程序：

#include <stdlib.h>
#include <stdio.h>
class TreeNode{
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int v) : value(v) {
left = NULL;
right = NULL;
}
~TreeNode() {
if (left != NULL) {
delete left;
left = NULL;
}
if (right != NULL) {
delete right;
right = NULL;
}
}
};

struct QueueNode {
TreeNode *data;
QueueNode *next;
};

//用链表的方式实现队列
class Queue {
private:
QueueNode *head; //队列的投指针
QueueNode *tail; //队列的尾指针
public:
Queue()
{
head = NULL;
tail = NULL;
}
void enqueue(TreeNode *node) { //入队列
QueueNode *q = new QueueNode();
q->data = node;
q->next = NULL;
if(head == NULL) {
head = q;
tail = q;
} else {
tail->next = q;
tail = q;
}
}
//判断队列是否是空
bool isEmpty(){
return head == NULL;
}
//出队列
TreeNode * dequeue(){
if(head == NULL) return NULL; //如果当前队列是空，直接返回null.
QueueNode *p = head;
TreeNode *ptree = p->data;
head = head->next;
if (head==NULL) { //如果出队列之后，队列为空了，则修改tail为空
tail == NULL;
}
p->next = NULL;
delete p; //删除队列节点
return ptree;
}
~Queue(){
QueueNode *p = head, *q;
while(p != NULL) {
q = p;
p = p->next;
delete q;
}
}
};
/*
判断一个二叉树是否是完全二叉树
广度优先搜索整个二叉树，一旦找一个节点只不含有子节点或者子含有一个左子节点，
那么后续的所有节点都必须是叶子节点。否则，该树就不是完全二叉树。
*/
bool isCompBinTree(TreeNode *root)
{

if(root == NULL) return true;
Queue qu;
bool last = false; //判断当前是否已经找到了第一个不含有两个子节点的节点。
bool isCompBTree = true;
TreeNode *p;
qu.enqueue(root);
while( ! qu.isEmpty()) {
p = qu.dequeue();
if(! last) { //前面所有的节点都含有两个子节点
if (p->left != NULL && p->right !=NULL) { //当前节点也含有两个子节点
qu.enqueue(p->left);
qu.enqueue(p->right);
} else if (p->left != NULL && p->right==NULL) { //当前节点只含有左子节点，则在其后面的所有节点都必须是叶子节点
last = true;
qu.enqueue(p->left);
} else if (p->left == NULL && p->right!=NULL) { //当前节点只含有右子节点，该树不是完全的。
last = true;
isCompBTree = false;
break;
} else { //当前节点不含有任何的子节点。
last = true;
}
}
else
{
//已经找到了第一个不含有两个子节点的节点，当前扫描的节点必须是叶子节点。
if ( p->left!=NULL || p->right != NULL) {
isCompBTree = false;
break;
}
}
}
if (isCompBTree) {
printf("是完全二叉树.\n");
} else {
printf("不是完全二叉树.\n");
}
return isCompBTree;
}
/*
1 1
2 3 2 3
4 5 4 5 6

*/
void clear(TreeNode *ele[], int n) {
for(int i=0; i<n; i++) {
ele[i]->left = NULL;
ele[i]->right = NULL;
}
}
int main()
{
TreeNode *ele[10];
TreeNode *root, *p, *q;
for(int i=0; i<10; i++) {
ele[i] = new TreeNode(i+1);
}

printf("Case 1: ");
root = ele[0];
root->left = ele[1]; root->right=ele[2];
root->left->left=ele[3]; root->left->right=ele[4];
isCompBinTree(root);

printf("Case 2: ");
clear(ele, 10);
root = ele[0];
root->left = ele[1]; root->right=ele[2];
root->left->right=ele[3]; root->right->left=ele[4]; root->right->right=ele[5];
isCompBinTree(root);

/*
1
*/
printf("Case 3: ");
clear(ele, 10);
root = ele[0];
isCompBinTree(root);

/*
1
2
3
*/
printf("Case 4: ");
clear(ele, 10);
root = ele[0];
root->left = ele[1];
root->left->left = ele[2];
isCompBinTree(root);

/*
1
2
*/
printf("Case 5: ");
clear(ele, 10);
root = ele[0];
root->left = ele[1];
isCompBinTree(root);

/*
1
2 3
4 5
*/
printf("Case 6: ");
clear(ele, 10);
root = ele[0];
root->left = ele[1]; root->right=ele[2];
root->right->left = ele[3]; root->right->right = ele[4];
isCompBinTree(root);

clear(ele, 10);
for(int i=0; i<10; i++) {
delete ele[i];
}
system("pause");
return 0;
}