分享程序员开发的那些事...
更新时间：2021-09-30 13:06:36
|
题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
|
例如输入
8
/ \
6 10
/\ /\
5 7 9 11
输出8 6 10 5 7 9 11。
二叉树结点的定义如下：
struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; };
从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。
既然我们已经确定数据容器是一个队列了，现在的问题就是如何实现队列。实际上我们无需自己动手实现，因为STL已经为我们实现了一个很好的deque（两端都可以进出的队列）。下面是用deque实现的参考代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void PrintFromTopToBottom(BinaryTreeNode *pTreeRoot)
{ if(!pTreeRoot)
return;
std::deque<BinaryTreeNode*> dequeTreeNode;
dequeTreeNode.push_back(pTreeRoot);
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);
}
} |
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3405282.html，如需转载请自行联系原作者