遞歸的幾種場景記錄詳情 - 前端,javascript,遞歸熱飯班長動態日志

場景1：從樹中查找查找符合條件的節點（一個）

const findNodeById = (nodes, id) => {
  // 遍歷當前層的所有數組元素
  for (const node of nodes) {
    // 找到目標節點，直接返回，遞歸結束
    if (node.id === id) {
      // 這裏會有兩種情況：
      // 1. 如果這裏不是在遞歸中，node會作為調用處的返回值，函數結束
      // 2. 如果這裏是在遞歸中，node會作為遞歸調用處的返回值(賦值給foundNode的地方)，當前層的遞歸結束
      return node;
    }

    // 未找到目標節點，如果存在children，則將其作為nodes和原始id一起遞歸調用findNodeById
    if (node.children) {
      const foundNode = findNodeById(node.children, id);

      // 找到目標節點，直接返回，遞歸結束
      if (foundNode) {
        return foundNode;
      }
    }
  }

  // 未目標節點，遞歸結束
  return null;
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
  },
];

const res = findNodeById(tree, '1-1');
console.log(res);
//  {"id":"1-1","name":"營銷體系-南區開發團隊"}

場景2：從樹中查找符合條件的節點（所有）

const getNodes = (nodes) => {
  const nextNodes = [];

  for (const node of nodes) {
    const { children, ...rest } = node;

    if (rest.value > 1) {
      nextNodes.push(rest);
    }

    if (children) {
      // 關鍵代碼，將返回值賦值給children
      nextNodes.push(...getNodes(children));
    }
  }

  // 如果只有一級，這裏返回的就是返回給外部調用處
  // 如果有多級，這裏會返回給nextNodes.push
  return nextNodes;
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    value: 1,
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
        value: 2,
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
    value: 2,
  },
];

const res = getNodes(tree);
console.log(res);
// [{"id":"1-1","name":"營銷體系-南區開發團隊","value":2},{"id":"2","name":"交付體系","value":2}]

優化一下，將識別目標的判斷提取為函數依賴，提高靈活性

const getNodes = (nodes, checkIsTarget) => {
  const nextNodes = [];

  for (const node of nodes) {
    const { children, ...rest } = node;

    if (checkIsTarget(rest)) {
      nextNodes.push(rest);
    }

    if (children) {
      // 關鍵代碼，將返回值賦值給children
      nextNodes.push(...getNodes(children, checkIsTarget));
    }
  }

  // 如果只有一級，這裏返回的就是返回給外部調用處
  // 如果有多級，這裏會返回給nextNodes.push
  return nextNodes;
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    value: 1,
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
        value: 2,
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
    value: 2,
  },
];

const res = getNodes(tree, (node) => node.value > 1);
console.log(res);
// [{"id":"1-1","name":"營銷體系-南區開發團隊","value":2},{"id":"2","name":"交付體系","value":2}]

場景3：修改樹中的指定節點名

修改節點名和修改節點值都可以用這種方式。只不過該方法會修改原始的樹，簡單的處理方式是在傳入前提供tree的副本。（後面會添加不修改原始tree的版本。）

const updateTreeName = (nodes, currKey, targetKey) => {
  for (const node of nodes) {
    // 檢查屬性是否存在，如果存在則添加一個屬性，並且把原始屬性的值賦值給新屬性
    if (node[currKey]) {
      const value = node[currKey];
      node[targetKey] = value;
      delete node[currKey];
    }

    if (node.children) {
      updateTreeName(node.children, currKey, targetKey);
    }
  }
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
  },
];

const res = updateTreeName(tree, 'name', 'title');
console.log(res);
// [{"id":"1","title":"營銷體系","children":[{"id":"1-1","title":"營銷體系-南區開發團隊"}]},{"id":"2","title":"交付體系"}]

場景4：修改樹中的指定節點名（不修改原樹）

const updateTreeName = (nodes, currKey, targetKey) => {
  const nextNodes = [];

  for (const node of nodes) {
    const { children, [currKey]: value, ...rest } = node;

    // 得到原始key的值
    if (currKey in node) {
      rest[targetKey] = value;
    }

    if (children) {
      // 關鍵代碼，將返回值賦值給children
      rest.children = updateTreeName(children, currKey, targetKey);
    }

    nextNodes.push(rest);
  }

  // 如果只有一級，這裏返回的就是返回給外部調用處
  // 如果有多級，這裏返回給children
  return nextNodes;
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
  },
];

const res = updateTreeName(tree, 'name', 'title');
console.log(res);
// [{"id":"1","title":"營銷體系","children":[{"id":"1-1","title":"營銷體系-南區開發團隊"}]},{"id":"2","title":"交付體系"}]

總結

遞歸模式分類：

模式1：不需要返回值遞歸
這類的遞歸很簡單，只需要記得添加一個遞歸調用的條件，然後調用就行。

const recursion = (nodes) => {
  for (const node of nodes) {
    // do whatever you want

    // 添加遞歸的調用條件，然後調用就好
    if (node.children) {
      recursion(node.children);
    }
  }
};

下面給出一個示例，用來修改樹上的節點：

const func = (nodes, updater) => {
  for (const node of nodes) {
    node = updater(node);
    if (node.children) {
      // 要素1：遞歸調用
      func(node.children, updater);
    }
  }
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    value: 1,
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
        value: 2,
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
    value: 2,
  },
];

func(tree, (node) => {
  const { name: title, ...rest } = node;

  // 將name字段更名為title
  return {
    ...rest,
    title,
  };
});

模式2. 獲取樹中符合條件的節點
這個類型的遞歸，相對於上面的，需要注意的地方就多了一點。

創建一個容器來收集目標節點
判斷是否找到目標節點，並且放到容器中
返回目標容器
如果發生了遞歸，則將遞歸的結果也塞到容器中

const getNodes = (nodes) => {
  // (1/4)
  const nextNodes = [];
  for (const node of nodes) {

    // (2/4)
    if (node.id === '1') {
      nextNodes.push(node)
    }

    // (4/4)
    if (node.chidren) {
      nextNodes.push(...getNodes(item.children))
    }
    
  }

  // (3/4)
  return nextNodes;
};

下面給出一個示例，用於從樹中遞歸獲取目標節點集合：

const getNodes = (nodes, isTarget) => {
  const nextNodes = [];

  for (const node of nodes) {
    if (isTarget(node)) {
      nextNodes.push(node);
    }

    if (node.children) {
      nextNodes.push(...getNodes(node.children, isTarget));
    }
  }

  return nextNodes;
};

const tree = [
  {
    id: '1',
    name: '營銷體系',
    value: 1,
    children: [
      {
        id: '1-1',
        name: '營銷體系-南區開發團隊',
        value: 2,
      },
    ],
  },
  {
    id: '2',
    name: '交付體系',
    value: 2,
  },
];

getNodes(tree, (node) => {
  // 識別目標
  return node.value === 2;
});