ツリー

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 }, 
]; 

この木構造です。各要素の直後に子があり、同じブランチ上のすべての要素がソート値でソートされます。

私が思いつくのは、最初に親によってソートして、各ブランチで2番目のソートを行うことです。これは非効率的と思われる。

編集：ソート順が正しくありませんでした。私はそれを修正しました。

説明のために編集：各ネストされたブランチは、ブランチの終わりではなく、親の値のすぐ下に表示する必要があります。

編集：データをさらに修正します。

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を使用します。テーブル内のテーブル行を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); 
      } 
     } 

    }; 
})(); 

はと木を読み込む：このアルゴリズムは、私に私のとまったく同じ結果を与える

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