时间戳

首页 > 解决方案 > Javascript：当用户从树中选择/取消选择节点时如何保留树结构和祖父母关系

javascript - Javascript：当用户从树中选择/取消选择节点时如何保留树结构和祖父母关系

问题描述

我有一个树结构{name, [children]}（JS 对象）。用户可以任意选择任何节点以部分复制结构（复制到 JS 对象数组中，因为可以选择松散叶节点）。例如，用户可以选择一个叶节点，但不能选择它的父/祖父，那么叶节点将只是位于children最高父级的平面数组中。

例子：

original (JS Object)      selected
   A✓                       A
   |  \ \                  / \
   B✓ C D✓                B  D
  / \          =>         / \
 E✓  F                   E  G
     |
     G✓ 

original                  selected(Array of JS objects)
   A                       B, D      
   |  \ \                 / \
   B✓ C D✓               E  G 
  / \          =>         
 E✓  F                   
     |
     G✓

我的第一个想法是：对于单击的每个节点，假设我们维护一个selected数组：

  1. 如果此节点位于selected=> 取消选择（相当直接）：

    1。如果节点是“顶级”元素 => 将其从数组中删除，并将其子节点推送到数组中。

    a2。如果节点是顶级元素的（大）子节点 => 从其父节点的子节点中删除该节点，并将该节点的子节点重新附加到其父节点。

  2. 如果此节点不在selected=> select 中（发生奇怪的事情）：

    一个。tempNode用空初始化 a children，因为我们还不知道它的孩子

    湾。如果这个节点有（大）孩子=>对于每个（大）孩子，如果（大）孩子在selected=>删除（大）孩子selected=>将此（大）孩子添加到tempNode's children（应该是递归的对于多个级别）

    c1。如果该节点的（大）父节点selected已经存在 => 将其附加tempNode到（大）父节点（对于多个级别应该是递归的）

    c2。如果该节点的（祖）父节点不在 中selected，则将其推送到数组中。

我主要停留在步骤 2b 和 2c 上。

//for adding node into selected
const addChildInSelected = (child) => {
    var tempNode = {
        name: child.name,
        children: []
    }
    var clonedState = clone(selected)
    var childInTree = findChildInTree(child.id, props.data)
    //if the child has children, check if they are in selected yet.
    if (childInTree.children.length > 0) {
        //Problem 1: I should run this recursively for all the grandchildren, 
        //but I struggle to find the base case. But recursion might not be the best solution
        for (var i = 0; i < childInTree.children.length; i++) {
            //Problem 2: findChildInSelected/removeChildInSelect are all recursive calls as well,
            //due to the tree structure. very worried about stack overflow during this step...
            var grandChildInSelected = findChildInSelected(childInTree.children[i].id)
            if (grandChildInSelected !== null) {
                clonedState = removeChildInSelected(clonedState)
                tempNode.children.push(findChildInTree(childInTree.children[i]))
            }
        }
    }
    //Problem 3. I realized I needed to check for each node in the `selected` again. 
    //another potential performance hurdle
}

现在我重新考虑这个问题，每个节点只关心它自己、它的直接父/祖父以及它的所有子/孙子作为一个平面数组。这可能是研究这个问题的一个很好的视角。也许找到父母/祖父母或所有孩子的辅助功能将是一个好的开始。（另外我意识到在几个功能中我忘记检查祖父母......）

但是由于我使用多个树结构进行操作，所以下面的函数似乎并不理想......

//just a quick example
const findDescendantsInSelected = (node, descendants=[]) => {
    //recursive call within recursive function which could overflow if the tree is big
    if (findNodeInSelected(node) !== null) {
        descendents.push(node)
    }
    if (node.children.length > 0) {
        for (var i = 0; i < entry.children.length; i++) {
            result = findDescendantsInSelected(node.children[i], descendants);
        }
        return result
    }
    return descendents
}

总而言之，维护几乎 3 个独立的树（选择状态、原始数据和每个步骤的克隆，因为我使用了 react）并在每个步骤中跟踪父母/孩子，跨越不同的功能让我很头疼。任何有关如何简化问题的见解将不胜感激！

标签： javascripttree

解决方案

一个使用深度优先遍历的简单纯递归函数就足够了。它返回您想要的选定树的列表（称为森林）。如果选择了一个节点，它将收集所有选定的后代树并返回一个以这些为子节点的新节点。如果未选择该节点，它只会加入其子节点的列表并返回该列表。

function selectedForest(node) {
    const trees = node.children.flatMap(selectedForest);
    return isSelected(node) ? [ {...node, children: trees} ] : trees;
}

演示：

const demo = { name: "A", children: [
  { name: "B", children: [
    { name: "E", children: [] },
    { name: "F", children: [
      { name: "G", children: [] },
    ] },
  ] },
  { name: "C", children: [] },
  { name: "D", children: [] },
] };
let selection;
function isSelected({name}) {
  return selection.has(name);
}
function selectedForest(node) {
  const trees = node.children.flatMap(selectedForest);
  return isSelected(node) ? [ {...node, children: trees} ] : trees;
}

selection = new Set("ABDEG");
console.log(JSON.stringify(selectedForest(demo), null, 2));
selection = new Set("BDEG");
console.log(JSON.stringify(selectedForest(demo), null, 2));

推荐阅读