二叉搜索樹遍歷 - 預購

Question

餘米嘗試使用收益率的回報，它返回一個IEnumerable

private IEnumerable<T> Preorder(Node<T> node) 
{ 

    while(node != null) 
    { 
     yield return node.Data; 
     yield return node.LeftChild.Data; 
     yield return node.RightChild.Data; 
    } 

} 

在這種情況下實現樹的遍歷預購，它進入無限循環是的，我知道我必須保持穿越。如何才能做到這一點？

如果LeftChild或RightChild爲空，則拋出空異常。我認爲在這一點上我需要減產;

我認爲，inorder和postorder也會類似，有什麼想法嗎？

我有Resursive版本，效果很好。

public void PreOrderTraversal(Node<T> node) 
{ 

    if(node!=null) 
    { 
     Console.Write(node.Data); 
    } 
    if (node.LeftChild != null) 
    { 
     PreOrderTraversal(node.LeftChild); 
    } 

    if (node.RightChild != null) 
    { 
     PreOrderTraversal(node.RightChild); 
    } 
} 

謝謝。

Answer 1

選項＃1遞歸

public class Node<T> : IEnumerable<T> 
{ 
    public Node<T> LeftChild { get; set; } 

    public Node<T> RightChild { get; set; } 

    public T Data { get; set; } 

    public IEnumerator<T> GetEnumerator() 
    { 
     yield return Data; 

     if (LeftChild != null) 
     { 
      foreach (var child in LeftChild) 
       yield return child; 
     } 
     if (RightChild != null) 
     { 
      foreach (var child in RightChild) 
       yield return child; 
     } 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
} 

用法：

var child1 = new Node<int> { Data = 1 }; 
var child2 = new Node<int> { Data = 2 }; 
var child3 = new Node<int> { Data = 3, LeftChild = child1 }; 
var root = new Node<int> { Data = 4, LeftChild = child3, RightChild = child2 }; 

foreach (var value in root) 
    Console.WriteLine(value); 

選項＃2非遞歸靜態方法

public static IEnumerable<T> Preorder<T>(Node<T> root) 
{ 
    var stack = new Stack<Node<T>>(); 
    stack.Push(root); 

    while (stack.Count > 0) 
    { 
     var node = stack.Pop(); 
     yield return node.Data; 
     if (node.RightChild != null) 
      stack.Push(node.RightChild); 
     if (node.LeftChild != null) 
      stack.Push(node.LeftChild); 
    } 
}