# [Binary tree series of data structure] level order traversal

## 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);
}

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))
{
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.

Posted by JRS on Mon, 30 Jan 2023 09:08:28 +1030