[编程之美-16]层序打印二元树，每层打印一行

题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 

例如输入：

8

/ \

6 10

/ \ / \

5 7 9 11

输出8 6 10 5 7 9 11  我们增加一下难度，我们打印如下的结果：  8  6 10  5 7 9 11  看到这里大家已经知道我们是怎么打印的吧。按行打印。

思想：层序遍历的思想，就是引入last和nlast，last保存当前层最右一个节点，nlast保存下一行最右一个节点。

代码如下：

#include<iostream> #include<deque> using namespace std; struct BSTreeNode { int m_nValue; BSTreeNode *m_pleft; BSTreeNode *m_pright; }; void addBSTreeNode(BSTreeNode *&pCurrent, int value); void levelOrderBSTree(BSTreeNode *pRoot); int main() { BSTreeNode *pRoot = NULL; addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 5); addBSTreeNode(pRoot, 7); addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 9); addBSTreeNode(pRoot, 11); levelOrderBSTree(pRoot); return 0; } void levelOrderBSTree(BSTreeNode *pRoot) { if(pRoot == NULL) return ; deque<BSTreeNode*> que; que.push_back(pRoot); BSTreeNode *last, *nlast; last = pRoot; nlast = pRoot; while(que.size() != 0) { BSTreeNode *pCurrent = que.front(); que.pop_front(); if(pCurrent != last) cout<<pCurrent->m_nValue<<" "; else cout<<pCurrent->m_nValue<<endl; if(pCurrent->m_pleft != NULL) { nlast = pCurrent->m_pleft; que.push_back(pCurrent->m_pleft); } if(pCurrent->m_pright != NULL) { nlast = pCurrent->m_pright; que.push_back(pCurrent->m_pright); } if(pCurrent == last) last = nlast; } } void addBSTreeNode(BSTreeNode *&pCurrent, int value) { if(pCurrent == NULL) { BSTreeNode *pBSTree = new BSTreeNode(); pBSTree->m_nValue = value; pBSTree->m_pleft = NULL; pBSTree->m_pright = NULL; pCurrent = pBSTree; } else { if((pCurrent->m_nValue) > value) addBSTreeNode(pCurrent->m_pleft, value); else if((pCurrent->m_nValue) < value) addBSTreeNode(pCurrent->m_pright, value); } }