疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

二叉树层序遍历


 

 
     微软面试题,难度系数低,题目描述如下:
 
  输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。
 
  例如输入
 
  8
 
  /
 
  6 10
 
  / /
 
  5 7 9 11
 
  输出8 6 10 5 7 9 11.
 
  逻辑分析:
 
  1、显然就是二叉树的层序遍历,在学习数据结构课程的时候,多数人都对先序,中序,后序遍历感到熟悉,这三种都属于深度搜索,而层序遍历则是广度搜索。尽管如此,
微软以此为面试题目,还是相当便宜面试者。
 
  2、对于层序遍历,类似先序遍历的想法,我们知道,先序遍历的循环实现需要借助辅助栈来实现,栈是一种LIFO的数据结构,即后进先出,last in first out,那么,对于层序遍历来说,过程刚好相反,即FIFO,first in first out,我们每次将根节点入队列,当队列非空,则将front赋给临时指针temp,继而输出根节点的卫星域,接下来判断根节点左右孩子是否为空,非空则入队列,上述工作以后,再度从队列中取元素,队列空,则循环结束。
  void printByLevel(BSTreeNode* root)
 
  {
 
  queue<BSTREENODE*> Q;
 
  BSTreeNode* p = root;
 
  if(p == NULL)
 
  return ;
 
  Q.push(p);
 
  while(!Q.empty())
 
  {
 
  p = Q.front();
 
  Q.pop();
 
  cout 《 p->m_nValue 《 endl;
 
  if(p->m_pLeft)
 
  Q.push(p->m_pLeft);
 
  if(p->m_pRight)
 
  Q.push(p->m_pRight);
 
  }
 
  }
 
  3、因为之前做的是BSTree的镜像翻转例子,这里为了方便,不再改写为BTree,毕竟二叉排序树也是二叉树的一种。完整代码如下:
 
  #include <IOSTREAM>
 
  #include <QUEUE>
 
  using namespace std;
 
  typedef struct BSTreeNode          //a node in the BST
 
  {
 
  int m_nValue;                            //Value of node
 
  struct BSTreeNode *m_pLeft;    //left child of node
 
  struct BSTreeNode *m_pRight;   //right child of node
 
  }BSTreeNode;
 
  void printByLevel(BSTreeNode* root)
 
  {
 
  queue<BSTREENODE*> Q;
 
  BSTreeNode* p = root;
 
  if(p == NULL)
 
  return ;
 
  Q.push(p);
 
  while(!Q.empty())
 
  {
 
  p = Q.front();
 
  Q.pop();
 
  cout 《 p->m_nValue 《 endl;
 
  if(p->m_pLeft)
 
  Q.push(p->m_pLeft);
 
  if(p->m_pRight)
 
  Q.push(p->m_pRight);
 
  }
 
  }
 
 int main()
 
  {
 
  BSTreeNode node[7];
 
  node[0].m_nValue = 8;
 
  node[0].m_pLeft = &node[1];
 
  node[0].m_pRight = &node[2];
 
  node[1].m_nValue = 6;
 
  node[1].m_pLeft = &node[3];
 
  node[1].m_pRight = &node[4];
 
  node[2].m_nValue = 10;
 
  node[2].m_pLeft = &node[5];
 
  node[2].m_pRight = &node[6];
 
  node[3].m_nValue = 5;
 
  node[3].m_pLeft = NULL;
 
  node[3].m_pRight = NULL;
 
  node[4].m_nValue = 7;
 
  node[4].m_pLeft = NULL;
 
  node[4].m_pRight = NULL;
 
  node[5].m_nValue = 9;
 
  node[5].m_pLeft = NULL;
 
  node[5].m_pRight = NULL;
 
  node[6].m_nValue = 11;
 
  node[6].m_pLeft = NULL;
 
  node[6].m_pRight = NULL;
 
  printByLevel(&node[0]);
 
  return 0;
 
  }
 
  注:这里为了方便,我借用了C++ STL的queue.