题目
1、不分行从上到下打印二叉树
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如，输入图4.6中的二叉树，则依次打印出8，6，10，5，7，9，11.
分析
因为按层打印的顺序决定了先打印根结点，所以我们从树的根结点开始分析。
为了能够打印值为8的结点的两个子结点，我们应该在遍历到该结点时把值为6和值为10的两个结点保存到队列里，那么现在队列内就有两个结点了。
按照从左到右打印的要求，我们先取出值为6的结点，打印出6之后，把它的子结点5和7放入队列。接下来取值为10的结点，然后把子结点9和11放入队列。典型的先进先出，配合队列完美的实现层级打印操作
总结：每次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到队列的末尾。接下来从队列的头部取出最早进入队列的结点，重复前面的打印操作，直到队列中所有的结点都被打印出来
算法实现
#include <iostream>
#include <deque>
using namespace std;
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
void PrintFromTopToBottom(BinaryTreeNode *pRoot) {
if (pRoot == nullptr)
return;
deque<BinaryTreeNode *> dequeTreeNode;
// 入队列
dequeTreeNode.push_back(pRoot);
while (dequeTreeNode.size()) {
// 获取第一个结点
BinaryTreeNode *node = dequeTreeNode.front();
// 第一个结点出队列
dequeTreeNode.pop_front();
// 打印结点值
printf("%d", node->m_nValue);
// 左子结点存在入队列
if (node->m_pLeft) {
dequeTreeNode.push_back(node->m_pLeft);
}
// 右子结点存在入队列
if (node->m_pRight) {
dequeTreeNode.push_back(node->m_pRight);
}
}
}
2、分行从上到下打印二叉树
从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。例如下：
8
6 10
5 7 9 11
算法实现
void Print(BinaryTreeNode *pRoot) {
if (pRoot == nullptr)
return;
queue<BinaryTreeNode *> nodes;
nodes.push(pRoot);
int nextLevel = 0;
int toBePrinted = 1;
while (!nodes.empty()) {
BinaryTreeNode *pNode = nodes.front();
printf("%d", pNode->m_nValue);
if (pNode->m_pLeft != nullptr) {
nodes.push(pNode->m_pLeft);
++nextLevel;
}
if (pNode->m_pRight != nullptr) {
nodes.push(pNode->m_pRight);
++nextLevel;
}
nodes.pop();
--toBePrinted;
if (toBePrinted == 0) {
printf("\n");
toBePrinted = nextLevel;
nextLevel = 0;
}
}
}
在上述代码中，变量toBePrinted表示在当前层中还没有打印的结点数，而变量nextLevel表示下一层的结点数。如果一个结点有子结点，则每把一个子结点加入队列，同时把变量nextLevel加1。每打印一个结点，toBePrinted减1。当toBePrinted变成0时，表示当前层的所有结点已经打印完毕，可以继续下一层
3、之字形打印二叉树
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。例如：
1
3 2
4 5 6 7
15 14 13 12 11 10 9 8
思路：
按之字形顺序打印二叉树需要两个栈，在打印某一层的结点时，把下一层的子结点保存到相应的栈里，如果当前打印的是奇数层（第一层、第三层等），则先保存左子结点再保存右子结点到第一个栈里；如果当前打印的是偶数层（第二层、第四层等），则先保存右子结点再保存左子结点到第二个栈里
算法实现
void Print(BinaryTreeNode *pRoot) {
if (pRoot == nullptr)
return;
stack<BinaryTreeNode *> levels[2];
int current = 0;
int next = 1;
levels[current].push(pRoot);
while (!levels[0].empty() || !levels[1].empty()) {
// 获取栈顶元素
BinaryTreeNode *pNode = levels[current].top();
levels[current].pop();
// 打印值
printf("%d", pNode->m_nValue);
// 入栈子结点
if (current == 0) {
if (pNode->m_pLeft != nullptr) {
levels[next].push(pNode->m_pLeft);
}
if (pNode->m_pRight != nullptr) {
levels[next].push(pNode->m_pRight);
}
} else {
if (pNode->m_pRight != nullptr) {
levels[next].push(pNode->m_pRight);
}
if (pNode->m_pLeft != nullptr) {
levels[next].push(pNode->m_pLeft);
}
}
// 当前行结点打印结束
if (levels[current].empty()) {
printf("\n"); // 换行
current = 1 - current;
next = 1 - next;
}
}
}
参考
《剑指offer》
