二叉树层次遍历(借助队列实现)
/*按层次遍历二叉树
*经调试可运行源码及分析如下：
***/
#include <>
#include <iostream>
#include <queue>
using std::cout;
using std::cin;
using std::endl;
using std::queue;
/*二叉树结点定义*/
typedef struct BTreeNode
{
char elem;
struct BTreeNode *pleft;
struct BTreeNode *pright;
}BTreeNode;
/*
按层次遍历二叉树步骤：
第一步：借助队列，首先将根节点proot入队；
第二步：当队列不空时，获得队首元素并出队，赋给proot，执行第三步；
第三步：如果proot左节点存在，则入队；如果proot右节点存在，则入队；执行第二步。
*/
/*按层次遍历二叉树*/
void level_traverse(BTreeNode* proot)
{
if (proot == NULL)
return;
queue <BTreeNode*> que;
(proot);
while (!())
{
proot = ();
();
cout << "遍历节点：" << proot->elem << endl;
if (proot->pleft != NULL)
{
(proot->pleft);//左孩子入队
}
if (proot->pright != NULL)
{
(proot->pright);//右孩子入队
}
}
}
/*初始化二叉树根节点*/
BTreeNode* btree_init(BTreeNode* &bt)
{
bt = NULL;
return bt;
}
/*先序创建二叉树*/
void pre_crt_tree(BTreeNode* &bt)
{
char ch;
cin >> ch;
if (ch == '#')
{
bt = NULL;
}
else
{
bt = new BTreeNode;
bt->elem = ch;
pre_crt_tree(bt->pleft);
pre_crt_tree(bt->pright);
}
}
int main()
{
int tree_node_number = 0;
BTreeNode *bt;
btree_init(bt);//初始化根节点
pre_crt_tree(bt);//创建二叉树
level_traverse(bt);//递归
system("pause");
return 0;
}
/*
运行结果：
a b c # # # d e # # #
---以上为输入---
---以下为输出---
遍历节点：a
遍历节点：b
遍历节点：d
遍历节点：c
遍历节点：e
请按任意键继续. . .
本例创建的二叉树形状：
a
b d
c e
参考资料：
/beitiandijun/article/details/41940417
/code/c_505ea04f8f6186
*/