精华内容
下载资源
问答
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    二叉树层序遍历 1、算法思想 用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点...此过程不断进行,当队列为空时,二叉树层次遍历结束...

    二叉树层次遍历

    层次遍历基础需要了解二叉树、队列。
    二叉树基本运算:https://blog.csdn.net/weixin_42109012/article/details/92000919
    顺序队基本运算:https://blog.csdn.net/weixin_42109012/article/details/92104948

    1. 算法思想

    用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。
    在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点开始,首先将根节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作:

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

    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
    在这里插入图片描述

    展开全文
  • 二叉树层次遍历按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是:通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队。而后每次队列中一个结点出队,都将其左孩子和右孩子...

    二叉树层次遍历

    2e1cbc4826e22793d8dabbef9d7540b9.png

    按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是:通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队。而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,出队结点的先后顺序就是层次遍历的最终结果。

    86a072a4b034728de2e8f732d6ca49ee.png

    图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 
    展开全文
  • 二叉树层次遍历按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是:通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队。而后每次队列中一个结点出队,都将其左孩子和右孩子...

    二叉树层次遍历

    00b5e19feaf94543a27c7115840c12c2.png

    按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是:通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队。而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,出队结点的先后顺序就是层次遍历的最终结果。

    5a2ec3e60b85a5dacb32ccfc03e10d03.png

    图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二叉树层次遍历相关的内容,一起来了解一下这个实例吧!从上往下打印出二叉树的每个节点,同层节点从左至右打印。代码实现:importjava.util.ArrayList;importjava.util....

    下面要给大家分享的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工具网来进行了解呢。

    推荐阅读:

    展开全文
  • 二叉树层次遍历

    2019-06-05 17:48:43
    层次遍历二叉树:即从左到右,从上到下,从左到右依次遍历。 废话不多说,直接上图 ABCEHDFG 上面二叉树层次遍历结果为:A,B,C,D,E,F,G,H 层次遍历的算法思想: 1.初始化一个空队列Q 2.若二叉树bt为空树,则...
  • DP问题,欢迎关注 动态规划一篇就够了 全网最详细, 逐步理解, 万字总结 - Johngo的文章 - 知乎 https://zhuanlan.zhihu.com/p/130743652二叉树层次遍历二叉树的遍历方式主要由先序遍历、中序遍历和后续遍历,还后...
  • 二叉树层次遍历深度优先&广度优先给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。例如: 给定二叉树: [3,9,20,null,null,15,7],3 / 9 20 / 15 7返回其层次遍历结果:...
  • Java 二叉树层次遍历

    2020-06-06 16:28:41
    Java 二叉树层次遍历
  • 二叉树层次遍历算法 #include <stdio.h> #include <alloc.h> #define MaxSize 1000 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTNode; 创建二叉树...
  • 1.二叉树层次遍历 2.二叉树结构图的打印 结语 1.二叉树层次遍历 主要用到队列操作,先入队根结点,再不断出队,判断出队结点是否有左右孩子,有则入队,直到队列空为止。 层次遍历挺简单,但是如果要输出结点...
  • 「@Author:Runsen」在讲解二叉树的时候,提到二叉树的遍历除了前中后序遍历,还有层次遍历。前中后序这三种遍历方法以及可以通过递归的方式实现了,那么今天就来讲讲层次遍历吧!LeetCode 第 102题:二叉树层次...
  • 二叉树层次遍历 力扣​leetcode-cn.com 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)思路:按照 BFS(Breath-First-Search)广度优先搜素的方法,通过维护一个队列,依序将...
  • 二叉树 层次遍历

    2019-02-17 11:20:28
    给定一颗二叉树,依次从根节点一层一层返回节点 基本思路:利用队列模拟这一过程 根节点入队列 取队列头节点 若该节点还有左右节点 入队列 之道队列为空 二叉树结构 struct TreeNode { int val; struct ...
  • 二叉树的遍历详解:前、中、后、层次遍历(Python实现)二叉树是一种常见的数据结构,而它的常见遍历方法有前序遍历、中序遍历、后续遍历、层次遍历——掌握这几种遍历方法是很有必要的。假设我们二叉树节点的定义如下...
  • 5(107) 二叉树层次遍历Ⅱ描述给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)示例给定二叉树 [3,9,20,null,null,15,7], 3 / 9 20 / 15 7...
  • 1040. 二叉树层次遍历  Description 给出一棵二叉树,求它的层次遍历结果。 [二叉树的遍历问题是一种精神,务必领会] Input Format 第一行,N 默认序号为0的节点为树根。接下来共N-1行,依次表示序号为...
  • 二叉树层次遍历和深度遍历

    千次阅读 2015-09-26 17:21:23
    二叉树层次遍历和深度遍历 源码实现过程:
  • 给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树 [3,9,20,null,null,15,7],3 / 9 20 / 15 7返回其自底向上的层次遍历为:[ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,284
精华内容 4,513
关键字:

二叉树层次遍历