如何在二维矩阵中表示n-ary树？-解网

问：

我正在尝试在 2D 矩阵中表示 n 元树。不知道如何处理这个问题。这将是某种层次结构。我有树的根节点

例：

输出：

算法数据结构树视图与语言无关

目前尚不清楚您到底在要求什么。正如其他人所建议的那样，邻接矩阵是在矩阵中表示树或图形的一种非常标准的方法。如果这是一棵严格的 n 元树，那么您可以使用用于表示二进制（或 n）堆的相同技术轻松地在一维数组中表示它，尽管如果树不是完整和平衡的，则表示将非常稀疏。

0赞 rici 12/15/2022

这种表示的目的是什么？在我看来，您展示的示例除了可能作为视觉表示（也不是最好的）之外似乎没有用。如果你想使用数据结构来做某种树分析，那么有更有效和可用的数据结构，知道你对什么样的分析感兴趣会很有用。

0赞 trincot 12/15/2022

“我正在尝试”：请编辑您的问题并展示您的尝试，并解释问题所在。该矩阵看起来像是树的预序遍历的结果。目前尚不清楚问题出在哪里。

答：

1赞 trincot 12/15/2022 #1

该表表示预序（深度优先）遍历。您可以使用递归函数来实现它。

伪代码：

function dfs(children, row=0, col=0):
    if no children:
        return row + 1  # It is a leaf
    for each child in children:
        output child.label in table(row, col)
        row = dfs(child.children, row, col + 1)
    return row   # It was not a leaf

下面是一个 JavaScript 中的实现，输出到 HTML 表：

function output(label, row, col) {
    document.querySelector("table").rows[row].cells[col].textContent = label;
}

function dfs(children, row=0, col=0) {
    if (!children?.length) return row + 1; // End of path
    for (const child of children) {
        output(child.label, row, col);
        row = dfs(child.children, row, col + 1);
    }
    return row; // It was not a leaf
}

// Example tree:
const forest = [
    { "label": "a", "children": [
        { "label": "b", "children": [
            { "label": "j" },
            { "label": "k" },
        ]},
        { "label": "c" },
        { "label": "d", "children": [
            { "label": "e" },
            { "label": "f", "children": [
                { "label": "h" },
                { "label": "i" },
            ]},
            { "label": "g" },
        ]}
    ]}
];

dfs(forest);

table { border-collapse: collapse; width: 100%; }
table td { border: 1px solid; width: 20%; padding-left: 10px }
tr { height: 25px; v-align: middle; }

<table>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
    <tr><td></td><td></td><td></td><td></td><td></td></tr>
</table>

上一个：循环访问文件中的记录并替换另一个文件上的内容的最快方法

下一个：如何获取字符串的最后 2 个字符，最后一个字符是 A 或 B，最后一个字符的第二个是 1-360？（正则表达式 GREP）

如何在二维矩阵中表示n-ary树？

How to represent n-ary tree in 2D matrix?

评论