树遍历算法

前端编程

前言

树是常用的数据结构，Virtual DOM 即标准树结构。后续实现自己的 diff-patch 算法，即建立在树遍历的基础之上，包含深度优先遍历，广度优先遍历。

树遍历

为方便分析，采纳 DOM Tree 作为案例，回避手动构造树结构麻烦，代码如下：

<main class="container" data-traverse-id="bs-container">
  <div class="bs-example" data-traverse-id="bs-alerts">
    <div class="alert alert-success" role="alert" data-traverse-id="alert-success">
      Well done! You successfully read this important alert message.
    </div>
    <div class="alert alert-info" role="alert" data-traverse-id="alert-info">
      Heads up! This alert needs your attention, but it's not super important.
    </div>
    <div class="alert alert-warning" role="alert" data-traverse-id="alert-warning">
      Warning! Better check yourself, you're not looking too good.
    </div>
    <div class="alert alert-danger" role="alert" data-traverse-id="alert-danger">
      Oh snap! Change a few things up and try submitting again.
    </div>
  </div>
  <div class="bs-example" data-traverse-id="bs-list-group">
    <ul class="list-group" data-traverse-id="list-group">
      <li class="list-group-item text-success" data-traverse-id="text-success">Cras justo odio</li>
      <li class="list-group-item text-info" data-traverse-id="text-info">Dapibus ac facilisis in</li>
      <li class="list-group-item text-warning" data-traverse-id="text-warning">Morbi leo risus</li>
      <li class="list-group-item text-danger" data-traverse-id="text-danger">Porta ac consectetur ac</li>
    </ul>
  </div>
</main>

DOM Tree 结构抽象如下：

使用控制台输出作为简单的遍历操作，代码如下：

/**
 * @description - lite operation
 *
 * @param {HTMLElement} node
 */
function operate(node) {
  console.log(`Traverse: ${node.getAttribute('data-traverse-id')}`);
}

深度优先遍历递归如下：

/**
 * @description - depth-first
 *
 * @param {HTMLElement} tree
 * @param {Function} callback
 */
function DFTraverseRecursive(tree, callback) {
  if (!tree) {
    return;
  }
  callback(tree);
  if (tree.children) {
    for (let i = 0; i < tree.childElementCount; i++) {
      DFTraverseRecursive(tree.children.item(i), callback)
    }
  }
}

非递归实现方式如下：

/**
 * @description - depth-first
 *
 * @param {HTMLElement} tree
 * @param {Function} callback
 */
function DFTraverse(tree, callback) {
  let node;
  let Queue = [];
  Queue.push(tree);
  // eslint-disable-next-line
  while (node = Queue.pop()) {
    callback(node);
    if (node.children) {
      for (let i = node.childElementCount; i > 0; i--) {
        Queue.push(node.children.item(i-1));
      }
    }
  }
}

遍历过程示意如下：

广度优先遍历如下：

/**
 * @description - depth-first
 *
 * @param {HTMLElement} tree
 * @param {Function} callback
 */
function BFTraverse(tree, callback) {
  let node;
  let Queue = [];
  Queue.push(tree);
  // eslint-disable-next-line
  while (node = Queue.shift()) {
    callback(node);
    if (node.children) {
      for (let i = 0; i < node.childElementCount; i++) {
        Queue.push(node.children.item(i));
      }
    }
  }
}

遍历过程示意如下：

Contact

Email: hjj491229492@hotmail.com