foreword

The several traversal methods we learned above mainly include: pre-order traversal, in-order traversal, and layer-order traversal. These traversal methods are all implemented recursively, while the hierarchical traversal learned today is implemented in a non-recursive manner, mainly in an iterative manner, and at the same time needs to use a queue structure for auxiliary implementation.

sequence traversal

In fact, layer-order traversal can also be called breadth-first traversal, which is the process of traversing down only in order.

The idea of ​​layer order traversal: use a queue structure for auxiliary implementation, first judge whether the corresponding tree is an empty tree, if it is an empty tree, return it directly, if it is not an empty tree, first put the value of the root node into the queue, Loop traversal. When the queue is not empty, take out the head element first, and then remove the head element from the queue. At this time, you can first access the value stored in the taken out head element, and then judge whether the head element exists in the left and right subtrees. If there is a left subtree, enqueue the left subtree, and if there is a right subtree, enqueue the right subtree. do the next cycle

• Code

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// tree structure
typedef int TreeDataType;

// tree node
typedef struct TreeNode
{
	TreeDataType val;
	struct TreeNode* left;
	struct TreeNode* right;
};


typedef TreeNode* QDataType;

// Define the structure of the nodes in the queue
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* front;
	QueueNode* tail;
}Queue;


void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType val);
QDataType QueueFront(Queue* q);
bool QueueEmpty(Queue* q);
void QueueDestroy(Queue* q);
void QueuePop(Queue* q);





// sequence traversal
void LevelOrder(TreeNode* root)
{
	if (root == NULL)
	{
		// empty tree
		return;
	}
	// non-empty tree
	// enqueue the root node

	// create a queue
	Queue q;// create queue
	QueueInit(&q);// Initialize the queue
	QueuePush(&q, root);// Insert the value of the root node into the queue first

	while (!QueueEmpty(&q))
	{
		// When the queue is not empty, traversal processing is required'
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		// Determine whether the fetched node has left and right subtrees
		if (front->left)
		{
			QueuePush(&q, front->left);
		}

		if (front->right)
		{
			QueuePush(&q, front->right);
		}

		// The value retrieved from the queue must not be empty
		// access to fetched data
		printf("%d ", front->val);
	}
	printf("\n");
	QueueDestroy(&q);

}

Application of layer order traversal: judging whether a tree is a complete binary tree

bool TreeComplete(TreeNode* root)
{
	if (root == NULL)
	{
		return true;
	}

	// non-empty tree
	// create queue
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		// Get the head element
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q,front->left);
		QueuePush(&q,front->right);
	}
	// When the program comes here, it means that NULL has been encountered
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		// When a non-empty node is encountered, it means that the empty node encountered before appears before the non-empty node, which means that the tree is not a complete binary tree
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	// If there is no non-empty node visited in the above, it means that the empty node encountered for the first time has already visited all non-empty nodes
	QueueDestroy(&q);
	return true;

}

Idea analysis:

Using a queue structure for auxiliary implementation, the idea is similar to that of layer order traversal, except that in this question, the empty tree still needs to be queued. When the empty node is traversed for the first time, the first cycle ends. Then traverse the nodes in the queue. If a non-empty node is traversed, it means that the above empty node exists among valid nodes, and the tree is not a complete binary tree. If no non-empty is traversed, it means that the empty node traversed for the first time is after the valid node, indicating that the tree is a complete binary tree.