Binary Tree in C#

This short article show you the Tree creation and traversal using C#

 

I didn’t create from nothing, I rather take it from https://chinmaylokesh.wordpress.com/2012/02/16/tree-sort-in-order-traversal-of-a-binary-search-tree/.  

 

I will also avoid the long article. Go to read the theory in other article. This is more for those know the theory well bot do not remember how to code it immediately. Read the remark I added.

 

 

using System;

using System.Collections.Generic;

using System.Text;

 

namespace TreeSort

{

    //This class is the structure of the binary tree

    class Node

    {

        public int item;

        public Node leftChild;

        public Node rightChild;

        public void displayNode()

        {

            Console.Write(“[“);

            Console.Write(item);

            Console.Write(“]”);

        }

    }

    //This class build the root node, insert node.

    //The pre, pro and In-order traversal are all in this class

    class Tree

    {

        public Node root;

        public Tree()

        { root = null; }

        public Node ReturnRoot()

        {

            return root;

        }

        //Here is the location to insert node

        public void Insert(int id)

        {

            Node newNode = new Node();

            newNode.item = id;

            if (root == null)

                root = newNode;

            else

            {

                Node current = root;

                Node parent;

                while (true)

                {

                    parent = current;

                    if (id < current.item)

                    {

                        current = current.leftChild;

                        if (current == null)

                        {

                            parent.leftChild = newNode;

                            return;

                        }

                    }

                    else

                    {

                        current = current.rightChild;

                        if (current == null)

                        {

                            parent.rightChild = newNode;

                            return;

                        }

                    }

                }

            }

        }

        //This is the preorder traversal

        public void Preorder(Node Root)

        {

            if (Root != null)

            {

                Console.Write(Root.item + ” “);

                Preorder(Root.leftChild);

                Preorder(Root.rightChild);

            }

        }

       //This is the inorder traversal

        public void Inorder(Node Root)

        {

            if (Root != null)

            {

                Inorder(Root.leftChild);

                Console.Write(Root.item + ” “);

                Inorder(Root.rightChild);

            }

        }

        //This is the postorder traversal

        public void Postorder(Node Root)

        {

            if (Root != null)

            {

                Postorder(Root.leftChild);

                Postorder(Root.rightChild);

                Console.Write(Root.item + ” “);

            }

        }

    }

    class Program

    {

        static void Main(string[] args)

        {

            Tree theTree = new Tree();

            theTree.Insert(42);

            theTree.Insert(25);

            theTree.Insert(65);

            theTree.Insert(12);

            theTree.Insert(37);

            theTree.Insert(13);

            theTree.Insert(30);

            theTree.Insert(43);

            theTree.Insert(87);

            theTree.Insert(99);

            theTree.Insert(9);

 

            Console.WriteLine(“Inorder traversal resulting Tree Sort”);

            theTree.Inorder(theTree.ReturnRoot());

            Console.WriteLine(” “);

 

            Console.WriteLine();

            Console.WriteLine(“Preorder traversal”);

            theTree.Preorder(theTree.ReturnRoot());

            Console.WriteLine(” “);

 

            Console.WriteLine();

            Console.WriteLine(“Postorder traversal”);

            theTree.Postorder(theTree.ReturnRoot());

            Console.WriteLine(” “);

 

            Console.ReadLine();

        }

    }

}

 

To understand the inorder, preorder, and postorder I extracted the illustration form http://www.geeksforgeeks.org/618/.

 

clip_image001

Inorder Traversal:

Algorithm Inorder(tree)

   1. Traverse the left subtree, i.e., call Inorder(left-subtree)

   2. Visit the root.

   3. Traverse the right subtree, i.e., call Inorder(right-subtree)

 

Example: Inorder traversal for the above given figure is 4 2 5 1 3.

Preorder Traversal:

Algorithm Preorder(tree)
   1. Visit the root.
   2. Traverse the left subtree, i.e., call Preorder(left-subtree)
   3. Traverse the right subtree, i.e., call Preorder(right-subtree)

 

Example: Preorder traversal for the above given figure is 1 2 4 5 3.

Postorder Traversal:

Algorithm Postorder(tree)
   1. Traverse the left subtree, i.e., call Postorder(left-subtree)
   2. Traverse the right subtree, i.e., call Postorder(right-subtree)
   3. Visit the root.   
 

Example: Postorder traversal for the above given figure is 4 5 2 3 1.

You can also download a single solution from http://skydrive.live.com. The sample file name is ConAppTreeTraversal.zip. My MSN ID is chanmmn@hotmail.com.

 

About chanmingman

Since March 2011 Microsoft Live Spaces migrated to Wordpress (http://www.pcworld.com/article/206455/Microsoft_Live_Spaces_Moves_to_WordPress_An_FAQ.html) till now, I have is over 1 million viewers. This blog is about more than 50% telling you how to resolve error messages, especial for Microsoft products. The blog also has a lot of guidance teaching you how to get stated certain Microsoft technologies. The blog also uses as a help to keep my memory. The blog is never meant to give people consulting services or silver bullet solutions. It is a contribution to the community. Thanks for your support over the years. Ming Man is Microsoft MVP since year 2006. He is a software development manager for a multinational company. With 25 years of experience in the IT field, he has developed system using Clipper, COBOL, VB5, VB6, VB.NET, Java and C #. He has been using Visual Studio (.NET) since the Beta back in year 2000. He and the team have developed many projects using .NET platform such as SCM, and HR based applications. He is familiar with the N-Tier design of business application and is also an expert with database experience in MS SQL, Oracle and AS 400.
This entry was posted in .Net and tagged , , . Bookmark the permalink.

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