JavaScript实现DOM树的深度优先遍历和广度优先遍历

约定不等于承诺〃 2022-05-10 09:48 230阅读 0赞

#### 深度优先遍历 ####

// 非递归,首次传入的node值为DOM树中的根元素点，即html
    // 调用：deep(document.documentElement)
    function deep (node) {
      var res = []; // 存储访问过的节点
      if (node != null) {
        var nodeList = []; // 存储需要被访问的节点
        nodeList.push(node);
        while (nodeList.length > 0) {
          var currentNode = nodeList.pop(); // 当前正在被访问的节点
          res.push(currentNode);
          var childrens = currentNode.children;
          for (var i = childrens.length - 1; i >= 0; i--) {
            nodeList.push(childrens[i]);
          }
        }
      }
      return res;
    }
    
    // 使用递归
    var res = []; // 存储已经访问过的节点
    function deep (node) {
      if (node != null) { // 该节点存在
        res.push(node);
        // 使用childrens变量存储node.children，提升性能，不使用node.children.length，从而不必在for循环遍历时每次都去获取子元素
        for (var i = 0,  childrens = node.children; i < childrens.length; i++) {
          deep(childrens[i]);
        }
      }
      return res;
    }

#### 广度优先遍历 ####

// 递归
    var res = [];
    function wide (node) {
      if (res.indexOf(node) === -1) {
        res.push(node); // 存入根节点
      }
      var childrens = node.children;
      for (var i = 0; i < childrens.length; i++) {
        if (childrens[i] != null) {
          res.push(childrens[i]); // 存入当前节点的所有子元素
        }
      }
      for (var j = 0; j < childrens.length; j++) {
        wide(childrens[j]); // 对每个子元素递归
      }
      return res;
    }
    
    // 非递归
    function wide (node) {
      var res = [];
      var nodeList = []; // 存储需要被访问的节点
      nodeList.push(node);
      while (nodeList.length > 0) {
        var currentNode = nodeList.shift(0);
        res.push(currentNode);
        for (var i = 0, childrens = currentNode.children; i < childrens.length; i++) {
          nodeList.push(childrens[i]);
        }   
      }
      return res;
    }