二叉树的广度优先遍历

发表于   |   分类于

实际上也就是二叉树的层次遍历.

二叉树的遍历分为深度优先遍历(分别是: 先中后序遍历), 而广度优先遍历则是层次遍历.

一. 功能

从上往下, 一层一层的遍历每个结点.

二. 算法思想

首先将根指针(注意不是根节点)放进数组中, 输出它的内容, 然后将它的左孩子和右孩子放入数组中.
数组内部指针向后移动, 此时指向它的左孩子, 输出左孩子的内容, 并把左孩子的左孩子和右孩子放进数组中.
…
以此类推, 知道处理完数组中的最后一个元素.

三. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void LevelOrder(BiTree bt)
{
    BiTree Queue[MAXNODE];
    int front, rear;
    front = -1;
    rear = 0;
    Queue[rear] = bt;
    while(front != rear)
    {
        front++;
        printf("%d ",Queue[front]->data);
        if(Queue[front]->lchild != NULL)
        {
            rear++;
            Queue[rear] = Queue[front]->lchild;
        }
        if(Queue[front]->rchild != NULL)
        {
            rear++;
            Queue[rear] = Queue->rchild;
        }
    }
}

从这里可以看出, 队列不一定要用链表实现, 甚至可以用数组实现一个假队列.