Advice when creating an algorithm which sortes pages with infinite children hierarchy

I need some advice when it comes to solving a sorting algorithm. This particular algorithm will have an input of a list with n items. Each item has an id and a parent id. Like this:

[
    {id : 1, parent_id : 0},
    {id : 2, parent_id : 1},
    {id : 3, parent_id : 1},
    {id : 4, parent_id : 2},
    {id : 5, parent_id : 4},
    {id : 6, parent_id : 0}
]

Here's the expected result:

[
    {id : 1, parent_id : 0, children:
    [
        {id : 2, parent_id : 1, children:
        [
            {id : 4, parent_id : 2, children:
            [
                {id : 5, parent_id : 4}
            ]}
        ]
        },
        {id : 3, parent_id : 1}            
    ]},
    {id : 6, parent_id : 0}
]

My initial idea was split the algorithm into levels of hierarchy parsing each level recursively. So that it looks something like this in theory:

• Compare each item in the unsorted list with all items to see if there are any matches, put each matches in a child node in each parent, put each parent in a sorted list variable.
• Compare each item in the children node with all the items in the unsorted list to see if they have matches, put the matches in each child node into their own child node.
• Continue last step until each level doesn't have anymore matches.

I have just started looking on some functional programming paradigms and started reading more about algorithm and analysis, just because I'm not familiar with thinking recursively.

So my questions are:

• What are your advice when dealing with kind of logic?
• How do I learn to think in the right way?
• By looking at my current algorithm, I feel like I have grasped the concept except I don't really know how to make the second check work as a recursive solution. Am I far from going the right direction?

So far I have created an algorithm which will be capable of 2 levels of hierarchy. It looks something like this (currently written in php and is just proof of concept code):

function sortParentsChildren($unsortedList, $parentIDKey = "parent_id", $childNameKey = "children"){
    $sortedList = array();

    foreach($unsortedList as $key => $value){
        $children = array();
            //See if there are any children for this item
        foreach($unsortedList as $skey => $svalue){
            if($value["id"] == $svalue[$parentIDKey]){      
                $children[] = $svalue;
            }
        }

            //Add all items with parent id = 0 to the root
        if($value["parent_id"] == 0){
            $sortedList[$ke开发者_如何学编程y] = $value;
        }   

            //Check if there were any children
        if(sizeof($children) > 0){
                    //Search each children and see if they have any matches
            foreach($children as $ckey => $cvalue){
                foreach($unsortedList as $s2key => $s2value){
                    if($cvalue["id"] == $s2value[$parentIDKey]){        
                        $children[$ckey][$childNameKey][] = $s2value;
                    }
                }                   
            }

            $sortedList[$key] = $value;
            $sortedList[$key][$childNameKey] = $children;
        }
    }

    return $sortedList;
}

You'd typically do this with some kind of dictionary data structure. Basically, you have a structure like this:

Node
{
    int id;
    int parent;
    Node[] children;
}

You keep this in a dictionary or associative array keyed by id. Create a node with an id value of 0 and a parent id of -1.

Sort your input array by parent id and then go through the list. For every item, add it to the dictionary. Also look up its parent node (which is already in the dictionary because the input list has been sorted by parent id), and add the new node to the parent's children list.

When you've finished, node[0] contains the constructed hierarchy.

I'm not much of a PHP programmer, so you'll have to do with pseudocode:

Nodes = new associative array
Nodes[0] = new Node(0, -1)
sortedInput = sort input by parent id
foreach item in sortedInput
    Nodes[item.id] = new Node(item.id, item.parent);
    //Nodes[item.parent].Children.Add(Node);
    // Above line commented and replaced with this.
    Nodes[item.parent].Children.Add(Nodes[item.id]);
end

// Nodes[0] contains the hierarchy
OutputNode(Nodes[0], "")

The function to output the hierarchy is recursive:

OutputNode(Node, indent)
    print indent, Node.id, Node.parent
    foreach (child in Node.children)
        OutputNode(child, indent+"  ");
    end
end

There is no need for recursion. Just a simple loop over the objects. For each object, if its parent_id is 0, copy it to the answer array. Else access the parent object by its location in the array, and append the current object to its list of children.

Here is how that works out for your array. Note carefully the result of the fact that updating an object once updates all copies of that object.

0: Start
    answer = []
    objects = [
        {id : 1, parent_id : 0},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

1: Append object 1 to answer
    answer = [
        {id : 1, parent_id : 0}
    ]
    objects = [
        {id : 1, parent_id : 0},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

2: Append object 2 to children of object 1
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

3: Append object 3 to children of object 1
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

4: Append object 4 to children of object 2
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3}
            ]}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3}
        ]},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

5: Append object 5 to children of object 4
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3, children : [
                {id : 5, parent_id : 4}
            ]}
        ]},
        {id : 4, parent_id : 3, children : [
            {id : 5, parent_id : 4}
        ]}
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

6: Append object 6 to answer
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 6, parent_id : 0}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3, children : [
                {id : 5, parent_id : 4}
            ]}
        ]},
        {id : 4, parent_id : 3, children : [
            {id : 5, parent_id : 4}
        ]}
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]