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

Question

给定一个树状节点数据结构，每个节点都有一个属性

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 结合起来，以考虑当前节点左侧的子节点数量。然而，我正在努力弄清楚如何做到这一点。

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

Answer 1

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

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

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

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

function longestLine(lines) {
    return Math.max(...lines.map(line => line.length));
}

function padLines(lines, width) {
    for (let i = 0; i < lines.length; i++) {
        lines[i] = lines[i].padEnd(width);
    }
}

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, longestLine(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”标签不包含在此处。它似乎不符合正常的格式规则。但显然你可以在这个函数之外打印它。