微软等数据结构与算法面试100题第十六题

第十六题

题目:

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

分析：

这道题主要考察的是二叉树的广度优先周游，比较简单。就是使用队列（queue）作为辅助实现。

#include<iostream>#include<queue>using namespace std;struct node{node * nodeLeft;node * nodeRight;int value;};void levelOrder(node * root){queue<node *> pNodeQueue;node * pNodeTemp = root;pNodeQueue.push(pNodeTemp);while(!pNodeQueue.empty()){if(!pNodeQueue.empty()){pNodeTemp = pNodeQueue.front();pNodeQueue.pop();cout<<pNodeTemp->value<<" ";}if(NULL!=pNodeTemp->nodeLeft){pNodeQueue.push(pNodeTemp->nodeLeft);}if(NULL!=pNodeTemp->nodeRight){pNodeQueue.push(pNodeTemp->nodeRight);}}}int main(){//构建树struct node * a = new struct node();struct node * b = new struct node();struct node * c = new struct node();struct node * d = new struct node();struct node * e = new struct node();struct node * f = new struct node();a->nodeLeft = b;a->nodeRight = c;a->value = 1;b->nodeLeft = d;b->value = 2;b->nodeRight = NULL;c->nodeLeft = e;c->nodeRight = NULL;c->value = 3;d->nodeLeft = NULL;d->nodeRight = f;d->value = 4;e->nodeLeft = NULL;e->nodeRight = NULL;e->value = 5;f->nodeLeft = NULL;f->nodeRight = NULL;f->value = 6;levelOrder(a);return 0;}