Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good algorithm is needed, since I also have other .yaml files with more items.
Question: How can I convert a tree with recursive relationship between those elements to a parent-child tree.
There are more elemtens like id=2 which have no parent anymore and the height of the resulting tree might vary.
What I tried so far:
- Find the lowest childen which is not parent of some other element
- Save those childen into a list/vector
- Iterate over this list/vector and connect parents which results into a linked list
But now I have the problem that I have to rotate the tree in some way in order to receive a tree from which I can create my tree view. I hope there is a better solution than I came up with.
Edit 1: If you parse such a .yaml file you will get a tree structure where each node has a key with a value or not. You can see in the picture that for example '2' is a key without a value and one childen with the name 'name'. The child 'name' itself has two children with the key 'en' and value 'Europe'.
You can say that those children are attributes from the item with the id '2' but still you will get a tree structure.
Now I want to make a tree which has in its first node the item with id '2' and all its 'attributes' and then in its child node the item with the id '3' and a sibling node with id '1'; and the item with the id '3' has a child node with id '4'.
Edit 2: What did I mean with 'recursive relationship': The term might be confusing and inappropiate in this situation. In a relational database model you can have a relationship from one relation (table) to itself. You call this a 'recursive relation'. The table would then have the columns 'id' and 'name' and 'parentID'.
I was hoping that this term makes my problem more clear because the 'parentID' does not refer to another .yaml file or some different id. However, it refers to some 'top' node (except the single root node) within the same file ('top'-node means image 1: node with id=1, id=2, id=3, id=4). If you think of those 'top' nodes being a tuple within a relational database you can say that the 'parentID' refers to another tuple which is related to it as parent.
The general rule, which I can think of is: I have a broken tree where actual parents/children are all siblings: (image 1 and image 4)
- node with id=1 is sibling of node with id=2, id=3, id=4
- node with id=2 is sibling of node with id=1, id=3, id=4
- node with id=3 is sibling of node with id=1, id=2, id=4
- node with id=4 is sibling of node with id=1, id=2, id=3
The child node 'parentID' of all those siblings tells me which node should be the parent node. Now I want to create a tree with the correct child-parent relation: (image 2)
- node id=1 becomes a children of node id=2
- node id=4 becomes a children of node id=3
- node id=3 becomes a children of node id=2
- node id=2 has no 'parentID' and so won't change its place
So, the algorithm has to:
- Find the parentID of one 'top' node (maybe with DFS)
- Find the correct parent (maybe iterate over all 'top' nodes and stop when id=parentID)
- Make the node (1.) the child of node (2.) (Maybe linked list or something else)
- Repeat until I went through all 'top' nodes
This algorithm could be good but there is the fact that there is no order within the file. So, at step (2.) I also have to go through all child nodes since my parent could already became a child of some other node. See image 1:
- 'top'-node with id=1 becomes a children of 'top'-node with id=2
- 'top'-node with id=2 has no parent (parentID=0) and won't change its place
- 'top'-node with id=3 becomes a children of 'top'-node with id=2
- 'top'-node with id=4 has now to become a children of node id=3