@linux1s1s
2015-05-07T09:45:24.000000Z
字数 785
阅读 2180
C/C++
我们先来看一下这道面试题目
二叉树结点的定义如下:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
从上到下打印二叉树的规律:
每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。
既然我们已经确定数据容器是一个队列了,现在的问题就是如何实现队列。实际上我们无需自己动手实现,因为STL已经为我们实现了一个很好的deque(两端都可以进出的队列)。下面是用deque实现的参考代码:
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/archive/2013/11/03/3405282.html