遍历树结构

发表于
一般来说，递归都是可以用迭代来实现的。深度优先使用栈，广度优先使用队列。

用递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
interface TreeNode {
  code: string;
  children?: TreeNode[];
  [key: string]: any; // 允许其他属性
}

function transformTree(nodes: TreeNode[]): void {
  nodes.forEach(node => {
    node.value = node.code;
    delete node.code;

    if (node.children?.length) {
      transformTree(node.children);
    }
  });
}

深度优先迭代

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
interface TreeNode {
  code?: string;
  value?: string;
  children?: TreeNode[];
  [key: string]: any;
}

function transformTreeDFS(tree: TreeNode[]): TreeNode[] {
  const stack: TreeNode[] = [...tree];
  
  while (stack.length) {
    const node = stack.pop()!;
    
    if (node.code !== undefined) {
      node.value = node.code;
      delete node.code;
    }
    
    if (node.children?.length) {
      // 从右向左压入栈，这样出栈时就是从左向右处理
      // 也可以这么做 stack.push(...node.children.reverse());
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
  
  return tree;
}

广度优先迭代

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
/**
 * 迭代遍历树（广度优先），原地修改字段，使用队列结构
 */
interface TreeNode {
  code?: string;
  value?: string;
  children?: TreeNode[];
  [key: string]: any;
}

function transformTreeBFS(tree: TreeNode[]): TreeNode[] {
  const queue: TreeNode[] = [...tree];
  
  while (queue.length) {
    const node = queue.shift()!;
    
    if (node.code !== undefined) {
      node.value = node.code;
      delete node.code;
    }
    
    if (node.children?.length) {
      queue.push(...node.children);
    }
  }
  
  return tree;
}