主页 / coding / 问题 / 79166104
Accepted
Gigi Bayte 2
Asked: 2024-11-07 18:54:36 +0800 CST

具有从左到右路径的树（节点）数据结构的字符串表示

  • 772

给定一个树状节点数据结构，每个节点都具有children包含从左到右的子节点的属性，我希望创建此数据结构的字符串表示，使得表示从左到右的每个“垂直列”都是通向叶节点的路径。第一列将是最左边的路径，最后一列将是最右边的路径。

例如，这里有一个例子，说明每个节点的表示形式是单个字符的情况：

示例 1：

Root
├─T
├─E
├─S
├─T─────────┬───┐
├─N─┬───┐   ├─V ├─W
├─A ├─E ├─I ├─A ├─O
├─S ├─X ├─C ├─L ├─W─┐
├─T └─T └─E ├─U ├─H ├─T
└─Y         └─E ├─U ├─H
                └─H ├─I
                    ├─S
                    ├─I
                    ├─S
                    ├─L
                    ├─O
                    ├─N
                    └─G

以下是每个节点的字符串表示形式较长的字符串的情况：

示例 2：

Root
├─Apple─────────┐
├─Banana─┐      ├─Elderberry─┬───────┐
└─Cherry └─Date └─Fig        └─Grape └─Hazelnut

鉴于上述字符串表示中的每一行都代表树的一个级别（位于特定高度），我以为 BFS 是创建字符串表示的方法。

但是，从上面的示例可以看出，情况似乎并不那么简单，因为该线取决于当前节点左侧的节点及其字符串表示的长度。因此，我的想法是，您可能必须以某种方式将 BFS 与 DFS 结合起来，以考虑当前节点左侧的子节点数量。但是，我正在努力弄清楚如何做到这一点。

这不是一个特定于语言的问题，因为我正在寻找一种可以适用于我选择的语言的通用算法。不过，我希望算法尽可能高效。此外，请假设树节点是不可变的，因此无法修改以存储此算法的附加信息。

algorithm

1 个回答

  1. Best Answer

    正如您所指出的，使用 BFS 时，您缺少来自更深层次的间隔信息​​。因此，DFS 似乎是更自然的候选者，因为这样您就可以让该信息从递归中浮现出来。

    以下是 JavaScript 中的一种可能实现。下面的脚本包括创建两个示例树并在控制台中打印结果。

    class Node {
    constructor(value, ...children) {
        this.value = value;
        this.children = children;
    }
}

///// Utility functions to work with arrays of strings ///////

function widthOf(lines) { // Length of the longest string in the array
    return Math.max(...lines.map(line => line.length));
}

function mergeLines(a, width, b) {
    // The strings in the first array (a) get extended with those of the second array (b)
    // If b has more strings than a, then strings are added to a so to match its length
    // When concatenating strings from a and b, the strings from a are first padded with spaces
    // so that all strings from b start at the same offset
    for (let i = 0; i < b.length; i++) {
        if (i === a.length) a.push("");
        a[i] = a[i].padEnd(width) + b[i];
    }
}

////// Main algorithm ///////

function toLines(root) {
    // Returns an array of one-line strings. It is for the caller to concatenate them with newline separators.
    let label = root.value.toString();
    if (root.children.length == 0) return ["└─" + label];
    let topLine = "├─" + label;
    let split = "─";
    let minWidth = topLine.length;
    const allLines = [];
    let offset = 0;
    for (const child of root.children) {
        const childLines = toLines(child); // Recursion: DFS traversal
        const childWidth = Math.max(minWidth, widthOf(childLines));
        mergeLines(allLines, offset, childLines);
        if (minWidth == 0) { // Not the first child?
            topLine = (topLine + split).padEnd(offset, "─");
            split = "┬";
        }
        offset += childWidth + 1;
        minWidth = 0; 
    }
    if (root.children.length > 1) topLine += "┐";
    allLines.unshift(topLine); // Prefix a new string with the value of the current node
    return allLines;
}

/////////// Utility functions to create a tree for the demo ///////////////////

function chain(...values) {
    // Create a (vertical) branch of nodes
    let children = [];
    for (let i = values.length - 1; i >= 0; i--) {
        children = [new Node(values[i], ...children)]; // An array with just one child
    }
    return children[0]; // The root of the created branch
}

function down(root, levels) {
    // Return the node that is #levels below the given root, on the rightmost "branch"
    while (levels--) {
        root = root.children.at(-1); // rightmost child
    }
    return root;
}

//////// Example trees ////////////////////////////////////////

function exampleTree1() {
    const root = chain(..."TESTNASTY");
    down(root, 4).children.push(chain(..."EXT"), chain(..."ICE"));
    down(root, 3).children.push(chain(..."VALUE"), chain(..."WOWHUH"));
    down(root, 6).children.push(chain(..."THISISLONG"));
    return root;
}

function exampleTree2() {
    const root = chain("Apple", "Banana", "Cherry");
    down(root, 2).children.push(chain("Date"));
    down(root, 1).children.push(chain("Elderberry", "Fig"));
    down(root, 2).children.push(chain("Grape"), chain("Hazelnut"));
    return root;
}

//////// Demo ////////

for (const root of [exampleTree1(), exampleTree2()]) {
    console.log(toLines(root).join("\n"));
}

    请注意，您想要的输出显示的“Root”标签未包含在此处。它似乎不符合正常的格式规则。但您显然可以在该函数之外打印它。

    • 2

相关问题