二叉树的层序遍历(两种方法实现)

二叉树的层序遍历(两种方法实现)两种方法实现二叉树的层序遍历1、说明二叉树的层序遍历是面试经常会被考察的知识点,甚至要求当场写出实现过程。层序遍历所要解决的问题很好理解,就是按二叉树从上到下,从左到右依次打印每个节点中存储的数据。如下图:先序遍历:A→B→D→C中序遍历:B→D→A→C后续遍历:D→B→C→A层序遍历:A→B→C→…

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


两种方法实现二叉树的层序遍历

1、说明

二叉树的层序遍历是面试经常会被考察的知识点,甚至要求当场写出实现过程。

层序遍历所要解决的问题很好理解,就是按二叉树从上到下,从左到右依次打印每个节点中存储的数据。如下图:

这里写图片描述

先序遍历:A → B → D → C
中序遍历:B → D → A → C
后续遍历:D → B → C → A
层序遍历:A → B → C → D

2、实现

队列实现:
  • 仔细看看层序遍历过程,其实就是从上到下,从左到右依次将每个数放入到队列中,然后按顺序依次打印就是想要的结果。

  • 实现过程
    1、首先将二叉树的根节点push到队列中,判断队列不为NULL,就输出队头的元素,
    2、判断节点如果有孩子,就将孩子push到队列中,
    3、遍历过的节点出队列,
    4、循环以上操作,直到Tree == NULL。

void FloorPrint_QUEUE(pTreeNode &Tree) //层序遍历_队列实现
{
    queue < pTreeNode> q;
    if (Tree != NULL)
    {
        q.push(Tree);   //根节点进队列
    }

    while (q.empty() == false)  //队列不为空判断
    {
        cout << q.front()->data << " → "; 

        if (q.front()->leftPtr != NULL)   //如果有左孩子,leftChild入队列
        {
            q.push(q.front()->leftPtr);   
        }

        if (q.front()->rightPtr != NULL)   //如果有右孩子,rightChild入队列
        {
            q.push(q.front()->rightPtr);
        }
        q.pop();  //已经遍历过的节点出队列
    }
}
数组实现:
  • 实现过程
    1、创建一个指针数组,保存二叉树结构体指针,
    2、保存二叉树根节点,再申请变量 in、out ,控制数组,在遍历过程中,始终能找到节点和该节点的前一个节点,
    3、循环以上过程。
void FloorPrint(pTreeNode Tree)  //层序遍历
{
    pTreeNode temp[100];   //创建pTreeNode指针类型的指针数组
    int in = 0;
    int out = 0;

    temp[in++] = Tree;  //先保存二叉树根节点 

    while (in > out)
    {
        if (temp[out])
        {
            cout << temp[out]->data << " → ";
            temp[in++] = temp[out]->leftPtr;
            temp[in++] = temp[out]->rightPtr;
        }
        out++;
    }
}

3、完整代码

bintree.h

#ifndef __BINTREE_H__
#define __BINTREE_H__

#include<iostream>
#include<cstring>
#include<cassert>
#include<queue>

using namespace std;

typedef char DataType;

struct TreeNode {

    DataType data;    /* node data */

    struct TreeNode *leftPtr;   /* pointer to left subtree */

    struct TreeNode *rightPtr;  /* pointer to right subtree */
};

typedef struct TreeNode TreeNode;

typedef TreeNode * pTreeNode;

void CreateBinTree(pTreeNode *Tree);//创建二叉树

void InitTreeNode(pTreeNode *Tree);//初始化

void PreOrderPrint(pTreeNode Tree);//先序遍历

void MidOrderPrint(pTreeNode Tree);//中序遍历

void PostOrderPrint(pTreeNode Tree);//后续遍历

void FloorPrint(pTreeNode Tree);//层序遍历

void FloorPrint_QUEUE(pTreeNode &Tree);//层序遍历_队列实现

#endif

bintree.cpp

#include"binterr.h"

void InitTreeNode(pTreeNode *Tree)
{
    *Tree = NULL;
}

void CreateBinTree(pTreeNode *Tree)
{
    DataType ch;
    ch = getchar();
    if (ch == '#')
    {
        *Tree = NULL;
    }
    else
    {
        *Tree = (pTreeNode)malloc(sizeof(pTreeNode));

        if (NULL == (*Tree))
        {
            exit(0);
        }
        else
        {
            (*Tree)->data = ch;
            (*Tree)->leftPtr = NULL;
            (*Tree)->rightPtr = NULL;
            CreateBinTree(&(*Tree)->leftPtr); CreateBinTree(&(*Tree)->rightPtr); } } } void PreOrderPrint(pTreeNode Tree) { if (!Tree) { return; } cout << Tree->data << " → ";
    PreOrderPrint(Tree->leftPtr);
    PreOrderPrint(Tree->rightPtr);
}

void MidOrderPrint(pTreeNode Tree)//中序遍历
{
    if (NULL != Tree)
    {
        PreOrderPrint(Tree->leftPtr);
        cout << Tree->data << " → ";
        PreOrderPrint(Tree->rightPtr);
    }
}

void PostOrderPrint(pTreeNode Tree)//后续遍历
{
    if (NULL != Tree)
    {
        PreOrderPrint(Tree->leftPtr);
        PreOrderPrint(Tree->rightPtr);
        cout << Tree->data << " → ";
    }
}

void FloorPrint(pTreeNode Tree)  //层序遍历
{
    pTreeNode temp[100];   //创建pTreeNode指针类型的指针数组
    int in = 0;
    int out = 0;

    temp[in++] = Tree;  //先保存二叉树根节点 

    while (in > out)
    {
        if (temp[out])
        {
            cout << temp[out]->data << " → ";
            temp[in++] = temp[out]->leftPtr;
            temp[in++] = temp[out]->rightPtr;
        }
        out++;
    }
}

void FloorPrint_QUEUE(pTreeNode &Tree) //层序遍历_队列实现
{
    queue < pTreeNode> q;
    if (Tree != NULL)
    {
        q.push(Tree);   //根节点进队列
    }

    while (q.empty() == false)  //队列不为空判断
    {
        cout << q.front()->data << " → "; 

        if (q.front()->leftPtr != NULL) //如果有左孩子,leftChild入队列 { q.push(q.front()->leftPtr); } if (q.front()->rightPtr != NULL) //如果有右孩子,rightChild入队列 { q.push(q.front()->rightPtr); } q.pop(); //已经遍历过的节点出队列 } }

test.cpp

#include"binterr.h"

void test()
{
    pTreeNode T;
    InitTreeNode(&T);

    CreateBinTree(&T);  //创建一个二叉树

    cout << "前序遍历:" << endl;
    PreOrderPrint(T);    //前序遍历

    cout << "\n中序遍历:" << endl;
    MidOrderPrint(T);   //中序遍历

    cout << "\n后序遍历:" << endl;
    PostOrderPrint(T);   //后续遍历

    cout << "\n层序遍历:" << endl;
    FloorPrint(T);

    cout << "\n层序遍历——Queue:" << endl;
    FloorPrint_QUEUE(T);
}

int main(void)
{
    test();
    return 0;
}

4、结果截图

这里写图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/143162.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • datagrip2022安装教程与激活【2021最新】

    (datagrip2022安装教程与激活)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~0H…

  • vs2010旗舰版可用密钥

    vs2010旗舰版可用密钥YCFHQ9DWCYDKV88T2TMHG7BHP

  • 什么叫做解析几何_笛卡尔心形函数

    什么叫做解析几何_笛卡尔心形函数解析几何是进行科学研究的重要的数学工具。比如说,要确定船只在大海中航行的位置,就要确立经纬度,这就需要精确的掌握夭体运行的规律;要改善枪炮的性能,就要精确地掌握抛射物体的运行规律。解决这些问题必须采用解析几何。因为它可以利用字母表示流动坐标,用方程刻划一般平面的曲线。解析几何的发明人就是伟大的数学家笛卡尔。笛卡尔15%年出生在法国,父亲是一位相当富有的律师。8岁时,父亲把他送进荃督教会学校读书。他…

    2022年10月10日
  • 接口和api_api接口入门

    接口和api_api接口入门API集成服务有助于提高开发人员的开发性能并节省大量时间。

  • <四> H264解码输出yuv文件

    <四> H264解码输出yuv文件现在来写下s5pv210的h264解码,这一章有些部分我理解的不是很透彻,只能写个大概了。希望看到的人能给出些意见,有些地方写错的还望指正出来!  解码过程与编码过程类似,编码过程是先初始化编码器,然后从编码器输出buf中读出h264文件头数据,写入输出文件,然后开始不断地将一帧帧NV12格式的图像写入到编码器的输入buf,启动编码,从编码器输出buf中将h264视频数据写入到输出文件。解

  • 分别以递归调用和迭代的方法求数列_迭代算法和递归算法

    分别以递归调用和迭代的方法求数列_迭代算法和递归算法对于数列,递归和迭代的联系非常紧密。a0,a1,a2,…,an−1,ana_0,a_1,a_2,…,a_{n-1},a_na0​,a1​,a2​,…,an−1​,an​数列就是一串数字,数列来源于生活,有用的数列中蕴含着规则。要完整描述一个数列,方法有二:通项公式an=f(n)a_n=f(n)an​=f(n)递推公式其中通项公式是最一般的情况。由通项公式可以求得任意一…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号