[关闭]
@linux1s1s 2015-05-07T09:45:24.000000Z 字数 785 阅读 2161

树的层序遍历

C/C++


我们先来看一下这道面试题目

此处输入图片的描述

二叉树结点的定义如下:

  1. struct BinaryTreeNode
  2. {
  3. int m_nValue;
  4. BinaryTreeNode *m_pLeft;
  5. BinaryTreeNode *m_pRight;
  6. };

从上到下打印二叉树的规律:

每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。

既然我们已经确定数据容器是一个队列了,现在的问题就是如何实现队列。实际上我们无需自己动手实现,因为STL已经为我们实现了一个很好的deque(两端都可以进出的队列)。下面是用deque实现的参考代码:

  1. void PrintFromTopToBottom(BinaryTreeNode *pTreeRoot)
  2. {
  3. if(!pTreeRoot)
  4. return;
  5. std::deque<BinaryTreeNode*> dequeTreeNode;
  6. dequeTreeNode.push_back(pTreeRoot);
  7. while(dequeTreeNode.size())
  8. {
  9. BinaryTreeNode *pNode = dequeTreeNode.front();
  10. dequeTreeNode.pop_front();
  11. printf("%d " , pNode->m_nValue);
  12. if(pNode->m_pLeft)
  13. dequeTreeNode.push_back(pNode->m_pLeft);
  14. if(pNode->m_pRight)
  15. dequeTreeNode.push_back(pNode->m_pRight);
  16. }
  17. }

转载自:http://www.cnblogs.com/heyonggang/archive/2013/11/03/3405282.html

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注