两种方法实现二叉树的层序遍历
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;
}