从上到下打印二叉树
题目一：不分行从上到下打印二叉树。
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
image.png
从上到下按层打印的顺序为 8, 6, 10, 5, 7, 9, 11
因为按层打印的顺序决定应该先打印根节点，所以我们从树的根节点开始分析。为了接下来能够打印值为 8 的节点的两个子节点，我们应该在遍历到该节点时把值为 6 和 10 的两个节点保存到一个容器里，现在容器内就有两个节点了。按照从左到右打印的要求，我们先取出值为 6 的节点。打印出值 6 之后，把它的值分别为 5 和 7 的两个节点放入数据容器。此时数据容器中有 3 个节点，值分别为 10、5 和 7。接下来我们从数据容器中取出值为 10 的节点。注意到值为 10 的节点比值为 5 和 7 的节点先放入容器，此时又比这两个节点先取出，这就是我们通常所说的先入先出，因此不难看出这个数据容器应该是一个队列。由于值为 5、7、9、11 的节点都没有子节点，因此只要依次打印即可。
image.png
每次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的未尾。接下来到队列的头部取出最早进入队列的节点，重复前面的打印操作，直至队列中所有的节点都被打印出来。
#include <deque>
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
void PrintFromTopToBottom(BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return;
std::deque<BinaryTreeNode *> dequeTreeNode;
dequeTreeNode.push_back(pRoot);
while(dequeTreeNode.size())
{
BinaryTreeNode *pNode = dequeTreeNode.front();
dequeTreeNode.pop_front();
printf("%d ", pNode->m_nValue);
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft);
if(pNode->m_pRight)
dequeTreeNode.push_back(pNode->m_pRight);
}
}
摘抄资料：《剑指offer》
题目二：分行从上到下打印二叉树。
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
image.png
打印结果为：
8
6 10
5 7 9 11
用一个队列来保存将要打印的节点。为了把二叉树的每一行单独打印到一行里，我们需要两个变量：一个变量表示在当前层中还没有打印的节点数；另一个变量表示下一层节点的数目。
#include <queue>
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
void Print(BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return;
std::queue<BinaryTreeNode*> nodes;
nodes.push(pRoot);
int nextLevel = 0; // 表示下一层的节点数
int toBePrinted = 1; // 表示在当前层中还没有打印的节点数
while(!nodes.empty())
{
BinaryTreeNode* pNode = nodes.front();
printf("%d ", pNode->m_nValue);
// 如果一个节点有子节点，则每把一个子节点加入队列，同时把变量 nextLevel 加 1
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; // 每打印一个节点 toBePrinted 减 1
if(toBePrinted == 0) // 当 toBePrinted 变成 0 时，表示当前层的所有节点已经打印完毕，可以继续打印下一层。
{
printf("\n");
toBePrinted = nextLevel;
nextLevel = 0;
}
}
}
摘抄资料：《剑指offer》
题目三：之字形打印二叉树。
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
image.png
打印结果为：
1
3 2
4 5 6 7
15 14 13 12 11 10 9 8
按之字形顺序打印二叉树需要两个栈。我们在打印某一层的节点时，把下一层的子节点保存到相应的栈里。如果当前打印的是奇数层（第一层、第三层等），则先保存左子节点再保存右子节点到第一个栈里；如果当前打印的是偶数层（第二层、第四层等），则先保存右子节点再保存左子节点到第二个栈里。
image.png
定义两个栈 levels[0] 和 levels[1]。在打印一个栈里的节点时，它的子节点保存到另一个栈里。当一层所有节点都打印完毕时，交换这两个栈并继续打印下一层。
#include <stack>
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
void Print(BinaryTreeNode* pRoot)
{
if(pRoot == nullptr)
return;
std::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》
