好久没有写博客了，主要是没有想到写什么。最近有点焦虑，感觉自己啥也学不进去，工作上又特别清闲，虽然很安逸，但确实很焦虑。所以想着还是随便写点吧，也不是很难的东西，权当做个笔记记录一下吧，也好打发打发时光，排解焦虑。

关于树的遍历的话，其实平常开发的过程中常用吧，其实也并不是很常用，但也并非完全无用。主要场景的话可能在于一些层级菜单/部门树/权限树/层级节点树遍历之类可能会有一点点用处。

0. 引言

关于树的遍历的话，其实平常开发的过程中常用吧，其实也并不是很常用，但也并非完全无用。主要场景的话可能在于一些层级菜单/部门树/权限树/层级节点树遍历之类可能会有一点点用处。

但是总之，我还是对此做一个简单的总结，把树的遍历方法做一个记录。关于树的遍历算法的话，我会分m叉树和二叉树的遍历进行分类，原因大致有二：

  1. 二叉树与m叉树的数据结构会有一些差别（当然也可以用同样的数据结构同化掉）。
  2. 相对于m叉树，二叉树有其特殊的遍历方式

另外的话，我们熟知树结构的特殊性，所以从实现上来讲，树的算法很多都可以使用递归去实现，但递归会带来额外开销，所以就简单的遍历而言，我们完全可以使用迭代的思维去实现。故而，下面的算法我也会记录一下非递归实现。

tree

1. m叉树遍历

1.0 TREE 结构mock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        {
          value: 3,
          children: [],
        },
        {
          value: 4,
          children: [],
        },
        {
          value: 5,
          children: [],
        }
      ]
    },
    {
      value: 6,
      children: [
        {
          value: 7,
          children: []
        }
      ]
    }
  ]
}

1.1 DFS（Depth-First Search）

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const dfsGenerator = <T>(dfsKey: keyof T) => {
      const dfs = (tree: T | null, callback?: (v: T | null) => void) => {
        if(tree === null || tree === undefined) return;
        const children = tree[dfsKey]
        if(typeof callback === 'function') {
          callback(tree)
        }
        // @Comment: 1⃣️
        if(children instanceof Array && children.length > 0) {
          children.forEach(item => {
            dfs(item, callback);
          })
        }
      }
      return dfs;
    }

    1⃣️ 由于栈结构，先入栈的元素后出，故而此处为保证对于children的遍历索引从小到大，需要逆序入栈

  • 非递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    const dfsGenerator = <T>(dfsKey: keyof T) => {
      const dfsByStack = (tree: T | null, callback?: (v: T | null) => void) => {
        if(tree === null || tree === undefined) return;
        const stack: T[] = [];
        stack.push(tree);
        while(stack.length !== 0) {
          const temp = stack.pop() as T;
          const children = temp[dfsKey];
          if(typeof callback === 'function') {
            callback(temp);
          }
          if(children instanceof Array && children.length > 0) {
            for(let i = children.length - 1; i >= 0; i--) {
              stack.push(children[i]);
            }
          }
        }
      }
      return dfsByStack;
    }

    const bfs = bfs

  • Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

1.2 BFS（Beadth-First Search）

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    const bfsGenerator = <T>(bfsKey: keyof T) => {
    	// @Comment: 1⃣️ flag
      const bfs = (tree: T | null, callback?: (v: T | null) => void, flag = 0) => {
        if(tree === null || tree === undefined) return;
        if (flag === 0 && typeof callback === 'function') {
          callback(tree);
        }
        const children = tree[bfsKey];
        if (children instanceof Array) {
          if(typeof callback === 'function') {
            children.forEach(node => callback(node))
            children.forEach(node => bfs(node, callback, flag + 1))
          }
        }
      }
      return bfs;
    }

    1⃣️ flag参数，用于标记当前遍历的层级，是为了判断在0层的时候对根节点调用callback。当然也可以将层级标记传给callback，作为参数回调出去也是可以的。

  • 非递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    const bfsGenerator = <T>(bfsKey: keyof T) => {
      const bfsByQueue = (tree: T | null, callback?: (v: T | null) => void) => {
        if(tree === null || tree === undefined) return;
        const queue: T[] = [];
        queue.push(tree);
        while(queue.length > 0) {
          const temp = queue.shift() as T;
          const children = temp![bfsKey];
          if(typeof callback === 'function') {
            callback(temp);
          }
          if(children instanceof Array) {
            children.forEach((item: any) => {
              queue.push(item);
            })
          }
        }
      }
      return bfsByQueue;
    }

  • Output: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 7

2. 二叉树遍历

2.0 二叉树结构定义

1
2
3
4
5
6
7
8
9
10
11
12
class TTreeNode<DataType> {
  key: number;
  value: DataType;
  left: TTreeNode<DataType> | null;
  right: TTreeNode<DataType> | null;
  constructor(key: number, value: DataType) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

定义完二叉树的类结构以后给一个buildTRee的函数，用于我们去构建测试数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 生成测试数据
**/
// 子节点索引计算
const left = idx => idx * 2;
const right = idx => idx * 2 + 1;

// 以层级遍历构造二叉树
const buildTree = (nums: (number | null)[]) => {
  // 控制下标从1开始，只有下标从1开始才满足上述索引计算规则
  const list = [null, ...nums].map(item => {
    if (item === null) {
      return null;
    } else {
      return new TTreeNode<string>(item, `data-${item}`);
    }
  });

  let root: TTreeNode<string> | null = list[1];
  for(let i = 1; i < Math.floor(list.length / 2); i++) {
    list[i].left = list[left(i)];
    list[i].right = list[right(i)];
  }
  return root;
}

const tree = buildTree([
  6,
  4, 9,
  2, 5, 8, 11,
  1, 3, null, null, 7, null, 10, null
]);

binary-tree

2.1 DFS

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    const preOrder = (node: TTreeNode<number>, callback: (val?: TTreeNode<number>) => void) => {
      if (node === null) return node;
      // @Comment: 1⃣️
      if (typeof callback === 'function') {
        callback(node);;
      }
      // @Comment: 2⃣️
      inOrder(node.left, callback);
      // @Comment：3⃣️
      inOrder(node.right, callback);
    }

    递归实现逻辑比较简单，而且变化也比较简单：

    1⃣️2⃣️3⃣️顺序时为先根遍历（preOrder）

    2⃣️1⃣️3⃣️顺序时为中根遍历（inOrder）

    2⃣️3⃣️1⃣️顺序时为后根遍历（postOrder）

  • 非递归实现

    非递归实现上逻辑会比递归麻烦很多，写业务时可能还是比较倾向于使用递归去实现；而写库函数时，为了追求更好的性能，可能还是比较倾向于非递归实现。

    • 先根遍历

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      const preOrder = (root: TTreeNode<number>, callback?: (node?: TTreeNode<number>) => void) => {
        if (root === null) return null;
        const stack = [root];
        while(stack.length > 0) {
          const current = stack.pop();
          if (typeof callback === 'function')
            callback(current);
          if (current.right) stack.push(current.right);
          if (current.left) stack.push(current.left);
        }
      }
      1
      preOrder(node, v => console.log(v.value))

      先根遍历其实与m叉树的dfs没有什么区别，只不过不需要对children遍历压栈，只要将右子节点和左子节点依次压栈即可。

      Output: 6 -> 4 -> 2- > 1 -> 3 -> 5 -> 9 -> 8 -> 7 -> 11 -> 10

    • 中根遍历

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      const inOrder = (root: TTreeNode<number>, callback?: (node?: TTreeNode<number>) => void) => {
        const stack = [];
        let ptr = root;
        // 初始化stack数组，对于ptr节点，只要有左子节点，就一直压栈
        while(ptr) {
          stack.push(ptr);
          ptr = ptr.left;
        }
        while(stack.length) {
          const current = stack.pop();
          if (typeof callback === 'function') {
            callback(current);
          }
          const right = current.right;
          ptr = right;
          while(ptr) {
            stack.push(ptr);
            ptr = ptr.left;
          }
        }
      }

      Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11

    • 后根遍历

      后根遍历的顺序是“左->右->中”，而先根遍历的顺序是“中->左->右”，先根遍历经过简单变体可以变成“中->右->左”，这样就与后根遍历的顺序是反过来的。所以我们可以对节点进行“中->右->左”遍历，然后再逆序一次就可以了。可以使用双栈去解

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      const inOrder = (root: TTreeNode<number>, callback?: (node?: TTreeNode<number>) => void) => {
        const stack = [root];
        const out = [];
        while(stack.length) {
          const current= stack.pop();
          out.push(current);
          if (current.left) stack.push(current.left);
          if (current.right) stack.push(current.right);
        }
        while(out.length) {
          if (typeof callback === 'function') {
            callback(out.pop());
          }
        }
      }

      Output: 1 -> 3 -> 2 -> 5 -> 4 -> 7 -> 8 -> 10 -> 11 -> 9 -> 6