从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。例如如下二叉树打印出的结果为1、2、3、4、5、6、7、8、9。
上面所说的也就是二叉树的层序遍历，对于层序遍历来说，首先访问的肯定是根节点，然后是其左右结点，之后就是左子树的左右结点和右子树的左右结点，依次往下，如果使用像前中后序遍历那样按照左右结点去递归打印的话肯定是不行的，因为并不能一直先访问某个左结点或者右结点，而是应该左右交叉访问；
上面的二叉树中，打印的顺序是1、2、3、4、5、6、7、8、9，可以想到按照队列的方式依次将其放入其中，而先进先出，得到的也就是打印的顺序，至于如何存放，可以先将根结点放入其中，拿到队首结点，如果队首结点的左右结点不为NULL，就依次放入队列中，然后将队首元素pop出，再循环取队首元素进行判断放入......直至遍历完二叉树且队列为空为止；
程序设计如下：
计算
安全
数据库
网络和加速
企业服务
#include <iostream>
#include <assert.h>
#include <queue>
using namespace std;
struct BinaryTreeNode//二叉树结点结构体
{
int _val;
BinaryTreeNode *_Lnode;
BinaryTreeNode *_Rnode;
BinaryTreeNode(int val)//构造函数
:_val(val)
,_Lnode(NULL)
,_Rnode(NULL)
{}
};
BinaryTreeNode* _Create(int *arr, size_t& index, size_t size)//前序方式创建二叉树
{
if((index < size) && (arr[index] != '#'))
{
BinaryTreeNode *root = new BinaryTreeNode(arr[index]);
root->_Lnode = _Create(arr, ++index, size);
root->_Rnode = _Create(arr, ++index, size);
return root;
}
else
return NULL;
}
BinaryTreeNode* CreateBinaryTree(int *arr, size_t size)
{
assert(arr && size);
size_t index = 0;
return _Create(arr, index, size);
}
void DestoryBinaryTree(BinaryTreeNode* root)//销毁二叉树
{
if(root != NULL)
{
DestoryBinaryTree(root->_Lnode);
DestoryBinaryTree(root->_Rnode);
delete root;
root = NULL;
}
}
void LevelOrderBinaryTree(BinaryTreeNode *root)//层序遍历二叉树
{
assert(root);
queue<BinaryTreeNode*> q;
q.push(root);
while(!q.empty())
{
if(q.front()->_Lnode != NULL)
q.push(q.front()->_Lnode);
if(q.front()->_Rnode != NULL)
q.push(q.front()->_Rnode);
cout<<q.front()->_val<<" ";
q.pop();
}
cout<<endl;
}
void PrevOrder(BinaryTreeNode* root)//前序遍历二叉树，为了观察二叉树是否创建好
{
if(root != NULL)
{
cout<<root->_val<<" ";
PrevOrder(root->_Lnode);
PrevOrder(root->_Rnode);
}
}
int main()
{
int arr[] = {1,2,4,'#','#',5,8,'#','#','#',3,6,'#','#',7,'#',9,'#','#'};
BinaryTreeNode *root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0]));
cout<<"PrevOrder: ";
PrevOrder(root);
cout<<endl;
cout<<"LevelOrder: ";
LevelOrderBinaryTree(root);
DestoryBinaryTree(root);
return 0;
}运行程序：
《完》
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
