Binary tree sample

public static void TestBinaryTree()
        {
            BinaryTree tree = new BinaryTree("d");
            tree.AddNode("a");
            tree.AddNode("b");
            tree.AddNode("f");
            tree.AddNode("e");
            tree.AddNode("c");
            tree.AddNode("g");
            tree.Print();
            tree.Print();

            Console.WriteLine("tree.TreeSize: " + tree.TreeSize);           
            Console.WriteLine("tree.GetRoot().DepthFirstSearch(a).NumOfChildren: " +
                tree.GetRoot().DepthFirstSearch("b").NumOfChildren);           
            Console.WriteLine("tree.GetRoot().DepthFirstSearch(a).NumOfChildren: " +
                tree.GetRoot().DepthFirstSearch("a").NumOfChildren);           
            Console.WriteLine("tree.GetRoot().DepthFirstSearch(g).NumOfChildren: " +
                tree.GetRoot().DepthFirstSearch("g").NumOfChildren);           

            Console.WriteLine("tree.SearchDepthFirst(a): " +
                tree.SearchDepthFirst("a").Value.ToString());
            Console.WriteLine("tree.SearchDepthFirst(b): " +
                tree.SearchDepthFirst("b").Value.ToString());
            Console.WriteLine("tree.SearchDepthFirst(c): " +
                tree.SearchDepthFirst("c").Value.ToString());
            Console.WriteLine("tree.SearchDepthFirst(d): " +
                tree.SearchDepthFirst("d").Value.ToString());
            Console.WriteLine("tree.SearchDepthFirst(e): " +
                tree.SearchDepthFirst("e").Value.ToString());
            Console.WriteLine("tree.SearchDepthFirst(f): " +
                tree.SearchDepthFirst("f").Value.ToString());

            tree.GetRoot().RemoveLeftNode();
            tree.Print();

            tree.GetRoot().RemoveRightNode();
            tree.Print();
        }

        public class BinaryTree
        {
            public BinaryTree() {}

            public BinaryTree(IComparable value, int index)
            {
                BinaryTreeNode node = new BinaryTreeNode(value, index);
                root = node;
                counter = 1;
            }

            // Use this .ctor when you need to flatten this tree (see recipe 9.15)
            public BinaryTree(IComparable value)
            {
                BinaryTreeNode node = new BinaryTreeNode(value);
                root = node;
                counter = 1;
            }

            protected int counter = 0;             // Number of nodes in tree
            protected BinaryTreeNode root = null;  // Pointer to root node in this tree

            public  void AddNode(IComparable value, int index)
            {
                BinaryTreeNode node = new BinaryTreeNode(value, index);
                ++counter;

                if (root == null)
                {
                    root = node;
                }
                else
                {
                    root.AddNode(node);
                }
            }

            // Use this method to add a node
            //    when you need to flatten this tree (see recipe 9.15)
            public int AddNode(IComparable value)
            {
                BinaryTreeNode node = new BinaryTreeNode(value);
                ++counter;

                if (root == null)
                {
                    root = node;
                }
                else
                {
                    root.AddNode(node);
                }

                return (counter – 1);
            }

            public BinaryTreeNode SearchDepthFirst(IComparable value)
            {
                return (root.DepthFirstSearch(value));
            }

            public void Print()
            {
                root.PrintDepthFirst();
            }

            public BinaryTreeNode GetRoot()
            {
                return (root);
            }

            public int TreeSize
            {
                get {return (counter);}
            }       
        }

        public class BinaryTreeNode
        {
            public BinaryTreeNode() {}

            public BinaryTreeNode(IComparable value)
            {
                nodeValue = value;
            }

            // These 2 ctors Added to allow tree to be flattened
            public BinaryTreeNode(int index)
            {
                nodeIndex = index;
            }

            public BinaryTreeNode(IComparable value, int index)
            {
                nodeValue = value;
                nodeIndex = index;
            }

            protected int nodeIndex = 0;         // Added to allow tree to be flattened
            protected IComparable nodeValue = null;
            protected BinaryTreeNode leftNode = null;     //  leftNode.Value < Value
            protected BinaryTreeNode rightNode = null;    //  rightNode.Value >= Value

            public int NumOfChildren
            {
                get {return (CountChildren());}
            }

            public int CountChildren()
            {
                int currCount = 0;

                if (leftNode != null)
                {
                    ++currCount;
                    currCount += leftNode.CountChildren();
                }

                if (rightNode != null)
                {
                    ++currCount;
                    currCount += rightNode.CountChildren();
                }

                return (currCount);
            }

            public int Index
            {
                get {return (nodeIndex);}
            }

            public BinaryTreeNode Left
            {
                get {return (leftNode);}
            }

            public BinaryTreeNode Right
            {
                get {return (rightNode);}
            }

            public IComparable Value
            {
                get {return (nodeValue);}
            }

            public void AddNode(BinaryTreeNode node)
            {
                if (node.nodeValue.CompareTo(nodeValue) < 0)
                {
                    if (leftNode == null)
                    {
                        leftNode = node;
                    }
                    else
                    {
                        leftNode.AddNode(node);
                    }
                }
                else if (node.nodeValue.CompareTo(nodeValue) >= 0)
                {
                    if (rightNode == null)
                    {
                        rightNode = node;
                    }
                    else
                    {
                        rightNode.AddNode(node);
                    }
                }
            }

            public bool AddUniqueNode(BinaryTreeNode node)
            {
                bool isUnique = true;

                if (node.nodeValue.CompareTo(nodeValue) < 0)
                {
                    if (leftNode == null)
                    {
                        leftNode = node;
                    }
                    else
                    {
                        leftNode.AddNode(node);
                    }
                }
                else if (node.nodeValue.CompareTo(nodeValue) > 0)
                {
                    if (rightNode == null)
                    {
                        rightNode = node;
                    }
                    else
                    {
                        rightNode.AddNode(node);
                    }
                }
                else   //node.nodeValue.CompareTo(nodeValue) = 0
                {
                    isUnique = false;
                    // Could throw exception here as well…
                }

                return (isUnique);
            }

            public BinaryTreeNode DepthFirstSearch(IComparable targetObj)
            {
                // NOTE: foo.CompareTo(bar) == -1   –>   (foo < bar)
                BinaryTreeNode retObj = null;
                int comparisonResult = targetObj.CompareTo(nodeValue);

                if (comparisonResult  == 0)
                {
                    retObj = this;
                }
                else if (comparisonResult > 0)
                {
                    if (rightNode != null)
                    {
                        retObj = rightNode.DepthFirstSearch(targetObj);
                    }
                }
                else if (comparisonResult < 0)
                {
                    if (leftNode != null)
                    {
                        retObj = leftNode.DepthFirstSearch(targetObj);
                    }
                }

                return (retObj);
            }

            public void PrintDepthFirst()
            {
                if (leftNode != null)
                {
                    leftNode.PrintDepthFirst();
                }

                Console.WriteLine(this.nodeValue.ToString());

                try
                {
                    Console.WriteLine("\tContains Left: " +
                        leftNode.nodeValue.ToString());
                }
                catch
                {
                    Console.WriteLine("\tContains Left:  NULL");
                }
                try
                {
                    Console.WriteLine("\tContains Right: " +
                        rightNode.nodeValue.ToString());
                }
                catch
                {
                    Console.WriteLine("\tContains Right: NULL");
                }

                if (rightNode != null)
                {
                    rightNode.PrintDepthFirst();
                }
            }

            public void RemoveLeftNode()
            {
                leftNode = null;
            }

            public void RemoveRightNode()
            {
                rightNode = null;
            }
        }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s