二叉树层次遍历
层次遍历基础需要了解二叉树、队列。

二叉树基本运算：https://blog.csdn.net/weixin_42109012/article/details/92000919

顺序队基本运算：https://blog.csdn.net/weixin_42109012/article/details/92104948
1. 算法思想
用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。

在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

访问该元素所指向的节点
若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。

2. 原理解释
2.1. 二叉树图
一个二叉树，层次遍历就是每一行每一行的取出数据。

这个图的结果就是 ABCDEFGH


2.2. 层次遍历过程图
就是先父节点进入队列，然后循环，出队时带入下一组子节点进队，没有就没有进入队列的，当队列为空时结束循环。


3. 代码实现
3.1 实现步骤
1、首先将二叉树的根节点进入队列中，判断队列不为NULL。

2、打印输出该节点存储的元素。

3、判断节点如果有孩子（左孩子、右孩子），就将孩子进入队列中。

4、循环以上操作，直到 BT->lchild == NULL、BT->rchild=NULL。
3.2 全部代码
#define _CRT_SECURE_NO_WARNINGS // VS忽略警告，其它应该不需要

#include <malloc.h>
#include <stdio.h>
#include <string.h>

#define MAX_SIZE 1024
#define STR_SIZE 1024

typedef struct Node {    // 定义二叉链
    char         data;   // 数据元素
    struct Node* lchild; // 指向左孩子节点
    struct Node* rchild; // 指向右孩子节点
} BTNode;                // struct Node 的别名

typedef struct Quene {      // 定义顺序队
    int     front;          // 队头指针
    int     rear;           // 队尾指针
    BTNode* data[MAX_SIZE]; // 存放队中元素
} SqQueue;                  // struct Queue 的别名

/**
 * 队列函数
 */
void initQueue(SqQueue*& q);            // 初始化对立
bool emptyQueue(SqQueue*& q);           // 判断队列空
bool enQueue(SqQueue*& q, BTNode*& BT); // 入队
bool deQueue(SqQueue*& q, BTNode*& BT); // 出队

/**
 * 二叉树函数
 */
// void createBTNode2(BTNode** BT);                  // 创建二叉树
int  createBTNode(BTNode*& BT, char* str, int n); // 创建二叉树
void preOrder(BTNode*& BT);                       // 前序遍历
void inOrder(BTNode*& BT);                        // 中序遍历
void postOrder(BTNode*& BT);                      // 后序遍历
void levelOrder(BTNode*& BT);                     // 层次遍历

/**
 * 画树函数
 */
void draw_level(BTNode* root, bool left, char* str); // 画分支
void draw(BTNode* root);                             // 画根节点

/***************************************************************************
 * @date    2019/12/08
 * @brief   层次遍历二叉树
 * @param   BT  二叉树根节点
 ***************************************************************************/
void levelOrder(BTNode*& BT) {
    SqQueue* q;   // 定义队列
    initQueue(q); // 初始化队列
    if (BT != NULL) {
        enQueue(q, BT); // 根节点指针进队列
    }
    // 一层一层的把节点存入队列，当没有孩子节点时就不再循环
    while (emptyQueue(q) != true) { // 队不为空循环
        deQueue(q, BT);             // 出队时的节点
        printf("%c", BT->data);     // 输出节点存储的值
        if (BT->lchild != NULL) {   // 有左孩子时将该节点进队列
            enQueue(q, BT->lchild);
        }
        if (BT->rchild != NULL) { // 有右孩子时将该节点进队列
            enQueue(q, BT->rchild);
        }
    }
}

int main() {
    // 例子：ABDH###E##CF##G##
    BTNode* BT;
    printf("请输入字符串：");
    char* str = (char*)malloc(sizeof(char) * STR_SIZE);
    scanf("%s", str);
    if (strlen(str) == createBTNode(BT, str, 0)) {
        printf("二叉树建立成功\n");
    }
    // printf("请输入字符串：");
    // createBTNode2(&BT);
    draw(BT);

    printf("\n先序遍历结果：");
    preOrder(BT);

    printf("\n中序遍历结果：");
    inOrder(BT);

    printf("\n后序遍历结果：");
    postOrder(BT);

    printf("\n层序遍历结果：");
    levelOrder(BT);

    return 0;
}

// 初始化队列
void initQueue(SqQueue*& q) {
    q        = (SqQueue*)malloc(sizeof(SqQueue)); // 分配一个空间
    q->front = q->rear = -1;                      // 置 -1
}

// 判断队列是否为空
bool emptyQueue(SqQueue*& q) {
    // 首指针和尾指针相等，说明为空。空-返回真，不空-返回假
    if (q->front == q->rear) {
        return true;
    } else {
        return false;
    }
}

// 进队列
bool enQueue(SqQueue*& q, BTNode*& BT) {
    // 判断队列是否满了。满（插入失败）-返回假，不满（插入成功）-返回真
    if (q->rear == MAX_SIZE - 1) {
        return false;
    }
    q->rear++;             // 头指针加 1
    q->data[q->rear] = BT; // 传值
    return true;
}

// 出队列
bool deQueue(SqQueue*& q, BTNode*& BT) {
    // 判断是否空了。空（取出失败）-返回真，不空（取出成功）-返回假
    if (q->front == q->rear) {
        return false;
    }
    q->front++;             // 尾指针加 1
    BT = q->data[q->front]; // 取值
    return true;
}

// 创建二叉树
int createBTNode(BTNode*& BT, char* str, int n) {
    char ch = str[n];    // 把第 n 个字符赋给ch,方便后面判断
    n       = n + 1;     // 字符下标后移
    if (ch != '\0') {    // 如果 ch 不等于结束符就继续创建，否则就结束
        if (ch == '#') { // 以 # 号代表 NULL，下面没有了
            BT = NULL;
        } else {
            BT       = new BTNode;                       // 新建一个二叉链
            BT->data = ch;                               // 把字符存入二叉链
            n        = createBTNode(BT->lchild, str, n); // 左递归创建
            n        = createBTNode(BT->rchild, str, n); // 右递归创建
        }
    }
    // 返回 n，记录字符串使用到哪里了
    return n;
}
// 二级指针创建
// void createBTNode2(BTNode** BT) {
//     char ch;
//     ch = getchar();
//     if (ch == '#') {
//         *BT = NULL;
//     } else {
//         if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
//             printf("内存分配失败！");
//             return;
//         } else {
//             (*BT)->data = ch;
//             createBTNode2(&((*BT)->lchild)); // 分配成功则接着建立左子树和右子树
//             createBTNode2(&((*BT)->rchild));
//         }
//     }
// }

// 先序遍历
void preOrder(BTNode*& BT) {
    if (BT != NULL) {           // 判断不为空
        printf("%c", BT->data); // 访问根节点
        preOrder(BT->lchild);   // 递归，先序遍历左子树
        preOrder(BT->rchild);   // 递归，先序遍历右子树
    }
}

// 中序遍历
void inOrder(BTNode*& BT) {
    if (BT != NULL) {
        inOrder(BT->lchild);
        printf("%c", BT->data);
        inOrder(BT->rchild);
    }
}

// 后序遍历
void postOrder(BTNode*& BT) {
    if (BT != NULL) {
        postOrder(BT->lchild);
        postOrder(BT->rchild);
        printf("%c", BT->data);
    }
}

/*****************************************************************************
* @date   2020/4/19
* @brief  水平画树
* @param  root	二叉树节点
* @param  left	判断左右
* @param  str 	可变字符串
*****************************************************************************/
void draw_level(BTNode* root, bool left, char* str) {
    if (root->rchild) {
        draw_level(root->rchild, false, strcat(str, (left ? "|     " : "      ")));
    }

    printf("%s", str);
    printf("%c", (left ? '\\' : '/'));
    printf("-----");
    printf("%c\n", root->data);

    if (root->lchild) {
        draw_level(root->lchild, true, strcat(str, (left ? "      " : "|     ")));
    }
    //  "      " : "|     " 长度为 6
    str[strlen(str) - 6] = '\0';
}

/*****************************************************************************
* @date   2020/4/19
* @brief  根节点画树
* @param  root	二叉树根节点
*****************************************************************************/
void draw(BTNode* root) {
    char str[STR_SIZE];
    memset(str, '\0', STR_SIZE);

    if (root->rchild) {
        draw_level(root->rchild, false, str);
    }
    printf("%c\n", root->data);
    if (root->lchild) {
        draw_level(root->lchild, true, str);
    }
}


4. 结果展示
创建二叉树是以 “#” 为结束符NULL。

例子就是最上面的图：ABDH###E##CF##G##

结果应该为：ABCDEFGH

二叉树层次遍历
按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。
图1 二叉树
层次遍历的实现过程
例如，层次遍历图 1 中的二叉树：
首先，根结点 1 入队；
根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 分别入队；
队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 依次入队；
队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 依次入队；
不断地循环，直至队列内为空。
实现代码
#include #define TElemType int//初始化队头和队尾指针开始时都为0int front=0,rear=0;typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));  (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL;  (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL;  (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL;  (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}//入队函数void EnQueue(BiTree *a,BiTree node){ a[rear++]=node;}//出队函数BiTNode* DeQueue(BiTNode** a){ return a[front++];}//输出函数void displayNode(BiTree node){ printf("%d 

二叉树层次遍历
按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。
图1 二叉树
层次遍历的实现过程
例如，层次遍历图 1 中的二叉树：
首先，根结点 1 入队；
根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 分别入队；
队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 依次入队；
队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 依次入队；
不断地循环，直至队列内为空。
实现代码
#include #define TElemType int//初始化队头和队尾指针开始时都为0int front=0,rear=0;typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));  (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL;  (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL;  (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL;  (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}//入队函数void EnQueue(BiTree *a,BiTree node){ a[rear++]=node;}//出队函数BiTNode* DeQueue(BiTNode** a){ return a[front++];}//输出函数void displayNode(BiTree node){ printf("%d 

下面要给大家分享的java实例是和java二叉树层次遍历相关的内容，一起来了解一下这个实例吧!
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
代码实现：import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution
{
public ArrayList  PrintFromTopToBottom(TreeNode root)
{
ArrayList  resultList = new ArrayList  ();
if (root == null)
{
return resultList;
}
Queue  q = new LinkedList  ();
q.add(root);
while (!q.isEmpty())
{
TreeNode nowNode = q.peek();
q.poll();
resultList.add(nowNode.val);
if (nowNode.left != null)
{
q.add(nowNode.left);
}
if (nowNode.right != null)
{
q.add(nowNode.right);
}
}
return resultList;
}
}
在学习java的过程当中，多看一些相关实例是非常好的，希望上面的例子可以对你有所帮助哦。
你还想了解更多的java经典实例吗?可以继续关注奇Q工具网来进行了解呢。
推荐阅读：