按层遍历二叉树（行列实现）

按层遍历二叉树（队列实现）

按层遍历二叉树的思路：

1）创建一个队列用于保存指向Node节点的指针

2） 每遇到一个节点就遍历该节点，然后将该节点不为空的孩子压入栈中

3） 从栈中取出一个节点，回到第二步

#include <iostream>#include <queue>using namespace std;struct Node {int num;Node* pLeft;Node* pRight;};void insert(Node* &p,int num){Node* pTmp=new Node();pTmp->num=num;pTmp->pLeft=pTmp->pRight=NULL;if(p==NULL){p=pTmp;return;}if(num<p->num)insert(p->pLeft,num);else if(num>p->num)insert(p->pRight,num);elsereturn;}void PrintInLayer(Node* p){queue<Node*> MyQueue;while(p!=NULL||!MyQueue.empty()){cout<<p->num<<endl;if(p->pLeft!=NULL)MyQueue.push(p->pLeft);if (p->pRight!=NULL)MyQueue.push(p->pRight);if(!MyQueue.empty()){p=MyQueue.front();MyQueue.pop();}elsep=NULL;}}void main(){Node* p=NULL;insert(p,10);insert(p,6);insert(p,14);insert(p,4);insert(p,8);insert(p,12);insert(p,16);insert(p,1);insert(p,5);insert(p,15);insert(p,17);insert(p,7);insert(p,9);        PrintInLayer(p);}