其實我原本是想要測試 yield 可不可以在適用在遞迴的情形下,順手就做了一版簡單的 Preorder Tree Traversal。

我們先定義樹的節點 class,其中我們加上 Preorder 屬性,會回傳針對樹狀資料結構,做 preorder 巡訪的結果︰

/// <summary>
/// 樹狀結構節點
/// </summary>
/// <typeparam name="T">節點資料型別</typeparam>
public class Node<t>
{
    /// <summary>
    /// Initializes a new instance of the <see cref="Node&lt;T&gt;"></see> class.
    /// </summary>
    /// <param name="data">節點資料
    public Node(T data)
    {
        this.Data = data;
    }
 
    /// <summary>
    /// 節點資料
    /// </summary>
    public T Data { get; set; }
 
    /// <summary>
    /// 左子樹
    /// </summary>
    public Node<t> Left { get; set; }
 
    /// <summary>
    /// 右子樹
    /// </summary>
    public Node<t> Right { get; set; }
 
    /// <summary>
    /// Preorder Traversal
    /// </summary>
    public IEnumerable<t> Preorder
    {
        get
        {
            return this.ScanPreorder(this);
        }
    } 
 
    /// <summary>
    /// Preorder Traversal Algorithm
    /// </summary>
    /// <param name="tree">巡訪的樹
    /// <returns>巡訪結果</returns>
    private IEnumerable<t> ScanPreorder(Node<t> tree)
    {
        // 節點不得為 null
        if (tree == null)
        {
            throw new ArgumentNullException();
        }
 
        // preorder Traversal
        yield return tree.Data;
 
        if (tree.Left != null)
        {
            foreach (var node in this.ScanPreorder(tree.Left))
            {
                yield return node;
            }
        }
 
        if (tree.Right != null)
        {
            foreach (var node in this.ScanPreorder(tree.Right))
            {
                yield return node;
            }
        }
    }
}

我們要巡訪的樹,長相如下︰ image

使用方式如下︰

// 建立樹狀結構
Node tree = new Node(0);
tree.Left = new Node(1);
tree.Right = new Node(2);
tree.Left.Left = new Node(3);
tree.Left.Right = new Node(4);
tree.Right.Right = new Node(5);
tree.Left.Left.Left = new Node(6);
tree.Left.Left.Right = new Node(7);
tree.Right.Right.Left = new Node(8);
tree.Right.Right.Right = new Node(9);

// Preorder,印出上圖中,Preorder 的順序
Console.Write("Preorder:\t");
foreach (var node in tree.Preorder)
{
    Console.Write(node);
}

因為這篇算倉促為之,後續再補上原理和完整程式 XD