求教：js递归树结构输出问题

发布于 2022-09-13 00:14:01 字数 2400 浏览 30 评论 0

数据源如：

<!DOCtype html>
<html lang="en-US">
<head>
    <title>demo</title>
</head>
<body>
  <script>
    const json = [
  {
      "id":4,
      "name":"标题1",
      "flag":0,
      "parentId":1,
      "children":[
          {
              "id":3,
              "name":"1-1",
              "flag":0,
              "parentId":4,
              "isLeaf": true,
              "children":null
          }
      ]
  },
  {
      "id":5,
      "name":"标题2",
      "flag":0,
      "parentId":1,
      "children":[
          {
              "id":4,
              "name":"2-1",
              "flag":0,
              "parentId":5,
              "isLeaf": true,
              "children":null
          },
          {
              "id":5,
              "name":"2-2",
              "flag":0,
              "parentId":5,
              "checked":true,
              "isLeaf": true,
              "children":null
          }
      ]
  },
  {
      "id":7,
      "name":"标题3",
      "flag":0,
      "parentId":1,
      "children":[
          {
              "id":6,
              "name":"3-1",
              "flag":0,
              "parentId":7,
              "children":[
                {
                  "id": 106,
                  "name": "3-1-1",
                  "checked": true,
                  "isLeaf": true,
                  "children": null,
                }
              ]
          }
      ]
  }
];
  function returnSelectedTree(list) {
    if (Array.isArray(list) && list.length !== 0) {
      list = list.map((item, index) => {
        // 哪裏有問題
        const children = !item.isLeaf ? item.children.filter(it => it.checked) : [];
        if (children.length > 0) {
          item = {...item, ...{children: children}};
        }
        if (!item.isLeaf) {
          returnSelectedTree(item.children)
        }
        return item;
      });
      return list;
    } else {
      return false;
    }
  }
  returnSelectedTree(json)
  console.log(returnSelectedTree(json));
</script>
</body>
</html>

选中子级别，将其父级输出，如图

选中2-2，输出标题2的完整树结构，除过2-1；求N层级方法
即：排除未选择项，需要父级完整结构包含选择项。

想通過上面returnSelectedTree方法處理。。。

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

迷鸟归林 2022-09-20 00:14:01

type TreeNode = {
  id: number
  name: string
  flag: number
  parentId: number
  children: null | TreeNode[]
}

type TreeNodeWithExtraInfo = TreeNode & {
  __parent: TreeNodeWithExtraInfo | null
  __bitset: 0 | 1
  __subtreeBitSet: 0 | 1
  children: TreeNodeWithExtraInfo[] | null
}
type ID = number

const temp: TreeNode[] = [
  {
    id: 4,
    name: '标题1',
    flag: 0,
    parentId: 1,
    children: [{ id: 3, name: '1-12', flag: 0, parentId: 4, children: null }],
  },
  {
    id: 5,
    name: '标题2',
    flag: 0,
    parentId: 1,
    children: [
      { id: 4, name: '2-1', flag: 0, parentId: 5, children: null },
      { id: 6, name: '2-2', flag: 0, parentId: 5, children: null },
    ],
  },
  {
    id: 7,
    name: '标题3',
    flag: 0,
    parentId: 1,
    children: [
      { id: 8, name: '3-1', flag: 0, parentId: 7, children: null },
      { id: 9, name: '3-2', flag: 0, parentId: 7, children: null },
      { id: 10, name: '3-3', flag: 0, parentId: 7, children: null },
    ],
  },
]

const getSelectedSubtree = (nodes: TreeNode[], ids: ID[]): TreeNode[] => {
  const dummyRoot: TreeNodeWithExtraInfo = {
    children: nodes,
  } as any
  const idToNodeMap = new Map<ID, TreeNodeWithExtraInfo>()
  const ans: TreeNode = {
    children: [],
  } as any

  const proprocessNodes = (
    root: TreeNodeWithExtraInfo,
    parent: null | TreeNodeWithExtraInfo
  ): void => {
    if (parent) {
      root.__parent = parent
    }

    const children = root.children
    idToNodeMap.set(root.id, root)

    if (!children) return

    for (const node of children) {
      proprocessNodes(node, root)
    }
  }

  const markFlagFromSelectedNodeToRoot = (id: ID): void => {
    let node = idToNodeMap.get(id)!

    if (!node) {
      throw new Error('Not Implement')
    }

    let parent = node.__parent
    node.__bitset = 1

    while (parent) {
      parent.__subtreeBitSet |= node.__bitset | node.__subtreeBitSet

      node = parent
      parent = parent.__parent
    }
  }

  const bubbleProperties = (ids: ID[]) => {
    for (const id of ids) {
      markFlagFromSelectedNodeToRoot(id)
    }
  }

  const removeFlags = (node: TreeNodeWithExtraInfo): void => {
    node.__bitset = 0
    node.__subtreeBitSet = 0
  }

  const includeSomeFlags = (node: TreeNodeWithExtraInfo): boolean => {
    return (node.__bitset | node.__subtreeBitSet) !== 0
  }

  const dfs = (current: TreeNodeWithExtraInfo, workInProgress: TreeNode) => {
    if (!includeSomeFlags(current)) {
      return
    }

    const children = current.children

    if (!children) return

    for (const node of children) {
      const newNode: TreeNode = {
        ...node,
        children: [],
      }
      if (includeSomeFlags(node)) {
        workInProgress.children!.push(newNode)
        if (node.__subtreeBitSet) {
          dfs(node, newNode)
        }
      }
    }

    removeFlags(current)
  }

  proprocessNodes(dummyRoot, null)
  bubbleProperties(ids)
  dfs(dummyRoot, ans)

  return ans.children!
}

console.log(getSelectedSubtree(temp, [5, 10]))

可根据自己的业务逻辑添加二次查找时的优化逻辑以减少每次查询时预处理节点的逻辑的O(N)的时间复杂度

回复收藏 0

以歌曲疗慰 2022-09-20 00:14:01

试试这个？https://github.com/Lushenggan...

回复收藏 0

风苍溪 2022-09-20 00:14:01

这个问题可以参考我的博文：过滤/筛选树节点 - 第 2 节

参考写出来的代码：

function returnSelectedTree(list) {
    // 如果传入的 list 是空的（包含 null, undefined 和 empty），不用处理，直接返回
    if (!list?.length) { return list; }

    // 然后按一定条件进行过滤，
    // 这个条件就是自己是 checked 或者包含 chekced 的子节点
    return list.filter(node => {
        // 先递归找出符合条件的子树
        const children = returnSelectedTree(node.children);
        
        // 如果有，或者当前节点就符合条件，那需要返回当前节点
        // 不过返回前需要先处理 children，用过滤后的那个
        if (node.checked || children?.length) {
            node.children = children;
            return true;
        }
    });
}