blog

树的遍历搜索

2020.04.07

树的分类

树：由多个节点组成，每个节点最多拥有一个父节点，可拥有多个子节点或无子节点。
二叉树：首先它是一棵树，其次它最多只能拥有两个子节点。

为了方便理解，这里参照 virtual dom 以DOM为例进行节点的定义：

interface VNode {
  tag: string;
  children?: VNode[];
}

举个例子

<html>
  <head>
    <title></title>
    <style></style>
  </head>
  <body>
    <h1><h1>
    <div>
      <h2>
        <span></span>
      </h2>
    </div>
    <script></script>
  </body>
</html>

深度优先搜索遍历(DFS)

深度优先搜索遍历遵循几个规则：

每个节点只能访问一次；
当前节点访问结束后访问其未被访问的子节点；
当所有子节点都被访问后，返回到父节点；

const doWalkDFS = (tree) => {
  const walk = (vnode) => {
    console.log(vnode.tag);
    (vnode.children || []).forEach((item) => {
      walk(item);
    });
  };
  walk(tree);
};

所以上述DOM树中节点的访问顺序应该是：

html > head > title > style > body > h1 > div > h2 > span > script

广度优先搜索遍历(BFS)

广度优先搜索遍历也遵循几个规则：

每个节点只能访问一次；
定义一个队列，首次其中只有根节点；
从队列中获取一个节点进行访问，同时将该节点从队列中删除，将该节点的子节点依次排入队列；
重复第三步直至队列为空。

可以看到，如果说深度优先是纵向的，那么这里的广度优先搜索遍历就是横向的顺序，每次输出都是要将所有同级节点返回才算结束并进行下一级的访问。

const doWalkBFS = (tree) => {
  let queue = [tree];
  const walk = (vnode) => {
    console.log(vnode.tag);
    queue = queue.concat(vnode.children || []);
  };
  let item;
  while (item = queue.shift()) {
    walk(item);
  }
}

上述DOM树中节点的访问顺序应该是：

html > head > body > title > style > h1 > div > script > h2 > span

树转二叉树

将常规树结构转换为二叉树结构需要注意：每个节点都只能最多有两个子节点，且左子节点代表子节点，右子节点代表兄弟节点；

   A             A
 /   \    =>    /
B     C        B
                \
                 C

这样通过 前序遍历 也能实现深度优先搜索遍历的输出顺序。值得一提的是，在React的Fiber架构中也是用到了这种方式的数据结构，这样的好处很明显，就是具有连贯性，当渲染次序为ABC的时候，用二叉树结构就能做到即使在B停止，下次也可以从B继续重新开始未完成的C渲染。

类Fiber实现

在React的Fiber架构中采用了类似的数据结构，即每个节点有一个child子节点，一个sibling兄弟节点以及一个return指向父节点，同时采用链表结构，实现了根据任务调度灵活中断或开始对于节点的访问、渲染等操作。

interface FiberNode {
  tag: string;
  child: FiberNode | null;
  sibling: FiberNode | null;
  return: FiberNode | null;
}

基于上述的结构实现了一个遍历算法

let count = 0;
function doWalk (
  fiberNode: FiberNode, 
  prevNode: FiberNode | null
): [FiberNode | null, FiberNode | null] {
  if (fiberNode === null) {
    // 从根节点返回
    return [fiberNode, prevNode];
  }
  if (count === 4) {
    // 限制每次打印三个节点
    count = 0;
    return [fiberNode, prevNode];
  }

  if (
    prevNode === null // 根节点过来
      || prevNode === fiberNode.return // 父节点过来
      || prevNode.sibling === fiberNode // 兄弟节点过来
  ) {
    console.log(fiberNode.tag);
    // 遍历节点结束后进行计数增加
    count++;
  }

  if (
    prevNode === null // 根节点过来
      || prevNode === fiberNode.return // 父节点过来
      || prevNode.sibling === fiberNode // 兄弟节点过来
  ) {
    // 当前节点为第一次访问，后续需要尝试遍历child、sibling，否则返回return节点
    if (fiberNode.child) {
      // 尝试遍历子节点
      return doWalk(fiberNode.child, fiberNode);
    } else if (fiberNode.sibling) {
      // 尝试遍历兄弟节点
      return doWalk(fiberNode.sibling, fiberNode);
    } else {
      // 当前节点及以下节点都已经遍历结束
      return doWalk(fiberNode.return, fiberNode);
    }
  } else if (prevNode.return === fiberNode) {
    // prevNode是子节点，后续需要尝试遍历sibling，否则返回return节点
    if (fiberNode.sibling) {
      // 尝试遍历兄弟节点
      return doWalk(fiberNode.sibling, fiberNode);
    } else {
      // 当前节点及以下节点都已经遍历结束
      return doWalk(fiberNode.return, fiberNode);
    }
  }
}

上述代码实现了每一次遍历都访问三个节点，同时返回下次开始遍历任务所需的节点信息，模拟任务的中断与继续。代码存在冗余内容，但是大致意思可以非常清晰表示，方便理解，感兴趣的可以看一下。