《二叉树》——3（层序遍历）

目录

前言：

层序遍历:

解析：

---

前言：

本文主讲链式二叉树的层序遍历，在前面的张篇blog我们初步实现了链式二叉树递归部分的内容，对于递归算法的学习和思维方式我们仍然需要不断加强，所以将对链式二叉树进行收尾，下一章我们将开启递归算法的题目强化训练。

层序遍历:

typedef struct BTTreeNode* QDataType;
//将链队列中的节点类型改为struct BTTreeNode（二叉树节点的数据类型）void TreeLevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root == NULL){printf("空树\n");exit(-1);}int levelsize = 1;QueuePush(&q, root);while (!QueueEmpty(&q)){while (levelsize--){TreeNode* front = QueueFront(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}QueuePop(&q);}printf("\n");levelsize = QueueSize(&q);}printf("\n");QueueDestroy(&q);
}

层序遍历不需要用到递归的思想，用我们之前学习过的队列的知识就可以实现层序遍历。

这里是用到队列的先进先出的特性。

以上是一颗二叉树，现在要实现该数的层序遍历，最终结果为：

1

2 4

3 5 6

解析：

    Queue q;QueueInit(&q);if (root == NULL){printf("空树\n");exit(-1);}int levelsize = 1;QueuePush(&q, root);

 对于这一串代码，就是定义队列并且初始化，并将根节点入队列，再定义一个队列长度，用来接受队列里的节点数，当levelsize为空时，就代表当前层数的节点已经打印完毕。因为是将根节点入队列，而且第一层有且只有一个节点，即根节点，所以levelsize = 1;

while (!QueueEmpty(&q)){while (levelsize--){TreeNode* front = QueueFront(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}QueuePop(&q);}printf("\n");levelsize = QueueSize(&q);}

 

目前的队列如上图所示。

首先我们需要将定义front指针指向队列的第一个元素。

此时我们需要将root的左右子树入队列，首先我们需要判断左右子树是否为空树。

如果不是空树就入队列。

则有：

 

而这个时候front指向的节点会被先打印出来，再出队列，这时候front就会指向下一个节点，并且levelsize也为0，因为这时候队列的首数据已经出队列，所以队列中只有两个数据，那么levelsize就会被赋值为2。

如图：

 

 同样，接下来就是判断front指向的节点的左右子树是否为空，不为空则入队列。

即：

由于levelsize为2，所以程序会打印队列的前两个数据，即24

2打印完后，front就会指向4这个节点，同样也会判断该节点的左右子树是否为空，不为空则入队列。

如图：

 

然后打印完4的节点后，levelsize又会被赋值为3，用来答应下一层的节点。

 

如此不断重复，层序遍历则完美实现。