รากหรือลูกแต่ละคน เราเรียกว่าโหนด (node) แต่ละโหนดมีลูกได้ไม่เกิน 2 คน (binary tree) ที่เป็นพี่น้องกัน (sibling) ส่วนโหนดที่ไม่มีลูก เราเรียกว่าโหนดใบ (leaf)

ระดับความลึก (Depth) หรือความสูง (Height) ของต้นไม้นับจากรากลงมา โดยรากมีความลึก 0 และแต่ละระดับจะมีความลึกเพิ่มขึ้นระดับละ 1 เช่นตัวอย่างต้นไม้ในรูปด้านบน จะมีความลึกเป็น 3

1. ให้สร้างต้นไม้เพื่อเก็บนิพจน์ (a+b) * c * (d+e) จากนั้นให้ปีนต้นไม้ เพื่อแสดงนิพจน์ infix prefix และ postfix ตามตัวอย่าง
Hint: เปลี่ยน template [] เป็น [] และสร้างโหนดตามลำดับตามตัวอย่าง

2. กำหนดนิพจน์ postfix: AB*C-DEFG*H$$/+ ให้สร้างนิพจน์ต้นไม้ แล้วปีนต้นไม้ เพื่อหานิพจน์ infix, prefix และ postfix

 		 namespace Tree1 {
  		  using System;
    // BinaryNode class; stores a node in a tree;
    // contains recursive routines to compute size and height.
    //
    // CONSTRUCTION: with (a) no parameters, or (b) an Object,
    //     or (c) an Object, left child, and right child.
    //
    // *******************PUBLIC OPERATIONS**********************
    // int Size( )            --[>] Return size of subtree at node
    // int Height( )          --[>] Return height of subtree at node
    // void PrintPostOrder( ) --[>] Print a postorder tree traversal
    // void PrintInOrder( )   --[>] Print an inorder tree traversal
    // void PrintPreOrder( )  --[>] Print a preorder tree traversal
    // BinaryNode Duplicate( )--[>] Return a duplicate tree
    public class BinaryNode
    {
        private AnyType element;
        private BinaryNode left;
        private BinaryNode right;

        public BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt)
        {
            element = theElement;
            left = lt;
            right = rt;
        }
        // Return the size of the binary tree rooted at t.
        public static int Size(BinaryNode t)
        {
            if (t == null)
                return 0;
            else
                return 1 + Size(t.left) + Size(t.right);
        }
        // Return the height of the binary tree rooted at t.
        public static int Height(BinaryNode t)
        {
            if (t == null)
                return -1;
            else
                return 1 + Math.Max(Height(t.left), Height(t.right));
        }
        // Print tree rooted at current node using preorder traversal.
        public void PrintPreOrder()
        {
            Console.Write(element+" ");        // Node
            if (left != null)
                left.PrintPreOrder();           // Left
            if (right != null)
                right.PrintPreOrder();          // Right
        }
        // Print tree rooted at current node using postorder traversal.
        public void PrintPostOrder()
        {
            if (left != null)
                left.PrintPostOrder();          // Left
            if (right != null)
                right.PrintPostOrder();          // Right
            Console.Write(element+" ");          // Node
        }
        // Print tree rooted at current node using inorder traversal.
        public void PrintInOrder()
        {
            if (left != null)
                left.PrintInOrder();            // Left
            Console.Write(element+" ");       // Node
            if (right != null)
                right.PrintInOrder();           // Right
        }
        // Return a reference to a node that is the root of a
        // duplicate of the binary tree rooted at the current node.
        public BinaryNode Duplicate()
        {
            BinaryNode root = new BinaryNode(element, null, null);

            if (left != null)            // If there's a left subtree
                root.left = left.Duplicate();    // Duplicate; attach
            if (right != null)          // If there's a right subtree
                root.right = right.Duplicate();  // Duplicate; attach
            return root;                      // Return resulting tree
        }
        public AnyType Element
        {
            get
            {
                return element;
            }
            set
            {
                element = value;
            }
        }
        public BinaryNode Left
        {
            get
            {
                return left;
            }
            set
            {
                left = value;
            }
        }
        public BinaryNode Right
        {
            get
            {
                return right;
            }
            set
            {
                right = value;
            }
        }
    }

    // BinaryTree class; stores a binary tree and illustrates the calling of
    // BinaryNode recursive routines and Merge.
    //
    // CONSTRUCTION: with (a) no parameters or (b) an object to
    //    be placed in the root of a one-element tree.
    //
    // *******************PUBLIC OPERATIONS**********************
    // Various tree traversals, Size, Height, IsEmpty, MakeEmpty.
    // Also, the following tricky method
    // void Merge( Object root, BinaryTree t1, BinaryTree t2 )
    //                        --[>]Construct a new tree
    // *******************ERRORS*********************************
    // Error message printed for illegal Merges.
    public class BinaryTree
    {
        private BinaryNode root;
        public BinaryTree()
        {
            root = null;
        }
        public BinaryTree(AnyType rootItem)
        {
            root = new BinaryNode(rootItem, null, null);
        }
        public void PrintPreOrder()
        {
            if (root != null)
                root.PrintPreOrder();
        }
        public void PrintInOrder()
        {
            if (root != null)
                root.PrintInOrder();
        }
        public void PrintPostOrder()
        {
            if (root != null)
                root.PrintPostOrder();
        }
        public void MakeEmpty()
        {
            root = null;
        }
        public bool IsEmpty()
        {
            return root == null;
        }
        // Merge routine for BinaryTree class.
        // Forms a new tree from rootItem, t1 and t2.
        // Does not allow t1 and t2 to be the same.
        // Correctly handles other aliasing conditions.
        public void Merge(AnyType rootItem, BinaryTree t1, BinaryTree t2)
        {
            if (t1.root == t2.root && t1.root != null)
            {
                Console.Error.WriteLine("leftTree==rightTree; merge aborted");
                return;
            }
            // Allocate new node
            root = new BinaryNode(rootItem, t1.root, t2.root);
            // Ensure that every node is in one tree
            if (this != t1)
                t1.root = null;
            if (this != t2)
                t2.root = null;
        }
        public int Size()
        {
            return BinaryNode.Size(root);
        }
        public int Height()
        {
            return BinaryNode.Height(root);
        }
        public BinaryNode Root
        {
            get
            {
                return root;
            }
        }
    }
}

class Program
    {
        public static void Main(string[] args)
        {
            BinaryTree t1 = new BinaryTree(1);
            BinaryTree t3 = new BinaryTree(3);
            BinaryTree t5 = new BinaryTree(5);
            BinaryTree t7 = new BinaryTree(7);
            BinaryTree t2 = new BinaryTree();
            BinaryTree t4 = new BinaryTree();
            BinaryTree t6 = new BinaryTree();

            t2.Merge(2, t1, t3);
            t6.Merge(6, t5, t7);
            t4.Merge(4, t2, t6);
            Console.WriteLine("t4 should be perfect 1-7; t2 empty");
            Console.WriteLine("----------------");
            Console.WriteLine("t4");
            t4.PrintInOrder();
            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.WriteLine("t2");
            t2.PrintInOrder();
            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.WriteLine("t4 size: " + t4.Size());
            Console.WriteLine("t4 height: " + t4.Height());

            Console.WriteLine("t4 In Order");
            t4.PrintInOrder();
            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.WriteLine("t4 Pre Order");
            t4.PrintPreOrder();
            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.WriteLine("t4 Post Order");
            t4.PrintPostOrder();
            Console.WriteLine();
            Console.WriteLine("----------------");
            Console.ReadKey();
        }
    }