层序遍历判断完全二叉树

完全二叉树

层序遍历重点

使用辅助序列实现，在上一层遍历完后，下一层的所以节点都进入到辅助序列中

动画过程

层序遍历判断完全二叉树

实现代码

test.c

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#include"Queue.h"//二叉树结构体声明
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;//创建节点函数
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->val = x;node->left = NULL;node->right = NULL;return node;
}// 判断二叉树是否是完全二叉树
int TreeComplete(BTNode* root)
{//创建辅助队列Queue* q = QueueCreate();//如果不是空树，插入根节点if (root)QueuePush(q, root);//二叉树的层序遍历while (!QueueEmpty(q)){BTNode* front = QueueFront(q);if (front == NULL)break;QueuePush(q, front->left);QueuePush(q, front->right);QueuePop(q);}// 已经遇到空节点，如果队列中后面的节点还有非空，就不是完全二叉树while (!QueueEmpty(q)){BTNode* front = QueueFront(q);QueuePop(q);if (front != NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}int main()
{// 手撸二叉树BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;printf("TreeComplete：%d\n", TreeComplete(node1));TreeDestroy(node1);node1 = NULL;return 0;
}

test.c的main函数中用于检验的树结构如下。

Queue.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;typedef struct QNode
{QDataType data;struct QNode* next;
} QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
} Queue;Queue* QueueCreate();
void QueueDestroy(Queue* q);void QueuePush(Queue* q, QDataType x);
QDataType QueuePop(Queue* q);QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);int QueueSize(Queue* q);
bool QueueEmpty(Queue* q);

Queue.c

#include"Queue.h"Queue* QueueCreate()
{Queue* q = (Queue*)malloc(sizeof(Queue));if (NULL == q){perror("malloc failed");exit(-1);}q->head = q->tail = NULL;q->size = 0;return q;
}void QueueDestroy(Queue* q)
{assert(q);while (!QueueEmpty(q))QueuePop(q);free(q);
}void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (NULL == newnode){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;if (QueueEmpty(q))q->head = q->tail = newnode;else{q->tail->next = newnode;q->tail = newnode;}++(q->size);
}QDataType QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QDataType ret = q->head->data;QNode* newhead = q->head->next;free(q->head);q->head = newhead;if (NULL == newhead)q->tail = NULL;--(q->size);return ret;
}QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->head->data;
}QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->tail->data;
}int QueueSize(Queue* q)
{assert(q);return q->size;
}bool QueueEmpty(Queue* q)
{assert(q);return !(q->size);
}