博客

给我们一棵二叉树，我们可以一眼认出是否是

完全二叉树

，现在如何用代码判断完全二叉树呢？

我之前去百度了一下完全二叉树，上面说完全二叉树是一种效率极高的数据结构，究竟高在什么地方呢，说实话，我也不知道哈哈哈哈哈，上网搜了一圈也没有找到让我信服的答案，有兴趣的小伙伴可以上网查一查，可能是我现在的水平还不足以体会到完全二叉树有什么特殊的效果吧，但是作为数据结构的一种，咱们先学好再说，到以后做一些项目可能灵感会来得快点，废话不多说，今天的内容是

用代码

判断完全二叉树

核心代码块：

/*判断完全二叉树*/
int isComplete(BiTreeNode *root)
{
    //只有根结点，当然是完全二叉树
    if (root->leftChild == NULL && root->rightChild == NULL)
        return 1;
    Queue queue, *p1,*p2;
    p1 = &queue;
    p2 = &queue;
    initiateQueue(p1);
    queueAppend(p1,root);    //将根结点入队列
    BiTreeNode q;
    while (1)
    {
        BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        getHead(p1, temp);
        if (temp->data == '0')   //直到队列为空，跳出循环
            break;
        queuePop(p1, &q);
        queueAppend(p1, temp->leftChild);    //将出队的左孩子结点入队
        queueAppend(p1, temp->rightChild);
    }
    while (isNotEmpty(p2))
    {
        BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        getHead(p1, temp);
        if (temp->data != '0')       //如果队列不为空，就不是完全二叉树
            return 0;
        queuePop(p2, &q);
    }
    return 1;
}

代码思想：

1. 完全二叉树中间不会缺少结点

2. 中间缺少结点的二叉树就不是完全二叉树，否则即是Complete binary tree

3. 利用队列首先将根结点入队，再将根结点出队

4. 将出队结点的左孩子结点入队

5. 将出队结点的右孩子结点入队

6. 在进行一次出队，重复4,5步骤，直到出队的结点没有数据（即空结点）

7. 如果队列不为空，一直出队，如果出队的结点不是无数据的结点，那么就不是完全二叉树；如果出队的结点全是无数据的结点，那么是完全二叉树

8. 当然需考虑特殊情况，例如二叉树只有一个根结点等等

以上步骤就能判断二叉树中间是否有缺少的结点

实例代码:

注：实例由4个文件构成：《BiTree.h》《Domin.h》《Queue.h》《main.c》，本文核心代码块放在《Domin.h》头文件内

《BiTree.h》

#pragma once
/*二叉树基本操作头文件*/
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;   //声明数据类型
struct  BiTreeNode
{
    DataType data;
    BiTreeNode *leftChild;
    BiTreeNode *rightChild;
};
//初始化二叉树
void  initiateBiTree(BiTreeNode **root)
{
    (*root) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    (*root)->leftChild = NULL;
    (*root)->rightChild = NULL;
}
//插入左孩子结点
BiTreeNode* leftInsert(BiTreeNode *curr, DataType data)
{
    if (curr == NULL)
        return NULL;
    BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    node->data = data;
    node->rightChild = NULL;
    node->leftChild = curr->leftChild;
    curr->leftChild = node;
    return node;
}
//插入右孩子结点
BiTreeNode* rightInsert(BiTreeNode *curr, DataType data)
{
    if (curr == NULL)
        return NULL;
    BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    node->data = data;
    node->leftChild = NULL;
    node->rightChild = curr->rightChild;
    curr->rightChild = node;
    return node;
}
//前序遍历二叉树
void preOrder(BiTreeNode *root)
{
    if (root != NULL)
    {
        printf("%c ", root->data);
        preOrder(root->leftChild);
        preOrder(root->rightChild);
    }
}
//中序遍历
void midOrder(BiTreeNode *root)
{
    if (root != NULL)
    {
        preOrder(root->leftChild);
        printf("%c ", root->data);
        preOrder(root->rightChild);
    }
}

《Domin.h》

#pragma once
#include"Queue.h"
#include"BiTree.h"
/*二叉树的功能头文件*/
/*判断完全二叉树*/
int isComplete(BiTreeNode *root)
{
    //只有根结点，当然是完全二叉树
    if (root->leftChild == NULL && root->rightChild == NULL)
        return 1;
    Queue queue, *p1,*p2;
    p1 = &queue;
    p2 = &queue;
    initiateQueue(p1);
    queueAppend(p1,root);    //将根结点入队列
    BiTreeNode q;
    while (1)
    {
        BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        getHead(p1, temp);
        if (temp->data == '0')   //直到队列为空，跳出循环
            break;
        queuePop(p1, &q);
        queueAppend(p1, temp->leftChild);    //将出队的左孩子结点入队
        queueAppend(p1, temp->rightChild);
    }
    while (isNotEmpty(p2))
    {
        BiTreeNode *temp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        getHead(p1, temp);
        if (temp->data != '0')       //如果队列不为空，就不是完全二叉树
            return 0;
        queuePop(p2, &q);
    }
    return 1;
}

《Queue.h》

#pragma once
/*队列基本操作头文件*/
#include"BiTree.h"
typedef BiTreeNode queueDataType;
struct QueueNode
{
    queueDataType data;
    QueueNode *next;
};
struct Queue
{
    QueueNode *head;
    QueueNode *rear;
};
void initiateQueue(Queue *queue)
{
    queue->head = NULL;
    queue->rear = NULL;
}
/*判断非空*/
bool isNotEmpty(Queue* queue)
{
    if (queue->head == NULL)
        return false;
    return true;
}
/*入队函数*/
void queueAppend(Queue *queue, queueDataType *data)
{
    QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    if (data != NULL)
    {
        node->data.data = data->data;
        node->data.leftChild = data->leftChild;
        node->data.rightChild = data->rightChild;
    }
    else {
        node->data.data = '0';       // 用0来标记要入队的结点是空的二叉树结点
        node->data.leftChild = NULL;
        node->data.rightChild = NULL;
    }
    node->next = NULL;
    if (queue->rear == NULL)
    {
        queue->head = node;
        queue->rear = node;
    }
    else
    {
        queue->rear->next = node;
        queue->rear = node;
    }
}
/*出队函数*/
void queuePop(Queue*queue, queueDataType *data)
{
    if (!isNotEmpty(queue))
        return;
    *data = queue->head->data;
    queue->head = queue->head->next;
    if (queue->head == NULL)
        queue->rear = NULL;
}
/*取队头元素*/
void  getHead(Queue *queue,queueDataType *head)
{
    if (!isNotEmpty(queue))
        head = NULL;
    else
        *head = (queue->head->data);
}
/*遍历队列*/
void print(Queue*queue)
{
    printf("队列：");
    QueueNode *p;
    p = queue->head;
    while (p!=NULL)
    {
        printf("%c  ",p->data.data);
        p = p->next;
    }
    printf("\n");
}

《main.c》

注：为了验证所建立的二叉树是否为指定二叉树，采用前序遍历和中序遍历 输出二叉树的结点

#include"Queue.h"
#include"BiTree.h"
#include"Domin.h"
int main()
{
    /*测试二叉树*/
    BiTreeNode *root, *p;
    initiateBiTree(&root);
    p = leftInsert(root, 'A');
    p = leftInsert(p, 'B');
    leftInsert(p, 'D');
    rightInsert(p, 'E');
    p = rightInsert(root->leftChild, 'C');
    leftInsert(p, 'F');
    rightInsert(p, 'G');
    printf("二叉树前序遍历：");
    preOrder(root->leftChild);
    printf("\n");
    printf("二叉树中序遍历：");
    midOrder(root->leftChild);
    printf("\n");
    if (isComplete(root->leftChild))
        printf("该二叉树是完全二叉树！\n");
    else
        printf("该二叉树不是完全二叉树！\n");
    system("pause");
    return 0;
}

测试结果：

测试一：是完全二叉树

测试二：不是完全二叉树

将主函数稍微变动,注释掉中间的一个结点F

变成这样一棵二叉树

代码编译器：

Visual Studio 2017


ok