菜鸟笔记
提升您的技术认知

面试题

实现一个LRU Cache 算法LRU Cache C++三种解法java实现LRU算法及编码实现LRU策略缓存LRU算法常见缓存算法和LRU的c++实现设计循环双端队列(deque)LRU 缓存结构 (c++ 哈希双链表实现)LRU缓存机制删除单链表中的指定节点Linux 内核经典面试题拼多多社招面经:Redis是重点,讲一讲redis的内存模型线程、进程、协程的区别C++经典面试题面试官:我们只想要这样的C++工程师Linux C/C++ 学习路线链表操作汇总C++11的智能指针面试题浏览器中输入url后发生的事情常用的限流算法HTTP协议和HTTPS协议面试题网络编程面试题目总结c++后台面试题目如何实现LRU算法?如何寻找无序数组中的第K大元素?布隆过滤器 - 如何在100个亿URL中快速判断某URL是否存在?如何实现大整数相加?C++面试题及基本知识点总结C++给定出栈序列判定是否合法消息队列面试题要点redis缓存击穿,失效以及热点key解决方案网页在浏览器上的渲染过程几种限流算法lru算法例题C/C++常见面试知识点总结附面试真题----20210529更新引入MQ消息队列的作用及其优缺点MySQL面试篇社招三年后端面试题60道测开面试题,背完直接涨工资二叉树的层序遍历(两种方法实现)Bitmap 海量数据处理字符串倒序输出的五种方法C语言 输入10个数,统计出并输出正数、负数和0的个数字节三面:如何设计一个高并发系统架构,网络 面试36问,DDos攻击原理C++线程池使用 C++11 编写可复用多线程任务池

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

阅读 : 1009

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

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
#include
#include
#include

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、结果截图