C# Binary Trees - Edge Hill University

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
/// <summary>
/// The BinaryTree class implements a simple non-balanced sorted Binary Tree in C#
    /// From http://www.dijksterhuis.org/implementing-a-generic-binary-tree-in-c/
/// </summary>
/// <typeparam name="T">The tree can contain any type, but you are required to provide your own comparison function.</typeparam>

    class BinaryTree<T>
    {
        /// <summary>
        /// The tree is build up out of BinaryTreeNode instances
        /// </summary>

        class BinaryTreeNode
        {
            public BinaryTreeNode Left;
            public BinaryTreeNode Right;
            public BinaryTreeNode Parent;
            public T Data;

            public BinaryTreeNode()
            {
                Left = null;
                Right = null;
                Parent = null;
            }
        }

        BinaryTreeNode Root;
        Comparison<T> CompareFunction;

        /// <summary>
        /// The BinaryTree constructor requires that we pass a comparison function. We need one as generics can only
        /// be compared as equals, but not for order. The solution is to allow the caller to pass a suitable comparison
        /// function. We use the C# Comparison delegate for this (found in System.Collections)
        /// </summary>

        /// <param name="theCompareFunction">Pass a delegate function of the type Comparison to the function</param>

        public BinaryTree(Comparison<T> theCompareFunction)
        {
            Root = null;
            CompareFunction = theCompareFunction;
        }

        /// <summary>
        /// For integer comparisons we provide a demonstration function.
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns>&lt;0 for left smaller than right, &gt;0 if they are equal, +1 if right is larger than left</returns>

        public static int CompareFunction_Int(int left, int right)
        {
            return left - right;
        }

        public void preorderTraversal()
        {
            // Left children, then right children
            // eg 5213
            // 5
            // 2
            // 1
            // 3

            if (Root != null)
            {
                // node in the tree we wish to process
                BinaryTreeNode currentNode = Root;

                BinaryTreeNode lastNode = Root;
                Boolean process = true;
                int nodesProcessed = 0;
                while (nodesProcessed != 11)
                {
                    if (process)
                    {
                        Console.Write(currentNode.Data.ToString());
                        nodesProcessed = nodesProcessed + 1;
                    }
                    process = true;

                    // The node is not left, the last node is not left or right

                    if (currentNode.Left != null && lastNode != currentNode.Left && lastNode != currentNode.Right)
                    {
                        // Shift it to the left
                        lastNode = currentNode;
                        currentNode = currentNode.Left;
                    }

                    // The current node is not right, so shift it to the right
                    else if (currentNode.Right != null && lastNode != currentNode.Right)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Right;
                    }

                    // Its on the parent node, set the flag to false so that it does
                      // not increment the loop and repeat the process
                    else if (currentNode.Parent != null)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Parent;
                        process = false;
                    }
                }
            }
            else
            {
                Console.WriteLine("There is no tree to process");
            }
        }



        // InORDER:
        // IF LEFT EXISTS, GOTO AND PROCESS
        // ELSE PROCESS PARENT NODE
        // IF RIGHT EXSISTS, TRANSFER AND PROCESS


        public void inorderTraversal()
        {
            // No node exists.
            if (Root == null)
            {
                Console.WriteLine("There is no tree to process");
                return;
            }

            BinaryTreeNode currentNode = Root;
            BinaryTreeNode lastNode = Root;
            Boolean process = true;
            int nodesProcessed = 0;

            while (nodesProcessed != 11)
            {
                if (process)
                {
                    Console.Write(currentNode.Data.ToString());
                    nodesProcessed = nodesProcessed + 1;
                }
                process = true;


                // Are there any left nodes available?
                if (currentNode.Left != null)
                {
                    // OK
                    // Step 1: Go to furtherest most left node:
                    while (currentNode.Left != null)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Left;
                    }

                    // Ok we're at the left most node, process it.
                    process = true; // Don't have to include this, just makes it more readable
                    continue;
                }

                // No left nodes - process parent node then check the right.
                else if (currentNode.Parent != null)
                {
                    lastNode = currentNode;
                    currentNode = currentNode.Parent;

                    process = true; // Don't have to include this, just makes it more readable
                    continue;
                }
                    // Finally check for any right nodes
                else if (currentNode.Right != null)
                {
                    lastNode = currentNode;
                    currentNode = currentNode.Right;
                    process = true; // readability
                }

            }

        }

        /*

         NOT WORKING

        public void postorderTraversal()
        {
            if (Root != null)
            {
                BinaryTreeNode currentNode = Root;
                BinaryTreeNode lastNode = Root;

                //  Skip the root, set the initial process as false
                Boolean process = false;

                int nodesProcessed = 0;
                while (nodesProcessed != 11)
                {
                    // Processed a new node
                    // print it out and increment the number of nodes processed so we can
                    // keep track when 11 is up
                    if (process == true)
                    {
                        Console.Write(currentNode.Data.ToString() + " ");
                        nodesProcessed++;
                    }



                    // The node is not left, the last node is not left or right

                    if (currentNode.Left != null && lastNode != currentNode.Left && lastNode != currentNode.Right)
                    {
                        // Shift it to the left
                        lastNode = currentNode;
                        currentNode = currentNode.Left;
                    }

                    // The current node is not right, so shift it to the right
                    else if (currentNode.Right != null && lastNode != currentNode.Right)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Right;
                    }

                    // Its on the parent node, set the flag to false so that it does
                    // not increment the loop and repeat the process
                    else if (currentNode.Parent != null)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Parent;
                        process = false;
                    }




        */






              /*      // Are there any left children?
                    if (currentNode.Left != null)
                    {
                        if (left_side == false)
                        {
                            left_side = true;
                        }

                        lastNode = currentNode;
                        currentNode = currentNode.Left;
                        process = false;
                    }
                    // Okay if its looping through the left side and there aren't any children
                    // left we've reached the final one so we can go back up to the parent then proceed to the right

                    else if (left_side == true && currentNode.Left == null)
                    {
                        left_side = false;
                        process = true;
                        lastNode = currentNode;
                        currentNode = currentNode.Parent;
                        continue;
                    }

                    if (currentNode == currentNode.Parent)
                    {
                        if(
                    }

                    */










                    /*//         process = true;


                    // There are NO more nodes on the left
                    if (currentNode.Left == null)
                    {
               //         Console.WriteLine("  its null");

                        // Now shift to the right
                        if (currentNode.Right != null)
                        {
                            lastNode = currentNode;
                            currentNode = currentNode.Right;
                            currentNode.Left = null;
                        }
                    }

                    // This is NOT the last child on the left
                    // so do not process it
                    if (currentNode.Left != null)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Left;
                        process = false;
                    }
                    else
                    {
                        process = true;
                    }





                    */




                    // First step: needs to go through all the left children

                    /*
                    // PRINT ALL LEFT CHILDREN, ONLY ONCE
                    if (currentNode.Left != null)
                    {
                        if (currentNode.Left == lastNode)
                        {
                            // root is the default objects that these are assigned to
                            // so add an exception for this
                            if (currentNode != Root && lastNode != Root)
                            {
                                process = false;
                            }
                            continue;
                        }

                        lastNode = currentNode;
                        currentNode = currentNode.Left;
                    }

                    */
                    /*
                    // There is (another) left child that exists.

                    if (currentNode.Left != null)
                    {
                        // This is another node in the list
                        if (currentNode != lastNode)
                        {
                            lastNode = currentNode;
                            currentNode = currentNode.Left;
                            continue;
                        }
                        else if (currentNode == lastNode && currentNode != Root)
                        {
                            process = false;
                        }
             //           else if (currentNode == lastNode)
               //         {
                 //           process = false;
                   //     }
                     * }
                    */


/*
                    // No more children on the left side.
                    // Go back up to the root
                    else if(currentNode.Left == null)
                    {
                        lastNode = currentNode;
                        currentNode = currentNode.Parent;

                        // Skip the process here or it will just go back through
                        process = false;
                    }

                    // there is a right node here
                    if (currentNode.Right != null)
                    {
                        // process it!
                        lastNode = currentNode;
                        currentNode = currentNode.Right;
                    }*

                }
            }
            else
            {
                Console.WriteLine("There is no tree to process");
            }
        }
        */


        /// <summary>
        /// For string comparisons we provide a demonstration function
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns>-1 for left smaller than right, 0 if they are equal, +1 if right is larger than left</returns>

        public static int CompareFunction_String(string left, string right)
        {
            return left.CompareTo(right);
        }

        /// <summary>
        /// The add function uses non-recursive tree traversal to find the next available insertion point
        /// </summary>
        /// <param name="Value">The value to insert into tree.</param>

        public void Add(T Value)
        {
            BinaryTreeNode child = new BinaryTreeNode();
            child.Data = Value;
            // Is the tree empty? Make the root the new child
            if (Root == null)
            {
                Root = child;
            }
            else
            {
                // Start from the root of the tree
                BinaryTreeNode Iterator = Root;
                while (true)
                {
                    // Compare the value to insert with the value in the current tree node
                    int Compare = CompareFunction(Value, Iterator.Data);
                    // The value is smaller or equal to the current node, we need to store it on the left side

                    // We test for equivalence as we allow duplicates (!)
                    if (Compare <= 0)
                        if (Iterator.Left != null)
                        {
                            // Travel further left
                            Iterator = Iterator.Left;
                            continue;
                        }
                        else
                        {
                            // An empty left leg, add the new node on the left leg
                            Iterator.Left = child;
                            child.Parent = Iterator;
                            break;
                        }

                    if (Compare > 0)
                        if (Iterator.Right != null)
                        {
                            // Continue to travel right
                            Iterator = Iterator.Right;
                            continue;
                        }
                        else
                        {
                            // Add the child to the right leg
                            Iterator.Right = child;
                            child.Parent = Iterator;
                            break;
                        }
                }
            }
        }

        /// <summary>
        /// This routine walks through the tree to see if the value given can be found.
        /// </summary>
        /// <param name="Value">The value to look for in the tree</param>
        /// <returns>True if found, False if not found</returns>

        public bool Find(T Value)
        {
            BinaryTreeNode Iterator = Root;
            while (Iterator != null)
            {
                int Compare = CompareFunction(Value, Iterator.Data);
                // Did we find the value ?
                if (Compare == 0) return true;
                if (Compare < 0)
                {
                    // Travel left
                    Iterator = Iterator.Left;
                    continue;
                }
                // Travel right
                Iterator = Iterator.Right;
            }
            return false;
        }

        /// <summary>
        /// Given a starting node, this routine will locate the left most node in the sub-tree
        /// If no further nodes are found, it returns the starting node
        /// </summary>

        /// <param name="start">The sub-tree starting point</param>
        /// <returns></returns>

        BinaryTreeNode FindMostLeft(BinaryTreeNode start)
        {
            BinaryTreeNode node = start;
            while (true)
            {
                if (node.Left != null)
                {
                    node = node.Left;
                    continue;
                }
                break;
            }
            return node;
        }

        /// <summary>
        /// Returns a list iterator of the elements in the tree implementing the IENumerator interface.
        /// </summary>
        /// <returns>IENumerator</returns>

        public IEnumerator<T> GetEnumerator()
        {
            return new BinaryTreeEnumerator(this);
        }

        /// <summary>
        /// The BinaryTreeEnumerator implements the IEnumerator allowing foreach enumeration of the tree
        /// </summary>

        class BinaryTreeEnumerator : IEnumerator<T>
        {
            BinaryTreeNode current;
            BinaryTree<T> theTree;
            public BinaryTreeEnumerator(BinaryTree<T> tree)
            {
                theTree = tree;
                current = null;
            }

            /// <summary>
            /// The MoveNext function traverses the tree in sorted order.
            /// </summary>

            /// <returns>True if we found a valid entry, False if we have reached the end</returns>

            public bool MoveNext()
            {
                // For the first entry, find the lowest valued node in the tree
                if (current == null)
                    current = theTree.FindMostLeft(theTree.Root);
                else
                {
                    // Can we go right-left?
                    if (current.Right != null)
                        current = theTree.FindMostLeft(current.Right);
                    else
                    {
                        // Note the value we have found
                        T CurrentValue = current.Data;
                        // Go up the tree until we find a value larger than the largest we have
                        // already found (or if we reach the root of the tree)
                        while (current != null)
                        {
                            current = current.Parent;
                            if (current != null)
                            {
                                int Compare = theTree.CompareFunction(current.Data,CurrentValue);
                                if (Compare < 0) continue;
                            }
                            break;
                        }
                    }
                }
                return (current != null);
            }

            public T Current
            {
                get
                {
                    if (current == null)
                        throw new InvalidOperationException();
                    return current.Data;
                }
            }

            object System.Collections.IEnumerator.Current
            {
                get
                {
                    if (current == null)
                        throw new InvalidOperationException();
                    return current.Data;
                }
            }

            public void Dispose() { }

            public void Reset() { current = null; }

        }
    }

    class TreeTest
    {
        static BinaryTree<int> Test = new BinaryTree<int>(BinaryTree<int>.CompareFunction_Int);

        static void Main(string[] args)
        {

            // Build the tree
            Test.Add(5);
            Test.Add(2);
            Test.Add(1);
            Test.Add(3);
            Test.Add(3); // Duplicates are OK
            Test.Add(4);
            Test.Add(6);
            Test.Add(10);
            Test.Add(7);
            Test.Add(8);
            Test.Add(9);
            // Test if we can find values in the tree

            for (int Lp = 1; Lp <= 10; Lp++)
                Console.WriteLine("Find ({0}) = {1}", Lp,Test.Find(Lp));

            // Test if we can find a non-existing value
            Console.WriteLine("Find (999) = {0}", Test.Find(999));

            // Iterate over all members in the tree -- values are returned in sorted order
            foreach(int value in Test)
            {
                Console.WriteLine("Value: {0}", value);
            }
//
            Console.WriteLine("Preorder traversal");
            Test.preorderTraversal();
//
            Console.WriteLine("inorder traversal");
            Test.inorderTraversal();
            Console.WriteLine("\n");
        }

    }

}