ब्रेडथ-प्रथम ट्रैवर्सल

Question

मैं एक साक्षात्कार प्रश्न हल करने की कोशिश कर रहा था, लेकिन इसके लिए मुझे बाइनरी पेड़ स्तर को स्तर से यात्रा करना है। मैं चर

private object data; 
private BinaryNode left; 
private BinaryNode right; 

नीचे होने किसी ने मेरे BinarySearchTree वर्ग के अंदर BreadthFirstSearch विधि लिखने के लिए मदद कृपया सकते हैं साथ BinaryNode डिज़ाइन किया गया है?

अद्यतन: आपके इनपुट के लिए सभी को धन्यवाद। तो यह साक्षात्कार सवाल था। "एक बाइनरी खोज पेड़ को देखते हुए, एक एल्गोरिदम तैयार करें जो प्रत्येक गहराई पर सभी नोड्स की एक लिंक की गई सूची बनाता है (यानी, यदि आपके पास गहराई डी वाला पेड़ है, तो आपके पास डी लिंक्ड सूचियां होंगी)"।

यहां मेरा तरीका है, मुझे अपनी विशेषज्ञ टिप्पणी बताएं।

public List<LinkedList<BNode>> FindLevelLinkList(BNode root) 
    { 
     Queue<BNode> q = new Queue<BNode>(); 
     // List of all nodes starting from root. 
     List<BNode> list = new List<BNode>(); 
     q.Enqueue(root); 
     while (q.Count > 0) 
     { 
      BNode current = q.Dequeue(); 
      if (current == null) 
       continue; 
      q.Enqueue(current.Left); 
      q.Enqueue(current.Right); 
      list.Add(current); 
     } 

     // Add tree nodes of same depth into individual LinkedList. Then add all LinkedList into a List 
     LinkedList<BNode> LL = new LinkedList<BNode>(); 
     List<LinkedList<BNode>> result = new List<LinkedList<BNode>>(); 
     LL.AddLast(root); 
     int currentDepth = 0; 
     foreach (BNode node in list) 
     { 
      if (node != root) 
      { 
       if (node.Depth == currentDepth) 
       { 
        LL.AddLast(node); 
       } 
       else 
       { 
        result.Add(LL); 
        LL = new LinkedList<BNode>(); 
        LL.AddLast(node); 
        currentDepth++; 
       } 
      } 
     } 

     // Add the last linkedlist 
     result.Add(LL); 
     return result; 
    } 

Answer 1

एक चौड़ाई पहले खोज आम तौर पर एक कतार, गहराई पहले खोज एक ढेर उपयोग करने के साथ लागू किया गया है।

Queue<Node> q = new Queue<Node>(); 
q.Enqueue(root); 
while(q.Count > 0) 
{ 
    Node current = q.Dequeue(); 
    if(current == null) 
     continue; 
    q.Enqueue(current.Left); 
    q.Enqueue(current.Right); 

    DoSomething(current); 
} 

dequeuing आप कतार में जोड़ने से पहले जाँच कर सकते हैं के बाद null के लिए जाँच करने के लिए एक विकल्प के रूप। मैंने कोड संकलित नहीं किया है, इसलिए इसमें कुछ छोटी गलतियां हो सकती हैं।

---

एक सजावटी (लेकिन धीमी) संस्करण है कि LINQ से अच्छी तरह एकीकृत:

public static IEnumerable<T> BreadthFirstTopDownTraversal<T>(T root, Func<T, IEnumerable<T>> children) 
{ 
    var q = new Queue<T>(); 
    q.Enqueue(root); 
    while (q.Count > 0) 
    { 
     T current = q.Dequeue(); 
     yield return current; 
     foreach (var child in children(current)) 
      q.Enqueue(child); 
    } 
} 

कौन सा Node पर एक Children संपत्ति के साथ एक साथ इस्तेमाल किया जा सकता:

IEnumerable<Node> Children { get { return new []{ Left, Right }.Where(x => x != null); } } 

...

foreach(var node in BreadthFirstTopDownTraversal(root, node => node.Children)) 
{ 
    ... 
} 

Answer 2

var queue = new Queue<BinaryNode>(); 
queue.Enqueue(rootNode); 

while(queue.Any()) 
{ 
    var currentNode = queue.Dequeue(); 
    if(currentNode.data == searchedData) 
    { 
    break; 
    } 

    if(currentNode.Left != null) 
    queue.Enqueue(currentNode.Left); 

    if(currentNode.Right != null) 
    queue.Enqueue(currentNode.Right); 
} 

Answer 3

डीएफएस दृष्टिकोण का उपयोग कर: पेड़ ट्रेवर्सल है O (n)

public class NodeLevel 
{ 
    public TreeNode Node { get; set;} 
    public int Level { get; set;} 
} 

public class NodeLevelList 
{ 
    private Dictionary<int,List<TreeNode>> finalLists = new Dictionary<int,List<TreeNode>>(); 

    public void AddToDictionary(NodeLevel ndlvl) 
    { 
     if(finalLists.ContainsKey(ndlvl.Level)) 
     { 
      finalLists[ndlvl.Level].Add(ndlvl.Node); 
     } 
     else 
     { 
      finalLists.Add(ndlvl.Level,new List<TreeNode>(){ndlvl.Node}); 
     } 
    } 

    public Dictionary<int,List<TreeNode>> GetFinalList() 
    { 
     return finalLists; 
    } 
} 

विधि है कि करता है ट्रेवर्सल:

public static void DFSLevel(TreeNode root, int level, NodeLevelList nodeLevelList) 
{ 
    if(root == null) 
     return; 

    nodeLevelList.AddToDictionary(new NodeLevel{Node = root, Level = level}); 

    level++; 

    DFSLevel(root.Left,level,nodeLevelList); 
    DFSLevel(root.Right,level,nodeLevelList); 

}