JavaScript实现树深度优先和广度优先遍历搜索

1、前置条件

我们提前构建一棵树，类型为 Tree ，其节点类型为 Note。这里我们不进行过多的实现，简单描述下 Note 的结构：

class Node{

    constructor(data){

        this.data = data;

        this.children = []; // 存放所以子节点,如果是二叉树，可以分为两个属性，left和right分别存储左右子节点

    }

}

class Tree{

    constructor(){

        this.root = new Node('root'); // 树结构，标识出自己的根节点

    }

}

2、广度优先遍历

广度优先遍历，就是按层来遍历树结构，例如：

    1

  2   3

4  5    6

// 遍历出来的结果：123456

实现思路：

1. 首先创建一个队列，然后将树的根节点，放入队列，作为队列第一个元素
1. 然后开始遍历队列，如果遍历的元素，有子节点，则将所有子节点，追加进队列末尾
1. 最后的队列就是广度优先遍历的结果
  
  使用JavaScript来实现：

function bsf(tree){

        let quen = []; // 用来遍历的数组

        // let result = []; // 遍历的结果

        quen.push(tree.root);

        // 从队列取，然后再追加

        for(let i = 0;i<=quen.length-1;i++){

            let k = quen[i];

            if(k.children.length){

                quen = quen.concat(k.children);

            }

        }

        return quen;

    }

3、深度优先搜索

先遍历完一个末尾节点，再遍历第二个末尾节点，例如：

    1

  2   3

4  5    6

// 遍历出来的结果：124536

深度优先，最简单的方法就是递归遍历，但是不适合实际中使用：

使用栈来实现深度优先遍历：

1. 节点需要增加一些属性，来标识我们的计算状态，isDone是否已经检测过，isOver是否还有子节点未检测
1. 建立一个栈，把树的根节点放进去。在准备一个数组，用来显示我们检测的路径
1. 取出栈中最上面的节点，检测（检测完放进路径数组）,然后将某个未检测的子节点，放入栈
1. 重复3步骤，如果该节点，没有未检测的子节点，且自身已检测完毕，则将其上级节点，再次添加到栈中
1. 重复3步骤

巴特西

JavaScript实现树深度优先和广度优先遍历搜索

1、前置条件

2、广度优先遍历

3、深度优先搜索

最新文章

热门文章