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.