对数据进行排序成树

Question

，我有以下数据：

var data = [ 
    { index : 1, sort : 10, parent : 0 }, 
    { index : 2, sort : 7, parent : 0 }, 
    { index : 3, sort : 15, parent : 1 }, 
    { index : 4, sort : 4, parent : 0 }, 
    { index : 5, sort : 13, parent : 1 }, 
    { index : 6, sort : 20, parent : 5 }, 
    { index : 7, sort : 2, parent : 8 }, 
    { index : 8, sort : 6, parent : 5 }, 
]; 

如何有效地两家母公司ID和排序值，使我最终解决这：

var data = [ 
    { 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 }, 
]; 

这是一个树形结构。每个元素之后紧跟着任何子元素，并且同一分支上的所有元素都按排序值排序。

我能想到的最好的方法是首先按父母排序，然后在每个分支上进行第二排序。这似乎效率低下。

编辑：示例排序顺序错误。我纠正了它。

编辑澄清：每个嵌套的分支需要紧挨着父值出现，而不是在分支末尾。

编辑：进一步修正数据。

Answer 1

这不是你原来的做法，但你可以从你的数据建立一个实际的树，像这样：

function TreeNode(data) { 
    this.data  = data; 
    this.parent = null; 
    this.children = []; 
} 
TreeNode.comparer = function (a, b) { 
    return a.data.sort < b.data.sort ? 0 : 1; 
}; 
TreeNode.prototype.sortRecursive = function() { 
    this.children.sort(TreeNode.comparer); 
    for (var i=0, l=this.children.length; i<l; i++) { 
    this.children[i].sortRecursive(); 
    } 
    return this; 
}; 

function toTree(data) { 
    var nodeById = {}, i = 0, l = data.length, node; 

    nodeById[0] = new TreeNode(); // that's the root node 

    for (i=0; i<l; i++) { // make TreeNode objects for each item 
    nodeById[ data[i].index ] = new TreeNode(data[i]); 
    } 
    for (i=0; i<l; i++) { // link all TreeNode objects 
    node = nodeById[ data[i].index ]; 
    node.parent = nodeById[node.data.parent]; 
    node.parent.children.push(node); 
    } 
    return nodeById[0].sortRecursive(); 
} 

有了这个设置，你会得到你的节点整齐地嵌套有简单的调用：

var tree = toTree(data); 

 
TreeNode:0 
    parent -> null 
    data -> undefined 
    childen -> Array[ 
    TreeNode:1 
     parent -> TreeNode:0 
     data -> { index : 4, sort : 4, parent : 0 } 
     childen -> Array[] 
    TreeNode:2 
     parent -> TreeNode:0 
     data -> { index : 2, sort : 7, parent : 0 } 
     childen -> Array[] 
    TreeNode:3 
     parent -> TreeNode:0 
     data -> { index : 1, sort : 10, parent : 0 } 
     childen -> Array[ 
     TreeNode:4 
      parent -> TreeNode:3 
      data -> { index : 5, sort : 13, parent : 1 } 
      childen -> Array[ 
      ] 
     TreeNode:5 
      parent -> TreeNode:3 
      data -> { index : 3, sort : 15, parent : 1 } 
      childen -> Array[ 
      ... and so on ... 
      ] 
     ] 
    ] 

一旦你的树对象，你可以做很多事情有了它，包括穿越它以预期的顺序递归地递归。

要做到这一点，你可以添加一个辅助功能，做深度优先遍历和执行的有效载荷功能f为每个节点：

TreeNode.prototype.walk = function(f, recursive) { 
    for (var i=0, l=this.children.length; i<l; i++) { 
    var child = this.children[i]; 
    f.apply(child, Array.prototype.slice.call(arguments, 2)); 
    if (recursive) child.walk.apply(child, arguments); 
    } 
} 

，并调用它像这样：

tree.walk(function() { console.log(this.data) }, true); 

这将产生：

 
{ 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} 

使用更复杂的有效载荷func其他效果的tions，比如在jQuery中添加表格行或者在<select>框中添加项目。

Answer 2

编辑：呃，这是行不通的。

这是我管理的最好的。它应该对其进行排序。我还没有测试过。我会留下最好的答案，看看有没有人可以改进。

data.sort(function(a, b) { 
    return a.parent - b.parent; 
}); 

var changes = true; 
while (changes){ 
    changes = false; 
    for (var i = 1; i < data.length; i++) { 
     if(data[i].parent === data[i-1].parent && data[i].sort < data[i-1].sort){ 
      var tmp = data[i-1]; 
      data[i-1] = data[i]; 
      data[i] = tmp; 
      changes = true; 
     } 
    } 
} 

Answer 3

经过多次尝试，我想出了这个。它有效，但不是很优雅。也可以抽象成自己的课堂。

// 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; 

Answer 4

Tomalak请求上面，我张贴我的单身人士版本的答案。那就是：

/** 
* Represents sorted results in a tree structure. 
*/ 
Tree = (function() { 

    /** 
    * 
    * @type {Object} nodes Holds all the nodes in a flat format. 
    * @type {Object} nodes.data The data that is held in this node. 
    * @type {Object} nodes.parent Points to the parent object of this node. 
    * @type {Array} nodes.children An array of the child nodes of this node. 
    */ 
    var nodes = {}; 

    /** 
    * @type {Object} root_node A Reference to the root node in nodes. 
    */ 
    var root_node; 

    /** 
    * A sort function to sort the nodes by the data.sort value in each node. 
    * @param {Number} a The first node to compare 
    * @param {Number} b The second node to compare 
    * @return {Boolean} Swap these nodes or not. 
    */ 
    var comparer = function (a, b) { 
     return a.data.sort < b.data.sort ? 0 : 1; 
    }; 

    /** 
    * Sorts all the nodes so that they are in the correct order according to each nodes data.sort value. 
    * @param {Object} node A reference to the node in the nodes object. 
    */ 
    var sortRecursive = function (node) { 
     node.children.sort(comparer); 
     var len = node.children.length; 
     for (var i = 0 ; i < len ; i++) { 
      sortRecursive(node.children[i]); 
     } 
    }; 

    /** 
    * Create a new node with the passed in data. 
    * @param {Object} data The data that is associated with this node. 
    */ 
    var create_node = function(data){ 
     var node = { 
      data : data, 
      parent : null, 
      children : [] 
     }; 
     return node; 
    }; 

    return { 

     /** 
     * Create a new tree of data 
     * @param {Array} data An array of data objects to transorm into a tree. 
     * @param {Array} data[].index The id of this node 
     * @param {Array} data[].parent The parent id of this node. 
     * @param {Number} root_id Id of the root node. 
     */ 
     create : function(data, root_id){ 

      // Clear any previous data 
      nodes = {}; 

      var i; 
      var len = data.length; 

      // Create an empty root node 
      nodes[root_id] = create_node({}); 
      root_node = nodes[root_id]; 

      // Make node objects for each data item 
      for (i=0; i<len; i++) { 
       if(typeof data[i].sort !== "undefined") 
        nodes[ data[i].index ] = create_node(data[i]); 
      } 

      // Link all TreeNode objects 
      for (i=0; i<len; i++) { 
       var node = nodes[data[i].index]; 
       node.parent = nodes[node.data.parent]; 
       node.parent.children.push(node); 
      } 
      sortRecursive(nodes[root_id]); 
     }, 

     /** 
     * Walk through the nodes in nested and then sorted order, calling the passed in callback for each node. 
     * @param {Function} callback A callback function to call for each node. 
     * @param {Boolean} recursive Should the walkback be recursive, or just fetch the top level results. 
     * @param {Object|Undefined} node The node that is currently being walked. 
     *        Ommit this value and the root node will be used. 
     */ 
     walk : function(callback, recursive, node) { 
      if(typeof node == "undefined") 
       node = root_node; 

      for (var i = 0, len = node.children.length; i < len; i++) { 
       var child = node.children[i]; 
       callback.apply(child, Array.prototype.slice.call(arguments, 2)); 
       if (recursive) 
        arguments.callee(callback, recursive, child); 
      } 
     } 

    }; 
})(); 

填充树：

Tree.create(unsorted_data, parent_id); 

获取与排序后的数组：

var sorted = []; 
Tree.walk(function(){ 
    sorted.push(this.data); 
}, true);