Arsalan's Musings on Software

Software design and development techniques, ideas, and source code snippets…

Archive for February 2008

Tree Traversals For Strongly-Typed Generic Trees (C# Solution)

leave a comment »

Copyright (2008) Ahmed Arsalan. All Rights Rserved.


using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace TreeTraversals

{

    class TreeTraversalsLauncher

    {

        static void Main(string[] args)

        {

            TreeTraversals treeTraversal = new TreeTraversals();

            Console.WriteLine("The tree has been initialized to:");

            foreach (TreeNode node in treeTraversal.Tree)

            {

                Console.Write(node.NodeValue.ToString() + " ");

            }

            Console.WriteLine();

            treeTraversal.Traversed.Clear();

            treeTraversal.InOrderTraversal(treeTraversal.Root);

            Console.WriteLine("In Order traversal processes nodes in the following order:");

            foreach (int node in treeTraversal.Traversed)

            {

                Console.Write(node.ToString() + " ");

            }

            Console.WriteLine();

            treeTraversal.Traversed.Clear();

            treeTraversal.PreOrderTraversal(treeTraversal.Root);

            Console.WriteLine("Pre Order traversal processes nodes in the following order:");

            foreach (int node in treeTraversal.Traversed)

            {

                Console.Write(node.ToString() + " ");

            }

            Console.WriteLine();

            treeTraversal.Traversed.Clear();

            treeTraversal.PostOrderTraversal(treeTraversal.Root);

            Console.WriteLine("Post Order traversal processes nodes in the following order:");

            foreach (int node in treeTraversal.Traversed)

            {

                Console.Write(node.ToString() + " ");

            }

            Console.ReadKey();

        }

    }

    public class TreeNode

    {

        #region ----- Private Data Members -----

        private T nodeValue;

        private TreeNode left;

        private TreeNode right;

        #endregion

        #region ----- Public Properties -----

        public T NodeValue

        {

            get

            {

                return this.nodeValue;

            }

            set

            {

                this.nodeValue = value;

            }

        }

        public TreeNode Left

        {

            get

            {

                return this.left;

            }

            set

            {

                this.left = value;

            }

        }

        public TreeNode Right

        {

            get

            {

                return this.right;

            }

            set

            {

                this.right = value;

            }

        }

        #endregion

    }

    public class TreeTraversals

    {

        #region ----- Constructors -----

        public TreeTraversals()

        {

            root = new TreeNode();

            tree = new List<treenode>();

            traversed = new List();

            PopulateInitialTree();

        }

        #endregion

        #region ----- Private Data Members -----

        private TreeNode root;

        private List < TreeNode < int > > tree;

        private List traversed;

        #endregion

        #region ----- Public Properties -----

        public TreeNode Root

        {

            get

            {

                return this.root;

            }

        }

        public List Traversed

        {

            get

            {

                return this.traversed;

            }

        }

        public List < TreeNode < int > > Tree >

        {

            get

            {

                return this.tree;

            }

        }

        #endregion

        #region ----- Private Methods -----

        private void PopulateInitialTree()

        {

            TreeNode node8 = new TreeNode();

            node8.NodeValue = 99;

            node8.Left = null;

            node8.Right = null;

            TreeNode node7 = new TreeNode();

            node7.NodeValue = 62;

            node7.Left = null;

            node7.Right = null;

            TreeNode node6 = new TreeNode();

            node6.NodeValue = 4;

            node6.Left = node7;

            node6.Right = node8;

            TreeNode node5 = new TreeNode();

            node5.NodeValue = 100;

            node5.Left = null;

            node5.Right = null;

            TreeNode node4 = new TreeNode();

            node4.NodeValue = 68;

            node4.Left = null;

            node4.Right = null;

            TreeNode node3 = new TreeNode();

            node3.NodeValue = 151;

            node3.Left = null;

            node3.Right = node5;

            TreeNode node2 = new TreeNode();

            node2.NodeValue = 10;

            node2.Left = node4;

            node2.Right = null;

            TreeNode node1 = new TreeNode();

            node1.NodeValue = 6;

            node1.Left = node2;

            node1.Right = node3;

            root.NodeValue = 5;

            root.Left = node1;

            root.Right = node6;

            this.tree.Add(root);

            this.tree.Add(node1);

            this.tree.Add(node2);

            this.tree.Add(node3);

            this.tree.Add(node4);

            this.tree.Add(node5);

            this.tree.Add(node6);

            this.tree.Add(node7);

            this.tree.Add(node8);

        }

        #endregion

        #region ----- Public Methods -----

        public void InOrderTraversal(TreeNode root)

        {

            if (root == null) return;

            InOrderTraversal(root.Left);

            Traversed.Add(root.NodeValue);

            InOrderTraversal(root.Right);

        }

        public void PreOrderTraversal(TreeNode root)

        {

            if (root == null) return;

            Traversed.Add(root.NodeValue);

            PreOrderTraversal(root.Left);

            PreOrderTraversal(root.Right);

        }

        public void PostOrderTraversal(TreeNode root)

        {

            if (root == null) return;

            PostOrderTraversal(root.Right);

            Traversed.Add(root.NodeValue);

            PostOrderTraversal(root.Left);

        }

        #endregion

    }

}

}
Advertisements

Written by Arsalan A.

February 17, 2008 at 1:04 pm

Posted in 1