多叉树的宽度优先搜索BFS

6-01 2,411 views

首先，选择一个合适的数据结构存储多叉树，我使用了“左孩子右兄弟”的方法，使用二叉树来存储多叉树，便于实现和遍历。
其次，宽度优先搜索时：
1.用队列（先进先出）保存遍历路径。
2.搜索顺序：对节点A，先访问节点的左节点（第一个孩子节点），从该左节点开始一直向右遍历直到最右叶子节点（所有兄弟节点），此时遍历完A的所有直接孩子。遍历的同时，节点入队列。
3.遍历完A的孩子后，取队列中的下一个节点，继续遍历其孩子节点。直到队列为空。
代码用C++实现，省略了类Queue, Node的实现：

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;  
        }  
    }  
};

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;

}

};

版权属于: 我爱我家

原文地址: http://magicwt.com/2012/06/01/%e5%a4%9a%e5%8f%89%e6%a0%91%e7%9a%84%e5%ae%bd%e5%ba%a6%e4%bc%98%e5%85%88%e6%90%9c%e7%b4%a2bfs/

转载时必须以链接形式注明原始出处及本声明。