BFS用deque来实现，因为deque是FIFO的性质，所以可以通过deque.front()拿到头上的item，然后pointer指着头item,找到他的左右孩子。
传pointer进deque，可以联系起deque和binary tree的联系。deque<TreeNode*>mydeque。
#include <iostream>
#include <deque>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
TreeNode* newNode(int n){
TreeNode* node = new TreeNode(n);
//node->val = n;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode* insert(TreeNode* node, int n){
if (node == NULL){
return (newNode(n));
}
else{
if(n<=node->val){
node->left = insert(node->left, n);
}
else{
node->right = insert(node->right,n);
}
}
return node;
}
void BFSaTree(TreeNode* root,deque<TreeNode*>& mydeque)
{
if(root==NULL){
return;
}
mydeque.push_back(root);
TreeNode* p_root = root;
while(!mydeque.empty())
{
if(p_root->left!=NULL){
mydeque.push_back(p_root->left);
}
if(p_root->right!=NULL){
mydeque.push_back(p_root->right);
}
cout<<mydeque.front()->val<<endl;
mydeque.pop_front();
p_root = mydeque.front();
}
}
int main()
{
TreeNode* node;
//node = insert(node, 2);
// node = insert(node, 3);
// node = insert(node, 1);
// node = insert(node, 1);
// node = insert(node, 8);
// node = insert(node, 9);
deque<TreeNode*>q;
BFSaTree(node,q);
return 0;
}
github的地址：https://github.com/will-I-amor/binaryTree/blob/master/BFS_a_Tree.cpp
