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

发布于
2021-06-18

更新于
2021-06-20

数据源如：

<!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方法處理。。。

javascript 循环嵌套递归遍历遍历json

阅读 3.1k

3 个回答

jsdeferred

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)的时间复杂度

边城

59.8k157274

发布于
2022-06-08

这个问题可以参考我的博文：过滤/筛选树节点 - 第 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;
        }
    });
}

已参与了 SegmentFault 思否社区 10 周年「问答」打卡，欢迎正在阅读的你也加入。

查看全部 3 个回答

被 1 篇内容引用

React父组件刷新导致子组件重新渲染问题
4

推荐问题

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

遇到一道设计模式的面试题，各位大佬看下如何解决,题目要求是优化这段业务代码？

扁平化数组转换成树形?

省市区街道数据在哪里可以下载？

Vue项目一个报错无法找到原因?

如何在JavaScript中从外部中断for循环的执行？

如何在浏览器开发者工具中导入本地JS文件并直接运行？

Quartz如何根据cron表达式计算任务开始前发送通知的时间？

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

遇到一道设计模式的面试题，各位大佬看下如何解决,题目要求是优化这段业务代码？

扁平化数组转换成树形?

省市区街道数据在哪里可以下载？

Vue项目一个报错无法找到原因?

如何在JavaScript中从外部中断for循环的执行？

如何在浏览器开发者工具中导入本地JS文件并直接运行？

Quartz如何根据cron表达式计算任务开始前发送通知的时间？

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