以级别的顺序穿越二进制树意味着按级别访问树级中的所有节点，从根开始，然后向下移动到叶子。
在这篇文章中，我们将使用队列数据结构来查看C中的实现。
数据结构
struct binary_tree_s
{
int n;
struct binary_tree_s *left;
struct binary_tree_s *right;
};
typedef struct binary_tree_s binary_tree_t;
执行
- 首先，我们检查输入二进制树是否不是空。
/* if tree is NULL */
if (tree == NULL)
{
return;
}
- 接下来，我们创建一个队列数据结构来存储需要添加的二进制树节点。
/* create queue to store node items */
binary_tree_t **queue = malloc(sizeof(*queue) * 1024);
if (queue == NULL) /* malloc fails */
{
return;
}
- 我们将树的根节点添加到队列中，然后将队列的尾巴和大小增加。
int head, tail, size, i;
head = tail = size = 0; /* initialize to zero */
queue[0] = tree; /* add root node to queue */
tail = size = 1; /* tail and size increases by 1 */
- 然后我们的功能进入一个循环，该循环在队列中的项目上迭代。
- 对于队列中的每个项目，该功能都会打印节点数据的值。
- 如果当前节点有一个左孩子，则将左子添加到队列中，并且队列的尾巴会增加。
- 如果当前节点有合适的孩子，则将正确的孩子添加到队列中，并且队列的尾巴会增加。
- 一旦将当前级别的所有节点添加到队列中，就会更新头部和大小索引以准备添加下一个级别。直到添加了树中的所有节点为止。
while (head < size) /* iterate over the items in the queue */
{
for (i = head; i < size; i++)
{
printf("%d\n", queue[i]->n); /* print value */
if (queue[i]->left) /* check if a left child exists */
{
queue[tail] = queue[i]->left; /* last item in queue now points to left */
tail++; /* tail increases */
}
if (queue[i]->right) /* check if a right child exists */
{
queue[tail] = queue[i]->right; /* last item in queue now points to right */
tail++; /* tail increases */
}
}
/* head becomes size this indicates the number of items that have been iterated/printed */
head = size;
/* size becomes tail, this is the number of items in the queue */
size = tail;
}
- 最后，我们释放了为队列分配的内存。
free(queue); /* free queue */
输出
树是使用级别的遍历打印的。
binary_trees$ ./level_order
.-------(098)-------.
.--(012)--. .--(402)--.
(006) (056) (256) (512)
98
12
402
6
56
256
512
binary_trees$