用于构建类似 object 层次结构的树的递归方法无法按预期工作

Question

我正在尝试编写类似这样的功能：

输入：

['A', '-B1', '--B2', '-C1', 'D']

输出：

{'A': {'B1': {'B2': {}}, 'C1': {}}, 'D': {}}

如您所见，B1 和 C1 是 A 的 children，B2 是 B1 的 child。它可以根据 -

嵌套到任何级别

我为此编写了一个 Javascript 代码，但在创建 children 时似乎有问题。这是我的代码：

function fetch_levels(li, chr='-') {
    var res_list = []
    for (i=0; i<li.length; i++) {
        item = li[i]
        level = item.length - item.replace(RegExp(`^${chr}+`), '').length
        key = item.replace(RegExp(`^${chr}+`), '')
        value = {}
        res_list.push({
            level: level,
            name: key,
            value: value
        })
    }
    return res_list
}

function ttree_to_json(ttree, level=0) {
    result = {}
    for (i = 0; i < ttree.length; i++) {
        cn = ttree[i]
        nn = ttree[i+1] || {'level': -1}

        // Edge cases
        if (cn['level'] > level) {
            continue
        }
        if (cn['level'] < level) {
            return result
        }

        // Recursion
        if (nn['level'] == level) {
            result[cn['name']] = cn['value']
        } else if (nn['level'] > level) {
            rr = ttree_to_json(ttree.slice(i+1), level=nn['level'])
            result[cn['name']] = rr
        }
        else {
            result[cn['name']] = cn['value']
            return result
        }
    }
    return result
}

调用函数的方式如下：

console.log(ttree_to_json(fetch_levels(['A', '-B1', '--B2', '-C', 'D'])))

我得到的输出是这样的：

Object { B2: {…}, C: {} }

这是错误的。

谁能帮我弄清楚 JavaScript 代码有什么问题？

解决方案的灵感来自提到的示例代码here:

编辑（2022 年 5 月 11 日）

我的错我没有给出实际问题。为了使问题更简短和准确，我给出了不同的数据结构。此处给出的所有答案都适用于上述 DS。但是我无法使我的实际 DS 获得所需的输出。

这里是实际输入：

[
    {
        "componentId": "1067256",
        "componentName": "Readiness",
        "shortHandName": "GTM"
    },
    {
        "componentId": "1067343",
        "componentName": "-Business Planning and Commercialization - BPC",
        "shortHandName": "BPC"
    },
    {
        "componentId": "1068213",
        "componentName": "-SKU Life Cycle Management (SLM)",
        "shortHandName": "SLM"
    },
    {
        "componentId": "1068210",
        "componentName": "--Partner Programs",
        "shortHandName": "Partner"
    },
    {
        "componentId": "1067317",
        "componentName": "--Activation",
        "shortHandName": "Activation"
    },
    {
        "componentId": "1067346",
        "componentName": "Sales Compensation",
        "shortHandName": "Sales Comp"
    }
]

预期输出：

{
    "GTM": {
        "componentId": "1067256",
        "componentName": "Readiness",
        "shortHandName": "GTM",
        "children": {
            "BPC": {
                "componentId": "1067343",
                "componentName": "Business Planning and Commercialization - BPC",
                "shortHandName": "BPC",
                "children": {
                    "Partner": {
                        "componentId": "1068210",
                        "componentName": "Partner Programs",
                        "shortHandName": "Partner",
                        "children": {}
                    },
                    "Activation": {
                        "componentId": "1067317",
                        "componentName": "Activation",
                        "shortHandName": "Activation",
                        "children": {}
                    }
                }
            },
            "SLM": {
                "componentId": "1068213",
                "componentName": "SKU Life Cycle Management (SLM)",
                "shortHandName": "SLM",
                "children": {}
            }
        }
    },
    "Sales Comp": {
        "componentId": "1067346",
        "componentName": "Sales Compensation",
        "shortHandName": "Sales Comp",
        "children": {}
    }
}

解释：

使用 componentName parent 和 child 关系（或级别）是基于 - 决定的，可以进入任何嵌套级别。
shortHandName 用作键，值为 object 应包含所有属性，包括新添加的属性 children
children 将具有相同的结构，最低级别 child 将具有 {} 与 children.

对我来说，很难理解所有的答案，所以可以让它们适用于我提到的新 DS。

Answer 1

您可以通过为嵌套对象的级别引用获取一个数组来简化代码。

任何属性都被分配到给定的级别（破折号的数量），并将对象带到下一个级别。

const
    data = ['A', '-B1', '--B2', '-C1', 'D'],
    result = {},
    levels = [result];
    
data.forEach(s => {
    let level = 0;
    while (s[level] === '-') level++;
    s = s.slice(level);
    levels[level][s] = levels[level + 1] = {};
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

现实世界问题的解决方案

const
    data = [{ componentId: "1067256", componentName: "Readiness", shortHandName: "GTM" }, { componentId: "1067343", componentName: "-Business Planning and Commercialization - BPC", shortHandName: "BPC" }, { componentId: "1068213", componentName: "-SKU Life Cycle Management (SLM)", shortHandName: "SLM" }, { componentId: "1068210", componentName: "--Partner Programs", shortHandName: "Partner" }, { componentId: "1067317", componentName: "--Activation", shortHandName: "Activation" }, { componentId: "1067346", componentName: "Sales Compensation", shortHandName: "Sales Comp" }],
    getLevelString = (string, level = 0) => string[0] === '-'
        ? getLevelString(string.slice(1), level + 1)
        : { level, string },
    result = data
        .reduce((levels, o) => {
            const { level, string: componentName } = getLevelString(o.componentName);
            levels[level][o.shortHandName] = { ...o, componentName, children: levels[level + 1] = {} };
            return levels;
        }, [{}])
        [0];

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

不需要递归。由于有关要添加的（下一个）嵌套级别的唯一可靠信息是由破折号计数携带的，因此无论如何都可以将下一个级别添加到最近处理的 previous/lower 级别的对象引用中。

因此，以数组形式查找，通过其索引引用每个最近创建的 level/branch 是基于简单循环的解决方案所需的一切。

下一个提供的实现使用基于 reduce 的方法。

function aggregateObjectHierarchyLevel(
  { recentLevels, result = {} },
  item,
  idx,
) {
  // handle/synchronize the initial `result` reference.
  if (idx === 0) {
    recentLevels = [result];
  }
  const [_, dashes = '', key = ''] = item.match(/^([-]*)(.*)/) ?? [];
  const level = dashes.length;

  recentLevels[level + 1] = recentLevels[level][key] = {};

  return { recentLevels, result };
};


console.log(
  ['A', '-B1', '--B2', '-C1', 'D']
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
)
console.log(
  ['A', '-B1', '--B2', '---B3', '-C1', 'D']
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
)
console.log(
  ['A', '-B1', '--B2', '---B3', '--C2', '---C3', '-D1', 'E']
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
)

.as-console-wrapper { min-height: 100%!important; top: 0; }

编辑 ...由于OP的真实世界数据变化

根据我上面的评论...

"@SauravKumar ... from what the OP was presenting before (and the base problem / hierarchy does not change) the expected output of what the OP refers to as "the actual input" does not match the basic building pattern. '--Partner Programs' and '--Activation' have to be the children of '-SKU Life Cycle Management (SLM)' and not of '-Business Planning and Commercialization - BPC'. If the OP wants the expected output, the input array needs to be changed to the two former mentioned child items become direct followers of the latter (parent) item."

update/refactoring从上面的代码到下一个提供的代码只用了 3 分钟，这证明了第一种方法的稳健性。

reducer 函数中的唯一变化是由于必要的对象解构和对象 re/assembling。无需更改任何时候的主要方法。

function aggregateObjectHierarchyLevel(
  { recentLevels, result = {} },
  { shortHandName, componentName: name , ...itemEntriesRest },
  idx,
) {
  // handle/synchronize the initial `result` reference.
  if (idx === 0) {
    recentLevels = [result];
  }
  const [_, dashes = '', componentName = ''] = name.match(/^([-]*)(.*)/) ?? [];
  const level = dashes.length;

  recentLevels[level][shortHandName] = {
    shortHandName,
    componentName,
    ...itemEntriesRest,
    children: recentLevels[level + 1] = {},
  };
  return { recentLevels, result };
};

const data = [
  { componentId: "1067256", componentName: "Readiness", shortHandName: "GTM" },
  { componentId: "1067343", componentName: "-Business Planning and Commercialization - BPC", shortHandName: "BPC" },
  { componentId: "1068213", componentName: "-SKU Life Cycle Management (SLM)", shortHandName: "SLM" },
  { componentId: "1068210", componentName: "--Partner Programs", shortHandName: "Partner" },
  { componentId: "1067317", componentName: "--Activation", shortHandName: "Activation" },
  { componentId: "1067346", componentName: "Sales Compensation", shortHandName: "Sales Comp" }
];

console.log(
  data
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Answer 3

另一个版本，在设计上与 Peter 和 Nina 的非常相似，但编码风格不同，如下所示：

const nest = (strings, result = {}) => strings .reduce (
  (levels, str, _, __, [___, hyphens, val] = str .match (/(\-*)(.+)/), lvl = hyphens .length) => (
    (levels [lvl] [val] = levels [lvl + 1] = {}), 
    levels
  ), [result]
) [0]

console .log (nest (['A', '-B1', '--B2', '-C1', 'D']))

我们使用与这两个答案相同的嵌套结构，并使用与 Peter 类似的正则表达式来分隔字符串的两个部分，以及与这两个答案相同的更新逻辑。这里我们在 .reduce 调用中执行此操作，仅修改隐藏的累加器。

我独立于那些写了这篇文章，回来后发现已经有两个很好的答案，但我认为这已经足够不同了，所以也可以包括在内。（我还修复了它以窃取 Peter 对正则表达式 match 调用的解构。比我原来的 .slice (1, 3)-then-destructure 方法好多了！）

有趣的是，三种截然不同的编码风格都使用相同的基本设计来解决问题！[=17=]

更新

此版本处理问题中的更新要求。将来，有了那么大的变化，请简单地开始第二个问题，并包括一个 link 回到原来的上下文。（您可能仍想这样做，因为新问题会受到更多关注。）

const nest = (input, result = {children: {}}) => input .reduce ((
  levels, 
  {componentId, componentName, shortHandName}, 
   _, __, [___, hyphens, val] = componentName .match (/(\-*)(.+)/), lvl = hyphens .length
) => (
  (levels [lvl] .children [shortHandName] = levels [lvl + 1] = {
    componentId, componentName: val, shortHandName, children: {}
  }), 
  levels
), [result]) [0] .children

const input = [{componentId: "1067256", componentName: "Readiness", shortHandName: "GTM"}, {componentId: "1067343", componentName: "-Business Planning and Commercialization - BPC", shortHandName: "BPC"}, {componentId: "1068213", componentName: "-SKU Life Cycle Management (SLM)", shortHandName: "SLM"}, {componentId: "1068210", componentName: "--Partner Programs", shortHandName: "Partner"}, {componentId: "1067317", componentName: "--Activation", shortHandName: "Activation"}, {componentId: "1067346", componentName: "Sales Compensation", shortHandName: "Sales Comp"}]

console .log (nest (input))

.as-console-wrapper {max-height: 100% !important; top: 0}

请注意，这与您的目标输出不匹配，将 Partner 和 Activation 嵌套在 SLM 中，而不是 BPC 中。但考虑到输入数据，这似乎是正确的。如果您想切换它，那么 SLM 必须在输入数组中稍后出现。

关于设计就不用多说了。它与上面的设计完全相同，只是有更多的字段，包括嵌套的 children 一个。

用于构建类似 object 层次结构的树的递归方法无法按预期工作

Recursive approach for building a tree like object hierarchy does not work as expected

javascript

recursion

tree

iteration

tail-recursion

编辑（2022 年 5 月 11 日）

更新