Tri des données dans un arbre

Edit: Scarp this, ça ne marche pas.

C'est le meilleur que j'ai géré. Qui devrait le trier. Je ne l'ai pas encore testé. Je laisserai la meilleure réponse ouverte pour voir si quelqu'un peut l'améliorer. xxx

Après de nombreuses tentatives, j'ai monté cela. Cela fonctionne, mais n'est pas très élégant. Pourrait également faire avec abstraction dans sa propre classe.

// Initial sort places items in the correct sort order.
data.sort(function(a, b) {
  return a.sort - b.sort;
});

vat top_parent_id = 1;          // The value of an items parent if it is a top level item.
var sorted = [];                // Empty array to copy sorted elements into.
var skipped = true;             // flag to indicate if any elements have been skipped.
var skip_count = 0;             // Counter to prevent infinite loops.
// Loop until no elements have been skipped. 
//This loops through each level of the tree until all nested branches have been added
while(skipped){
    skipped = false;
    skip_count++;
    if(skip_count === 50){      // Maximum tree depth.
        throw "Error in sorted data or tree depth too great.";
        break;
    }

    // Loop through the data in reverse order; this preserves the branch sort order.
    for (var i = data.length - 1; i >= 0; i--) {
        var item = data[i];

        // Skip if this element has already been processed.
        if(item.done)
            continue;

        // If this is this a top level item, then insert and continue.
        if(item.parent == top_parent_id){
            sorted.splice(0, 0, item);          // Insert at the start; last item is the top sort.
            item.done = true;
            continue;
        }

        // Loop the new array to try and find this items parent.
        var found = false;
        for (var j = 0; j < sorted.length; j++) {
            if(item.parent === sorted[j].index){
                sorted.splice(j + 1, 0, item);
                found = true;
                item.done = true;
                break;
            }
        }

        // If a place for an item has not been found then skip it for now so it can be tested again on the next iteration.
        if(!found){
            skipped = true;

        }
    }
}
data = sorted;

Ce n'est pas votre approche d'origine, mais vous pouvez construire un arbre réel de vos données, comme celui-ci:

{ index: 4, sort:  4, parent: 0}
{ index: 2, sort:  7, parent: 0}
{ index: 1, sort: 10, parent: 0}
{ index: 5, sort: 13, parent: 1}
{ index: 8, sort:  6, parent: 5}
{ index: 7, sort:  2, parent: 8}
{ index: 6, sort: 20, parent: 5}
{ index: 3, sort: 15, parent: 1}