从数组列表可视化树

Question

给定以下数组输入：

[a, b, d]
[a, b, e]
[a, c, f]
[a, c, g]
[a, c, h]

我想要一个构建树的输出，如下所示：

      a
    /    \
   b      c
  / \   / | \
 d  e  f  g  h

此解决方案应适用于任何数字或数组。

我一直在寻找一个好的工具来实现这一目标，但到目前为止还没有找到任何东西。我查看了 https://pypi.org/project/treebuilder/ 和 https://www.jstree.com/ 但都不满足这些要求。我想我会自己写，但想看看是否有人有任何聪明的解决方案、建议或关于如何做到这一点的意见。我猜这类事情的最佳解决方案将是用 Python 或 JavaScript 编写的东西，因此标记这些语言，但我对任何语言的解决方案持开放态度

Answer 1

输入/输出表明树有点像特里树，即父节点具有由其标签唯一标识的子节点，并且可能有多个顶级节点，由未渲染的（超级）根节点连接在一起.

因此，我们可以首先使用对象属性（Python 中的字典键）构建这样的树数据结构，就像在 attempts 中所做的那样，但没有“词尾”概念。

然后从该数据结构我们可以生成文本输出。在这里，我们将执行深度优先迭代（后序），其中兄弟树的字符串表示形式逐行“合并”。

这是 JavaScript 中的实现：

class TrieNode {
    static PADDING = 2 // Space between horiztonally adjacent node labels
    addPath([key, ...path]) {
        if (key === undefined) return;
        if (!Object.hasOwn(this, key)) this[key] = new TrieNode;
        this[key].addPath(path);
    }
    toString() {
        const prefixAll = (lines, count) => lines.forEach((line, i) => lines[i] = " ".repeat(count) + line);

        function buildLines(node) {
            let lines = [];
            for (const [key, child] of Object.entries(node)) {
                let childLines = buildLines(child);
                let width = childLines.reduce((acc, {length}) => Math.max(acc, length), 0);
                // Ensure there is enough width to fit the key
                if (key.length > width) {
                    prefixAll(childLines, (key.length - width) >> 1)
                    width = key.length;
                }
                // Determine position for key
                const i = (1 + childLines[0]?.search(/[┤├┼│┴]/)) || (key.length + 1) >> 1;
                // Add line with the key and a line with a temporary edge on top of this key
                childLines.unshift("┬".padStart(i), key.padStart(i + (key.length >> 1)));
                // Accumuate this subtree with previous sibling subtrees:
                // Calcuate horizontal offset of this subtree
                let x = Math.max(...childLines.slice(0, lines.length).map((line, i) =>                 
                    lines[i].length + TrieNode.PADDING - (line + ".").search(/\S/)
                ));
                if (x < 0) { // Make room at left side of partial tree if needed
                    prefixAll(lines, -x);
                    x = 0;
                }
                // Merge next subtree at the right side of the partial tree
                childLines.forEach((line, i) =>
                    lines[i] = line.replace(/^\s*/, m => (lines[i] ?? "").padEnd(x + m.length))
                );
            }
            // Connect the subtrees with a horizontal branch, towards a single upward branch
            if (!lines.length) return lines;
            let top = lines[0];
            const i = (top.length - 1 + top.indexOf("┬")) >> 1;
            top = top.replace(/(?<=┬)\s+(?=┬)/g, m => "─".repeat(m.length))
                      .replace("┬", "┌")
                      .replace(/┌$/, "│")
                      .replace(/┬$/, "┐");
            lines[0] = top.slice(0, i) + "┤├┼│┴"["┐┌┬│─".indexOf(top[i])] + top.slice(i + 1);
            return lines;
        }
        
        const lines = buildLines(this);
        if (lines[0].includes("│")) lines.shift(); // If top-level has just one node
        return lines.join("\n");
    }
}

let trie = new TrieNode();
let paths = [
    ["aaa", "cccccc", "ffff","ooooo"],
    ["aaa", "cccccc", "ffff","ppppp", "qqqqq"],
    ["aaa", "cccccc", "ffff","ppppp", "rrrrrr"],
    ["aaa", "cccccc", "ffff","ppppp", "ssssss"],
    ["aaa", "cccccc", "gggggg"],
    ["aaa", "cccccc", "hhh"],
    ["aaa", "bbbb", "ddd"],
    ["aaa", "bbbb", "eeeee", "iiiiiii"],
    ["aaa", "bbbb", "eeeee", "jjj", "s", "tttttttttttttttttttttttttttttttttttttttttttttttttttttttttt"],
    ["aaa", "bbbb", "eeeee", "kkk"],
    ["aaa", "bbbb", "eeeee", "lll"],
    ["aaa", "bbbb", "eeeee", "mmm"],
    ["other_root"]
];
// Load the paths into the trie:
for (const path of paths) trie.addPath(path);
console.log(trie.toString());

摆弄琴弦有点麻烦。我希望评论能澄清正在发生的事情。

Answer 2

请看看这个很棒的工具 https://eniac00.github.io/btv/