题目描述： 二叉树，按层打印，并且每层换行
分析： 我们知道，二叉树的层序遍历需要借助队列来实现，每取出一个节点打印，并将该节点的左右孩子放入队列中，依此反复，直到队列为空时，也就完成了二叉树的按层打印。
基本过程如图所示：
但是，关键是怎么换行？
分析：要换行则需要知道什么时候换行，由二叉树我们可以分析，我们需要知道每一层最右边的节点，每次打印完这个节点的值后，再打印一个换行即可。于是我们这样做：
定义两个变量，last 和 nlast
last : 表示正在打印的当前行的最右节点
nlast : 表示下一行的最右节点
步骤：
开始让 last 等于二叉树的根节点，并将其点放入队列中。
队头节点出队列，并打印，将该节点的左孩子入队，并让 nlast 等于该节点，将该节点的右孩子入队，并让 nlast 等于该节点。
如果打印的节点等于 last 当前指向的节点，则打印一次换行，同时让 last 等于 nlast。
重复步骤2,3，知道队列为空为止。
图示过程如下：
先将 1 入队
再将 1 出队，并将 2 ，3 入队，并让 nlast 分别指向 2， 3
此时发现，出队列的节点与 last 指向的节点相等，此时，打印换行符。同时让 last 等于 nlast
重复上述步骤，将 2 出队列，并将 4 入队列，让 nlast 指向 4
再将 3 出队列，并将 5,6 入队列，让 nlast 分别指向 5,6 ，此时发现3 等于 last ，则再打印一次换行，并让 last 等于 nlast
重复上述步骤，最终结果如下：
这样，按层换行打印二叉树就完成啦！
代码如下：
计算
安全
数据库
网络和加速
企业服务
#pragma once
#include<iostream>
#include<cassert>
#include<queue>
using namespace std;
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode(const T& x)
:_data(x)
, _left(NULL)
, _right(NULL)
{}
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
};
template<class T>
class BinaryTree
{
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size)
{
size_t index = 0;
_root = _CreateTree(a, size, index);
}
~BinaryTree()
{
_DestroyTree(_root);
_root = NULL;
}
void LevelOrder() //层次遍历
{
_LevelOrder(_root); //每层换行！
}
protected:
BinaryTreeNode<T>* _CreateTree(const T*& a, size_t size, size_t& index)
//创建二叉树
{
assert(a);
BinaryTreeNode<T>* NewNode = NULL;
if (index < size && '#' != a[index])
{
NewNode = new BinaryTreeNode<T>(a[index]);
NewNode->_left = _CreateTree(a, size, ++index);
NewNode->_right = _CreateTree(a, size, ++index);
}
return NewNode;
}
void _DestroyTree(BinaryTreeNode<T>*& root) //销毁二叉树
{
if (NULL == root)
return;
//后序遍历删除结点
_DestroyTree(root->_left);
_DestroyTree(root->_right);
delete root;
root = NULL;
}
void _LevelOrder(BinaryTreeNode<T>*& root)
{
if (NULL == root)
return;
std::queue<BinaryTreeNode<T>*> q;
q.push(root);
BinaryTreeNode<T>* last = root;
BinaryTreeNode<T>* nlast = NULL;
while (!q.empty())
{
BinaryTreeNode<T>* cur = q.front();
cout << cur->_data << " ";
q.pop();
if (cur->_left)
{
q.push(cur->_left);
nlast = cur->_left;
}
if (cur->_right)
{
q.push(cur->_right);
nlast = cur->_right;
}
if (cur == last)
{
cout << endl;
last = nlast;
}
}
cout << endl;
}
protected:
BinaryTreeNode<T>* _root;
};
void Test1()
{
int array[] = { 1, 2, 4, '#', '#', '#', 3, 5, 7, '#', '#', 8, '#', '#', 6 };
BinaryTree<int> t1(array, sizeof(array)/sizeof(int));
t1.LevelOrder();
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
