एक पेड़ से छँटाई डेटा

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

मैं कैसे कुशलतापूर्वक ताकि मैं अंत दोनों अभिभावक आईडी और प्रकार मूल्य द्वारा इस क्रमित करूं:

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 ... 
      ] 
     ] 
    ] 

एक बार जब आप उस वृक्ष वस्तु है, तो आप इसके साथ बातें की एक संख्या कर सकते हैं traversing सहित, यह अपेक्षित क्रम में पुनरावर्ती है।

ऐसा करने के लिए, आप एक सहायक समारोह है कि प्रत्येक नोड के लिए गहराई-प्रथम ट्रेवर्सल करता है और एक पेलोड समारोह 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

टॉमलाक अनुरोध ऊपर है कि मैं उनके उत्तर के अपने सिंगलटन संस्करण को पोस्ट करता हूं।संदेश यह है:

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