来个 js 算法大佬快来看看这个递归~

Question

var arr = [
  {
    id: '1',
    children: [
      {
        pid: 1,
        id: '1_1',
        children: [
          {
            pid: '1_1',
            id: '1_1_1',
            children: []
          }
        ]
      },
      {
        pid: 1,
        id: '1_2',
        children: [
          {
            pid: '1_2',
            id: '1_2_1',
            children: [
              { pid: '1_2_1', id: '1_2_1_1' },
              { pid: '1_2_1', id: '1_2_1_2' },
              { pid: '1_2_1', id: '1_2_1_3' }
            ]
          }
        ]
      },
      {
        pid: 1,
        id: '1_3',
        children: [
          {
            pid: '1_3',
            id: '1_3_1',
            children: []
          }
        ]
      },
      {
        pid: 1,
        id: '1_4',
        children: [
          {
            pid: '1_4',
            id: '1_4_1',
            children: []
          }
        ]
      }
    ]
  }
]
function getDataTree(arr, target) {
  let res = null
  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    const { id, children } = item
    if (target === id) {
      return item
    } else if (children?.length) {
      res = getDataTree(children, target)
      if (res) break
    }
  }
  return res
}
const res = getDataTree(arr, '1_3_1')
console.log('res: ', res)

目前只能获取到 指定 id 的当前 node 和 子节点,
请问怎么获取它的完成的父节点 和 当前节点 以及 子节点?

也就是

[
  {
    id: '1',
    children: [
      {
        pid: 1,
        id: '1_3',
        children: [
          {
            pid: '1_3',
            id: '1_3_1',
            children: []
          }
        ]
      }
    ]
  }
]

进阶一下:如果没有 pid 是否能获取到父节点?

Answer 1

function getDataTree(arr, target) {
    let res = null
    for (let i = 0; i < arr.length; i++) {
        const item = arr[i]
        const { id, children } = item
        if (target === id) {
            return item
        } else if (children?.length) {
            res = getDataTree(children, target)
            if (res) {
                return {
                    ...(item.pid && {
                        pid: item.pid
                    }), // 没 pid 就把这个删了
                    id: id,
                    children: [res]
                }
            }
        }
    }
    return res
}

pid 其实没有用，冗余信息。

Answer 2

第一种方法，先遍历，建立映射表，然后尽管查就好了

function prepareData(arr) {
    const nodes = goThrough({}, arr);

    function getNode(id) {
        return nodes[id];
    }

    function getPath(id) {
        const path = [];
        let current = nodes[id];
        while (current) {
            path.unshift(current);
            current = nodes[current.pid];
        }
        return path;
    }

    function goThrough(map, nodes) {
        nodes.forEach(node => {
            map[node.id] = node;
            if (node?.children?.length) {
                goThrough(map, node.children);
            }
        });

        return map;
    }

    return { getNode, getPath };
}

const { getNode, getPath } = prepareData(arr);

const path = getPath("1_3_1");
console.log(path.map(node => node.id));

const oneNode = getNode("1_2_1");
console.log(oneNode.id, oneNode?.children?.map(node => node.id));

这里是封装了两个闭包函数出来，是比较简化的做法。看起来正式一点的做法是封装一个类，通过实例方法来实现功能。先自己研究，如果需要我可以后面来补充这个类。

上面这种方法适合对一棵树的数据进行多次处理。但如果只是处理一次，也可以只遍历一次，直接拿到遍历结果（好像就是 @fefe 的方法）。这种方法是直接遍历，不需要 pid。

function getPath(nodes, targetId) {
    const target = nodes.find(node => node.id === targetId);
    if (target) {
        return [target];
    }
    for (const node of nodes) {
        if (!node.children?.length) { continue; }
        const path = getPath(node.children, targetId);
        if (path) {
            path.unshift(node);
            return path;
        }
    }
}
const path = getPath(arr, "1_2_1");
console.log("path: ", path.map(node => node.id));
const node = path[path.length - 1];
console.log(node.id, node.children?.map(it => it.id));

从代码来看，建立映射表，利用 pid，逻辑会比较简单一些。

Answer 3

function getDataTree(arr, target) {
    const ret = {};
    for (const node of find(arr, target)) {
        if (!ret.targetNode) {
            ret.targetNode = node;
            ret.children = node.children;
        } else {
            node.children = [ret.parentNode];
        }
        ret.parentNode = node;
    }
    if (ret.parentNode && Array.isArray(arr)) {
        ret.parentNode = [ret.parentNode];
    }
    return ret;
    function* find(tree, id, nodes = []) {
        if (Array.isArray(tree)) {
            for (const node of tree) {
                yield* find(node, id, nodes);
            }
        } else if (typeof tree === "object" && tree) {
            nodes = [{ ...tree }, ...nodes];
            if (tree.id === id) {
                yield* nodes;
            } else if (tree?.children?.length) {
                yield* find(tree.children, id, nodes);
            }
        }
    }
}
console.dir(getDataTree(arr, "1_3_1"));
console.dir(getDataTree(arr[0], "1_3_1"));