चौड़ाई-पहले ट्रेवर्सल

Question

मैं डेटा संरचनाओं में अच्छी तरह से जानने की कोशिश कर रहा हूँ और गहराई-प्रथम ट्रेवर्सल/एक नियमित रूप से पेड़ पर एक कॉलबैक के आवेदन के लिए निम्नलिखित कोड लागू किया मैं इसे बदले में पहले चौड़ाई बनाने के लिए इसे बदलता हूं? यह वही पेड़ क्लास लग रहा है की तरह है:

var Tree = function (value) { 
    var newTree = {}; 

    newTree.value = value; 
    newTree.children = []; 
    extend(newTree, treeMethods); 

    return newTree; 
}; 

Answer 1

मूल रूप से, डीएफएस और BFS के बीच अंतर यह है कि एक डीएफएस के साथ आप एक ढेर पर वर्तमान नोड के बच्चों को धक्का है, तो वे पॉप और कार्रवाई की जाएगी से पहले, जबकि बीएफएस के लिए आप बच्चों को कतार के अंत में धक्का देते हैं, इसलिए उन्हें सब कुछ के बाद पॉप किया जाएगा और संसाधित किया जाएगा।

डीएफएस पुनरावर्ती रूप से कार्यान्वित करना आसान है क्योंकि आप कॉल स्टैक को ढेर के रूप में उपयोग कर सकते हैं। आप बीएफएस के साथ ऐसा नहीं कर सकते, क्योंकि आपको कतार की आवश्यकता है। बस समानता स्पष्ट करना, चलो पहले एक सतत कार्यान्वयन करने के लिए अपने डीएफएस कन्वर्ट:

//DFS 
Tree.prototype.traverse = function (callback) { 
    var stack=[this]; 
    var n; 

    while(stack.length>0) { 

    n = stack.pop(); 
    callback(n.value); 

    if (!n.children) { 
     continue; 
    } 

    for (var i = n.children.length-1; i>=0; i--) { 
     stack.push(n.children[i]); 
    } 
    } 
}; 

और अब बीएफ

//BFS 
Tree.prototype.traverse = function (callback) { 
    var queue=[this]; 
    var n; 

    while(queue.length>0) { 

    n = queue.shift(); 
    callback(n.value); 

    if (!n.children) { 
     continue; 
    } 

    for (var i = 0; i< n.children.length; i++) { 
     queue.push(n.children[i]); 
    } 
    } 
};