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

I am trying to represent an n-ary tree in an 2D matrix. Not sure how to approach the problem. This would be some sort of hierarchy. I have the root node of the tree

Example :

Output:

CodePudding user response：

The table represents a pre-order (depth-first) traversal. You can implement it with a recursive function.

Pseudo code:

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

Here is an implementation in JavaScript, with output to an HTML table:

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>

CodePudding user response：

You can use the same technique used to represent graph in 2D matrix. see this article

For this tree the dimension of the matrix will be 11x11.

and the matrix will be like this