二叉树层序遍历（C语言）[通俗易懂]

全栈程序员-用户IM • 2022年5月22日上午7:40 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

二叉树的层序遍历即从上到下，在每一层从左到右依次打印数据。

如下：
在这里插入图片描述
层序遍历结果：
ABCDEFG

基本思路即将根节点入队后，之后每次都将队首元素出队，打印队首元素数据，并将队首元素左右子树入队，一直重复上述过程。

自然，本题还可以用数组来实现。

代码：

#include <stdio.h>
#include <stdlib.h>
#define QueueMax 100

typedef struct Node
{ 
   
    char data;
    struct Node *LChild, *RChild;
}BiNode, *BiTree;

typedef struct
{ 
   
    BiTree data[QueueMax];
    int head;
    int rear;
    int len;
}Queue;

BiTree CreateTree();  //建立二叉树
Queue InitQueue();  //初始化队列
int IsEmptyQueue(Queue seq);  //队列判空
int IsFullQueue(Queue seq);   //队列判满
void PushQueue(Queue *seq, BiTree T);  //入队
void PopQueue(Queue *seq, BiTree *T);  //出队
void LayerOrder(BiTree T);  //层序遍历

int main()
{ 
   
    BiTree T;
    T = CreateTree();
    LayerOrder(T);
    return 0;
}

BiTree CreateTree()
{ 
     //建立二叉树
    char c;
    c = getchar();
    BiTree T;
    if (c == '#') { 
   
        return NULL;
    }
    T = (BiTree) malloc (sizeof(BiNode));
    T->data = c;
    T->LChild = CreateTree();
    T->RChild = CreateTree();
    return T;
}

Queue InitQueue()
{ 
     //初始化队列
    Queue seq;
    for(int i = 0; i < QueueMax; i++) { 
   
        seq.data[i] = NULL;
    }
    seq.head = 0;
    seq.rear = -1;
    seq.len = 0;
    return seq;
}

int IsEmptyQueue(Queue seq)
{ 
     //队列判空
    if (seq.len == 0) { 
   
        return 1;
    }
    return 0;
}

int IsFullQueue(Queue seq)
{ 
     //队列判满
    if (seq.len == QueueMax) { 
   
        return 1;
    }
    return 0;
}

void PushQueue(Queue *seq, BiTree T)
{ 
     //入队
    if (IsFullQueue(*seq)) { 
   
        printf("ErrorFull");
        return;
    }
    seq->rear = (seq->rear + 1) % QueueMax;
    seq->len++;
    seq->data[seq->rear] = T;
}

void PopQueue(Queue *seq, BiTree *T)
{ 
     //出队
    if (IsEmptyQueue(*seq)) { 
   
        printf("ErrorEmpty");
        return;
    }
    seq->head = (seq->head + 1) % QueueMax;
    *T = seq->data[seq->head];
    seq->len--;
}

void LayerOrder(BiTree T)
{ 
     //层序遍历
    Queue seq;
    seq = InitQueue();
    BiTree tmp;
    tmp = T;
    PushQueue(&seq, tmp);
    while(!IsEmptyQueue(seq)) { 
   
        printf("%c", tmp->data);
        if (tmp->LChild != NULL) { 
   
            PushQueue(&seq, tmp->LChild);
        }
        if (tmp->RChild != NULL) { 
   
            PushQueue(&seq, tmp->RChild);
        }
        PopQueue(&seq, &tmp);
    }
}