一、二叉树的层序遍历

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历比较特别,需要用到前面学过的队列知识.

[数据结构]队列-CSDN博客

我先来说一下我们的思路:

我们是这样完成的:

1.我们先创建一个队列:

2.然后让1入队列:

3.接着把1的左右子树入队列:

4.因为1的左右子树已经入队列了,此时打印1然后让1出队列:

5.然后让2(也就是一的左子树)的左右子树入队列:

6.因为2的左右子树已经入队列了,此时打印2然后让2出队列:

7.然后让3的左右子树入队列:

8.然后让3出队列:

9.后面子树为空就不入队列,依次打印元素,,在打印完最后一个元素时(这里是7),销毁队列.

接下来我们来完成这个思路,下面是代码实现:

1.我们先写一个二叉树的接口:

typedef struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right;} TreeNode;

2.写一个队列的接口,以及相关操作:

typedef struct QueueNode {TreeNode* treenode;struct QueueNode* next;} QueueNode;typedef struct Queue {QueueNode* front;QueueNode* rear;} Queue;void initQueue(Queue* q) {q->front = q->rear = NULL;}int isEmpty(Queue* q) {return q->front == NULL;}void enqueue(Queue* q, TreeNode* treenode) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->treenode = treenode;newNode->next = NULL;if (isEmpty(q)) {q->front = q->rear = newNode;}else {q->rear->next = newNode;q->rear = newNode;}}

3.二叉树节点出队列:

TreeNode* dequeue(Queue* q) {if (isEmpty(q)) return NULL;QueueNode* temp = q->front;TreeNode* treenode = temp->treenode;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(temp);return treenode;}

4.层序遍历:

void levelOrderTraversal(TreeNode* root) {if (root == NULL) return;Queue q;initQueue(&q);enqueue(&q, root);while (!isEmpty(&q)) {TreeNode* current = dequeue(&q);printf("%d ", current->val);if (current->left != NULL) {enqueue(&q, current->left);}if (current->right != NULL) {enqueue(&q, current->right);}}}

下面我们来简单的测试一下:

我们写一个简单的主函数,然后运行一下:

int main() {TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = 1;root->left = (TreeNode*)malloc(sizeof(TreeNode));root->left->val = 2;root->left->left = (TreeNode*)malloc(sizeof(TreeNode));root->left->right = (TreeNode*)malloc(sizeof(TreeNode));root->right = (TreeNode*)malloc(sizeof(TreeNode));root->right->val = 3;root->right->left = (TreeNode*)malloc(sizeof(TreeNode));root->right->right = (TreeNode*)malloc(sizeof(TreeNode));root->left->left->val = 4;root->left->left->left = NULL;root->left->left->right = NULL;root->left->right->val = 5;root->left->right->left = NULL;root->left->right->right = NULL;root->right->left->val = 6;root->right->left->left = NULL;root->right->left->right = NULL;root->right->right->val = 7;root->right->right->left = NULL;root->right->right->right = NULL;levelOrderTraversal(root);return 0;}

我们把上面的二叉树数据写入,如果是层序遍历,结果应该就是:1 2 3 4 5 6 7

运行结果:

结果正确.

---

大家也可结合上回的前序遍历来把数据写入二叉树，使这段代码更加有意思。本篇的内容到此就结束了，感谢阅读。