“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

// The sequence is repeated
void BinaryTreeLeveOrder(BTNode* root);
// Check whether the binary tree is a complete binary tree
bool BinaryTreeComplete(BTNode* root);
Copy the code

BinaryTreeLeveOrder:

🔑 Core idea 🔑

Queue mode: enter the first layer, exit the upper layer, then enter the next layer… .

You need to use the queue you implemented earlier

BinaryTreeComplete:

🔑 Core idea 🔑

The presence of a complete binary tree must have something to do with the hierarchy

The sequence is repeated, and the void is also queued

Complete binary trees, non-empty is continuous, empty is continuous

An incomplete binary tree is not continuous if it is not empty, and empty is discontinuous

❗ three files are required here ❕

1️ leveorder. h, used for declaration of functions

#pragma once

/ / head
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

/ / structure
typedef struct BinaryTreeNode*  QDataType;
typedef struct QueueNode
{
	struct QueueNode* next; // point to the next node
	QDataType data; // Store integer data
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;/ / the head pointer
	QueueNode* ptail;/ / the tail pointer
}Queue;

/ / function
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x);	
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);
Copy the code

2️ leveorder. c, used for the realization of the function

#include"Queue_LeveOrder.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	// set two Pointers to null
	pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	// Create a BuyQueueNode for malloc space
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(- 1);
	}
	newnode->data = x;
	newnode->next = NULL;
	// First insertion
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	// Non-first insertion
	else{ pq->ptail->next = newnode; pq->ptail = newnode; }}bool QueueEmpty(Queue* pq)
{
	assert(pq);
	// Empty lists return true, non-empty lists return false
	return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	// The linked list cannot be deleted when it is emptyassert(! QueueEmpty(pq));// There is only one node
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	// Multiple nodes
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead) ; pq->phead = next; }}QDataType QueueSize(Queue* pq)
{
	assert(pq);
	// If you need to call QueueSize frequently, you can add a member to the Queue structure for the length of the record
	int sz = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{
		sz++;
		cur = cur->next;
	}
	return sz;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	// If the list is empty, the header cannot be fetchedassert(! QueueEmpty(pq));return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	// If the list is empty, no tail can be fetchedassert(! QueueEmpty(pq));return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	
	QueueNode* cur = pq->phead;
	// Iterate over the list
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}
Copy the code

3️ Test. C, used for function Test

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

// This contains the queue.h file
#include"Queue_LeveOrder.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}
// Create a binary tree
BTNode* BinaryCreatBinaryTree(a)
{
	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 = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;

	return node1;
}
// The sequence is repeated
void BinaryTreeLeveOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		/ / into the queue
		QueuePush(&q, root);
	}
	while(! QueueEmpty(&q)) {// retrieve queue header data
		BTNode* front = QueueFront(&q);
		/ / out of the team
		QueuePop(&q);
		printf("%d ", front->_data);
		if (front->_left)
		{
			// Enter the left subtree
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			// Enter the right subtreeQueuePush(&q, front->_right); }}printf("\n");
	QueueDestory(&q);
}
// Check whether the binary tree is a complete binary tree
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		/ / into the queue
		QueuePush(&q, root);
	}
	while(! QueueEmpty(&q)) {// retrieve queue header data
		BTNode* front = QueueFront(&q);
		/ / out of the team
		QueuePop(&q);
		// break the interval
		if(front == NULL)
		{
			break;
		}
		// Enter the left subtree
		QueuePush(&q, front->_left);
		// Enter the right subtree
		QueuePush(&q, front->_right);
	}
	// The queue is empty, which is a complete binary tree; And non-empty, it's not a perfect binary tree
	while(! QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q);/ / is not empty
		if(front)
		{
			QueueDestory(&q);
			return false; }}/ / is all empty
	QueueDestory(&q);
	return true;
}
// Finally destroy the binary tree
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}
int main(a)
{
	BTNode* root = BinaryCreatBinaryTree();
	BinaryTreeLeveOrder(root);
	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));
	BinaryTreeDestroy(root);
	root = NULL;
	return 0;
}
Copy the code