首页 > 代码库 > C++ Level-Order Traversal

C++ Level-Order Traversal

这里讲讲对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(FIFO)也变成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) :