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

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

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;

}