大家好,又见面了,我是你们的朋友全栈君。
两种方法实现二叉树的层序遍历
两种方法实现二叉树的层序遍历
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账号...