多叉树的宽度优先搜索BFS

发表于 | 分类于 | | 阅读次数:

首先，选择一个合适的数据结构存储多叉树，我使用了“左孩子右兄弟”的方法，使用二叉树来存储多叉树，便于实现和遍历。
其次，宽度优先搜索时：

  1. 用队列（先进先出）保存遍历路径。
  2. 搜索顺序：对节点A，先访问节点的左节点（第一个孩子节点），从该左节点开始一直向右遍历直到最右叶子节点（所有兄弟节点），此时遍历完A的所有直接孩子。遍历的同时，节点入队列。
  3. 遍历完A的孩子后，取队列中的下一个节点，继续遍历其孩子节点。直到队列为空。

代码用C++实现，省略了类Queue, Node的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Tree  
{  
public:  
    Node *root;  
    Tree()  
    {  
        root=NULL;  
    }  

    void BFS()  
    {  
        Queue *queue=new Queue();  
        Node *p=root;  
        if(p == NULL)  
            return;  
        //首先打印根节点  
        printf("%d\t",p->data);  
        //第一个孩子节点  
        p = p->left;  
        while(p != NULL)  
        {  
            //p打印，并入栈  
            queue->push(p);  
            printf("%d\t",p->data);  
            //如果有右孩子，一直入栈  
            p=p->right;  
            while(p!= NULL)  
            {  
                queue->push(p);  
                printf("%d\t",p->data);  
                p=p->right;  
            }  
            p=(Node *)queue->getFront();  
            if(p == NULL)  
                break;  
            //从队列中取出下一个节点，访问它的所有孩子节点  
            queue->pop();  
            p=p->left;  
        }  
    }  
};