这里讲讲对binary Tree 进行level order Traversal.。 即BF traversal（广度优先遍历）。即首先， 访问根节点F， 打印出数据。 接着访问level 1的所有节点， 即D， J。 访问完level1之后， 访问level2， 即B, E, G , K 等等一次访问下去， 直至遍历完所有的节点。

BFS遍历的思路很简单， 但是当我们编程实现的时候， 却会遇到问题的。

首先当我们访问完节点D的时候u， 我们并不能够直接从D到达J， 因为D的指针并没有指向J。

clearly， 只用一个指针是不够的。  我们的解决办法是， 当我们在访问一个节点的时候， 我们将这个节点的所有的孩子（children）的地址保存在一个queue中， so that we can visit them later。

A node in a queue can be called discovered node,but has not visited yet。

例如， 树的各个节点的存储位置如下标记的。 最开始， 我们从根节点开始， 将root node 标记为discovered node， 存储到queue中：

注意只要我们的queue不是empty的， 我们就可以从queue中取出这个地址， 访问树的相关的节点（例如打印节点的数据）。

接下来， 我们enqueue the children of the root node , 得到：

接下来， 我们从queue中（dequeue）200 的地址， 访问这个节点， 打印出数据（为D）， 然后enqueue the childen of the node with D， 得到如下：

接下来， 同理， 直至我们访问完所有的节点， queue（ＦＩＦＯ）也变成NULL了。

NOTE： queue的先进先出保证了我们能够实现BF Traversal.。

下面我们编程实现（C++）：

/* Binary tree - Level Order Traversal */#include<iostream>#include<queue>using namespace std;struct Node {	char data;	Node *left;	Node *right;};// Function to print Nodes in a binary tree in Level ordervoid LevelOrder(Node *root) {	if(root == NULL) return;	queue<Node*> Q;	Q.push(root);	//while there is at least one discovered node	while(!Q.empty()) {		Node* current = Q.front();		Q.pop(); // removing the element at front		cout<<current->data<<" ";		if(current->left != NULL) Q.push(current->left);		if(current->right != NULL) Q.push(current->right);	}}// Function to Insert Node in a Binary Search TreeNode* Insert(Node *root,char data) {	if(root == NULL) {		root = new Node();		root->data = http://www.mamicode.com/data;>

运行结果：
   
下面对上述的遍历算法做一个分析：
首先时间复杂度为O（n）, 因为每一个节点只访问了一次。
其次空间复杂度， 由于我们的queue是dynamic的， 所以空间复杂度（是算法所需要的extra memeroy）， 需要分情况。
最好的的情况下：
 
对于最坏的情况， 也就是完美的二叉树， 空间复杂度达到O（n）:
综合来看Average case下， 算法空间复杂度达到O（n） ：