大家好，又见面了，我是你们的朋友全栈君。
两种方法实现二叉树的层序遍历
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);//层序遍历_队列实现
#endifbintree.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、结果截图
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/143162.html原文链接：https://javaforall.cn
