פרק 6 – מחלקת BinNode⟨T⟩ ועצים בינאריים

ב‑#C ניתן היה לממש מחלקה גנרית עבור עץ בינארי באופן הבא:

public class BinNode<T>
{
    public T Value { get; set; }
    public BinNode<T> Left { get; set; }
    public BinNode<T> Right { get; set; }

    public BinNode(T value, BinNode<T> left = null, BinNode<T> right = null)
    {
        Value = value;
        Left = left;
        Right = right;
    }
}

אבל

public class BinNode<T>
{
    private T value;
    private BinNode<T> left;
    private BinNode<T> right;

    //-----------------------------------
    //constructors
    public BinNode(T value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    public BinNode(BinNode<T> left, T value, BinNode<T> right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    //-----------------------------------
    //getters
    public T GetValue()
    {
        return value;
    }
    public BinNode<T> GetLeft()
    {
        return this.left;
    }
    public BinNode<T> GetRight()
    {
        return this.right;
    }
    //-----------------------------------
    //setters
    public void SetValue(T value)
    {
        this.value = value;
    }
    public void SetLeft(BinNode<T> left)
    {
        this.left = left;
    }

    public void SetRight(BinNode<T> right)
    {
        this.right = right;
    }
    //-----------------------------------
    //returns true if this.left is not null, else returns false
    public bool HasLeft()
    {
        return (this.left != null);
    }
    //returns true if this.right is not null, else returns false
    public bool HasRight()
    {
        return (this.right != null);
    }
    //-----------------------------------
    //ToString
    public override string ToString()
    {
        return "(" + left + " " + value + " " + right + ")";
    }
}

נראה כמה סוגים של טרוורסה איטרטיבית (בלי רקורסיה). למרות כל הדוגמאות - עדיף ברקורסיה.

1. טרוורסה ברוחב (Level-Order / BFS) בעזרת Queue הרעיון: שמים את השורש בתור, ואז כל פעם מוציאים חוליה מהתור, מדפיסים את הערך שלה, ומכניסים את ילדיה (שמאל, ימין) לסוף התור.

    public static void BfsTraverse<T>(BinNode<T> root)
    {
        if (root == null)
            return;
   
        Queue<BinNode<T>> q = new Queue<BinNode<T>>();
        q.Insert(root); // מכניסים את השורש לתור
   
        while (!q.IsEmpty())
        {
            BinNode<T> node = q.Remove();   // מוציאים חוליה מהתור
            Console.WriteLine(node.GetValue());
   
            if (node.HasLeft())
                q.Insert(node.GetLeft());   // מכניסים בן שמאל
            if (node.HasRight())
                q.Insert(node.GetRight());  // מכניסים בן ימין
        }
    }
   

   זה עובר על העץ לפי שכבות: קודם שורש, אחר כך כל הילדים שלו, אחר כך הנכדים, וכו’.

   ---

2. טרוורסה בעומק (DFS Pre-Order) בעזרת Stack

   כאן נעשה Pre-Order (שורש → שמאל → ימין), אבל איטרטיבי.

   הרעיון: שמים את השורש במחסנית; כל פעם מוציאים חוליה מהמחסנית, מדפיסים אותה, ואז דוחפים קודם את הימני ואחר כך את השמאלי – כדי שהשמאלי ייצא ראשון.

    public static void PreOrderIterative<T>(BinNode<T> root)
    {
        if (root == null)
            return;
   
        Stack<BinNode<T>> s = new Stack<BinNode<T>>();
        s.Push(root);
   
        while (!s.IsEmpty())
        {
            BinNode<T> node = s.Pop();
            Console.WriteLine(node.GetValue()); // "שורש"
   
            if (node.HasRight())
                s.Push(node.GetRight()); // דוחפים קודם ימין
            if (node.HasLeft())
                s.Push(node.GetLeft());  // ואז שמאל – ייצא ראשון
        }
    }
   

3. טרוורסה In-Order איטרטיבית בעזרת Stack

   In-Order קלאסי (שמאל → שורש → ימין):

    public static void InOrderIterative<T>(BinNode<T> root)
    {
        Stack<BinNode<T>> s = new Stack<BinNode<T>>();
        BinNode<T> curr = root;
   
        while (curr != null || !s.IsEmpty())
        {
            while (curr != null)
            {
                s.Push(curr);
                curr = curr.GetLeft();  // יורדים שמאלה עד הסוף
            }
   
            curr = s.Pop();
            Console.WriteLine(curr.GetValue()); // שורש
   
            curr = curr.GetRight(); // עוברים לתת־עץ ימני
        }
    }