Say we have a tree stored like this:

1
1 2
1 2 3
1 2 3 4
1 5
1 5 6 
1 5 6 7
1 5 6 7 8
1 9 
1 9 10
1 9 10 11
1 9 10 11 12
1 9 10 13

If we were to draw this tree, it would look something like:

What I need to do is rewrite the tree into a name-parent-children type format. In this example, this would look like:

[{

        "name": "1",
        "parent": null,
        "children": [
            {
                "name": "2",
                "parent": "1",
                "children": [
                    {
                        "name": "3",
                        "parent": "2",
                        "children": [
                            {
                                "name": "4",
                                "parent": "3",
                                "children": []
                            }
                        ]
                    }
                ]
            },
            {
                "name": "5",
                "parent": "1",
                "children": [
                    {
                        "name": "6",
                        "parent": "5",
                        "children": [
                            {
                                "name": "7",
                                "parent": "6",
                                "children": [
                                    {
                                        "name": "8",
                                        "parent": "7",
                                        "children": []
                                    }
                                ]
                            }
                        ]
                    }
                ]
            },
            {
                "name": "9",
                "parent": "1",
                "children": [
                    {
                        "name": "10",
                        "parent": "9",
                        "children": [
                            {
                                "name": "11",
                                "parent": "10",
                                "children": [
                                    {
                                        "name": "12",
                                        "parent": "11",
                                        "children": []
                                    }
                                ]
                            },
                            {
                                "name": "13",
                                "parent": "10",
                                "children": []
                            }
                        ]
                    },
                    
                ]
            }
        ]


    }];

This is a JavaScript array. I want to know what the most efficient algorithm to achieve this conversion would be. If you're wondering why I put Python as a tag, this is because the algorithm will be written entirely in Python, but the list will ultimately be used in a JavaScript program that will display the tree.

CodePudding user response：

Start by doing a nested iteration that turns your list of strings into a nested dict:

data = """
1
1 2
1 2 3
1 2 3 4
1 5
1 5 6 
1 5 6 7
1 5 6 7 8
1 9 
1 9 10
1 9 10 11
1 9 10 11 12
1 9 10 13
"""

tree = {}
for line in data.split("\n"):
    node = tree
    for n in line.split():
        node = node.setdefault(n, {})
print(tree)

prints:

{'1': {'2': {'3': {'4': {}}}, '5': {'6': {'7': {'8': {}}}}, '9': {'10': {'11': {'12': {}}, '13': {}}}}}

Then we can massage the nested dict into your JS structure with a simple recursive function:

def node_to_js(tree, parent=None):
    return [{
            "name": name,
            "parent": parent,
            "children": node_to_js(node, name)
        }
        for name, node in tree.items()
    ]

print(node_to_js(tree))

prints:

[{'name': '1', 'parent': None, 'children': [{'name': '2', 'parent': '1', 'children': [{'name': '3', 'parent': '2', 'children': [{'name': '4', 'parent': '3', 'children': []}]}]}, {'name': '5', 'parent': '1', 'children': [{'name': '6', 'parent': '5', 'children': [{'name': '7', 'parent': '6', 'children': [{'name': '8', 'parent': '7', 'children': []}]}]}]}, {'name': '9', 'parent': '1', 'children': [{'name': '10', 'parent': '9', 'children': [{'name': '11', 'parent': '10', 'children': [{'name': '12', 'parent': '11', 'children': []}]}, {'name': '13', 'parent': '10', 'children': []}]}]}]}]

which you can easily JSONify in order to get it into your JS code.