Tree ADT - Array Implementation

Tree Class
--------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace Tree_Adt_Array_Implementation
{
     class BinaryTree
     {
          private int [] tree;
          private int size;

          public BinaryTree(int size)
          {
               this.size = size;
               tree = new int[size + 1];
          }

          public void CreateBinaryTree()
          {
               for (int i = 1; i <= size; i++)
               {
                    Console.Write("Enter an integer : ");
                    tree[i] = int.Parse(Console.ReadLine());
               }
          }

          public int searchIndex(int value)
          {
               int i = 1;
               while (i <= size)
               {
                    if (value == tree[i])
                         return i;
                    i++;
               }
               return 0;

          }

          public int parent(int value)
          {
               int index;
               index = searchIndex(value);
               if (index == 0)
               {
                    Console.WriteLine("Node does not exist.");
                    return 0;
               }
               else
                    return tree[index / 2];
          }

          public int leftchild(int value)
          {
               int index;
               index = searchIndex(value);
               if (index == 0)
               {
                    Console.WriteLine("Node does not exist.");
                    return 0;
               }
               else
                    return tree[index * 2];
          }

          public int rightchild(int value)
          {
               int index;
               index = searchIndex(value);
               if (index == 0)
               {
                    Console.WriteLine("Node does not exist.");
                    return 0;
               }
               else
                    return tree[index * 2 + 1];
          }
     }
}








Driver Program Using Tree ADT
----------------------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace Tree_Adt_Array_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               BinaryTree bt = new BinaryTree(7);
               bt.CreateBinaryTree(); //input: {20, 7, 25, 10, 15, 30, 22}
               Console.WriteLine("Left child of node 7 {0}",bt.leftchild(7)); //node 10
               Console.WriteLine("Right child of node 7 {0}", bt.rightchild(7)); //node 15
               Console.WriteLine("Parent of node 7 {0}", bt.parent(20)); // 20

               Console.ReadKey();
          }
     }
}

Binary Search Tree - Linked List Implementation

Node Class
----------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace BST_Linked_List_Implementation
{
     class Node
     {
          public int item;
          public Node parent;
          public Node left;
          public Node right;

          public Node()
          {
          }

          public Node(int item)
          {
               this.item = item;
          }

          public int Item
          {
               get { return item; }
          }

     }
}


BST Class
------------------------------------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace BST_Linked_List_Implementation
{
     class BST
     {
         

          private Node root;

          public BST()
          {
               root = null;
          }

          public Node Root
          {
               get { return root; }
          }

          public void insert(int item)
          {
               Node x, y;
               Node z = new Node(item);
               y = null;
               x = root;
               while (x != null)
               {
                    y = x;
                    if (z.item < x.item)
                         x = x.left;
                    else
                         x = x.right;
               }
               z.parent = y;
               if (y == null)
                    root = z;
               else
               {
                    if (z.item < y.item)
                         y.left = z;
                    else
                         y.right = z;
               }
          }

          public void preorder(Node root)
          {
               if (root != null)
               {
                    Console.Write("{0} ", root.item);
                    preorder(root.left);
                    preorder(root.right);
               }
          }

          public void inorder(Node root)
          {
               if (root != null)
               {
                    inorder(root.left);
                    Console.Write("{0} ", root.item);
                    inorder(root.right);
               }
          }

          public void postorder(Node root)
          {
               if (root != null)
               {
                    postorder(root.left);
                    postorder(root.right);
                    Console.Write("{0} ", root.item);
               }
          }

          public Node minimum(Node root)
          {
               Node ptr = root;

               while (ptr.left != null)
               {
                    ptr = ptr.left;
               }
               return ptr;
          }

          public Node maximum(Node root)
          {
               Node ptr = root;

               while (ptr.right != null)
               {
                    ptr = ptr.right;
               }
               return ptr;
          }

          public Node successor(Node ptr)
          {
              Node succ;
               if (ptr.right != null)
                   return minimum(ptr.right);
               succ = ptr.parent;
               while (succ != null && ptr == succ.right)
               {
                    ptr = succ;
                    succ = succ.parent;
               }
               return succ;
          }

          public Node search(Node root, int item)
          {
               while (root != null && item != root.item)
               {
                    if (item < root.item)
                         root = root.left;
                    else
                         root = root.right;
               }
               return root;
          }

          public void  delete(Node root,  Node z)
          {
               Node x, y;

              if ( z.left == null || z.right == null)
                   y = z;
              else
                   y = successor(z);
              if (y.left != null)
                   x = y.left;
              else
                   x = y.right;
              if ( x != null)
                   x.parent = y.parent;
              if (y.parent == null)
                   root = x;
              else {
                   if ( y == y.parent.left)
                        y.parent.left = x;
                  else
                       y.parent.right = x;
              }

               if ( y != z) {
                    z.item = y.item;
               }
          }

          public bool isEmpty()
          {
               return root == null;
          }
     }
}

Driver Program Using BST Class
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace BST_Linked_List_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               BST bst = new BST();
              
               bst.insert(20);
               bst.insert(10);
               bst.insert(30);
               bst.insert(5);
               bst.insert(15);
               bst.insert(25);
               bst.insert(35);

               bst.preorder(bst.Root);
               Console.WriteLine();
               bst.inorder(bst.Root);
               Console.WriteLine();
               bst.postorder(bst.Root);
               Console.WriteLine();
               Console.WriteLine("Minimum = {0}", bst.minimum(bst.Root).Item.ToString());
               Console.WriteLine("Maximum = {0}", bst.maximum(bst.Root).Item.ToString());
               Node ptr = bst.search(bst.Root, 20);
               if (ptr != null)
               {
                    bst.delete(bst.Root, ptr);
               }
               bst.inorder(bst.Root);
               Console.WriteLine();
              

               Console.ReadKey();

          }
     }
}

SET ADT - Array Implementation

using System;

namespace Set_Array_Implementation
{
     class Set
     {
          private bool [] set;
          private int size;

          public bool isMember(int element)
          {
               return set[element];
          }

          public void insert(int element)
          {
               set[element] = true;
          }

          public void delete(int element)
          {
               set[element] = false;
          }

          public void makenull()
          {
               for (int i = 1; i <= size; i++)
                    set[i] = false;
          }

          public Set(int size)
          {
               this.size = size;
               set = new bool[this.size + 1];
          }

          public bool isEmpty()
          {         
               foreach (bool element in set)
               {
                    if (element)
                         return false;
               }
               return true;
          }

          public Set Union(Set S)
          {
               Set newSet = new Set(size + 1);
               for (int i = 1; i <= size; i++)
               {
                    if (isMember(i) || S.isMember(i))
                    {
                         newSet.insert(i);
                    }
               }
               return newSet;
          }

          public Set Intersection(Set S)
          {
               Set newSet = new Set(size + 1);
               for (int i = 1; i <= size; i++)
               {
                    if (isMember(i) && S.isMember(i))
                    {
                         newSet.insert(i);
                    }
               }
               return newSet;
          }

          public Set Difference(Set S)
          {
               Set newSet = new Set(size + 1);
               for (int i = 1; i <= size; i++)
               {
                    if (isMember(i) && !S.isMember(i))
                    {
                         newSet.insert(i);
                    }
               }
               return newSet;
          }

          public void print()
          {
               string str = "";
               for (int i = 1; i <= size; i++)
               {
                    if (set[i])
                         str +=  i + " ";
               }
              
               if (str.Equals(""))
               {
                    Console.WriteLine("Set is Empty");
               }
               else
               {
                    Console.WriteLine("{" + string.Join(", ", str.TrimEnd().Split(' ')) + "}");
               }
          }

     }
}

--------------------------------------------------------------------------------------------------------------------


Driver Program Using Set ADT





using System;

namespace Set_Array_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               Set A = new Set(10);
               Set B = new Set(10);
               Set C;

               A.insert(1);
               A.insert(3);
               A.insert(4);
               Console.Write("Set A = ");
               A.print();

               B.insert(2);
               B.insert(3);
               B.insert(5);
               Console.Write("Set B = ");
               B.print();

               C = A.Union(B);
               Console.Write("Union of A and B = ");
               C.print();

               C = A.Intersection(B);
               Console.Write("Intersection of A and B = ");
               C.print();

               C = A.Difference(B);
               Console.Write("Difference of A and B = ");
               C.print();

               Console.WriteLine("Press any key to continue.");
               Console.ReadKey();  
          }
     }
}

SET ADT - Linked List Implementation

using System;

namespace Set_Linked_List_Implementation
{
     class Set
     {
          public class Node
          {
               public object item;
               public Node next;

               public Node()
               {
               }

               public Node(object item)
               {
                    this.item = item;
               }
          }

          private int length;
          private Node head;

          public Set()
          {
               length = 0;
               head = null;
          }

          public int Length
          {
               get { return length; }
          }

          public bool isEmpty()
          {
               return length == 0;   // or head == null
          }

          public Node search(Object item)
          {
               Node nodeptr = head;
               while (nodeptr != null)
               {
                    if (nodeptr.item.ToString().Equals(item.ToString()))
                    {
                         break;
                    }
                    nodeptr = nodeptr.next;
               }
               return nodeptr;
          }

          public void delete(Object item)
          {
               Node nodeptr = head;
               Node prevptr = null;

               while (nodeptr != null)
               {
                    if (nodeptr.item.ToString().Equals(item.ToString()))
                    {
                         break;
                    }
                    prevptr = nodeptr;
                    nodeptr = nodeptr.next;
               }
               if (nodeptr != null)
               {
                    prevptr.next = nodeptr.next;
                    length--;
               }
               else
               {
                    Console.WriteLine("Can't Delete! Item not found.");
               }
          }

          public void insert(object item)
          {
               length++;

               head = new Node()
               {
                    next = head,
                    item = item
               };
          }

          public override string ToString()
          {
               Node nodeptr = head;
               string nodes = "";

               while (nodeptr != null)
               {
                    nodes += nodeptr.item + " ";
                    nodeptr = nodeptr.next;
               }
               return nodes;
          }

          public Set Union(Set B)
          {
               Set C = new Set();
               Node nodeptr = head;
               while (nodeptr != null)
               {
                    C.insert(nodeptr.item);
                    nodeptr = nodeptr.next;
               }
               nodeptr = B.head;
               while (nodeptr != null)
               {
                    C.insert(nodeptr.item);
                    nodeptr = nodeptr.next;
               }
               return C;
          }

          public Set Intersection(Set B)
          {
               Set C = new Set();
               Node nodeAptr = head;
               Node nodeBptr = B.head;
               while (nodeAptr != null)
               {
                    if (B.search(nodeAptr.item) != null)
                    {
                         C.insert(nodeAptr.item);
                    }
                    nodeAptr = nodeAptr.next;
               }

               return C;
          }

          public Set Difference(Set B)
          {
               Set C = new Set();
               Node nodeAptr = head;
               Node nodeBptr = B.head;
               while (nodeAptr != null)
               {
                    if (B.search(nodeAptr.item) == null)
                    {
                         C.insert(nodeAptr.item);
                    }
                    nodeAptr = nodeAptr.next;
               }

               return C;
          }

          public void print()
          {
               Console.WriteLine("{" + string.Join(", ", ToString().TrimEnd().Split(' ')) + "}");
          }
     }
}
---------------------------------------------------------------------------------------------------------------

Driver program using Set ADT

using System;

namespace Set_Linked_List_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               Set A = new Set();
               Set B = new Set();
               Set C = new Set();

               A.insert(1);
               A.insert(3);
               A.insert(4);

               Console.Write("Set A = ");
               A.print();

               B.insert(2);
               B.insert(3);
               B.insert(5);
               Console.Write("Set B = ");
               B.print();

               C = A.Union(B);
               Console.Write("Union of A and B = ");
               C.print();

               C = A.Intersection(B);
               Console.Write("Intersection of A and B = ");
               C.print();

               C = A.Difference(B);
               Console.Write("Difference of A and B = ");
               C.print();

               Console.WriteLine("Press any key to continue.");
               Console.ReadKey();
          }
     }
}

Queue ADT- Linked List Implementation

using System;

namespace Queue_Linked_List_Implementation
{
     class Queue
     {
        public class Node
        {
            public object item;
            public Node next;

            public Node() {
            }

            public Node(object item) {
               this.item = item;
            }
        }

        private int length;
        private Node rear, front;

        public Queue()
        {
             front = rear = null;
             length = 0;
        }

        public int Length
        {
            get { return length; }
        }

        public bool isEmpty()
        {
             return front == null;
        }

        public void enqueue(Object item)
        {
             length++;
             Node newptr;
             newptr = new Node()
             {
                  next = null,
                  item = item
             };

             if (isEmpty()) {
                  front = rear = newptr;
             }
             else
             {
                  rear.next = newptr;
                  rear = newptr;
             }
        }

        public Object dequeue()
        {
             Object item = "";
             if (!isEmpty())
             {
                  item = front.item;
                  front = front.next;
                  length--;
             }
             else
             {
                  Console.WriteLine("Error! Queue Underflow");
             }
             return item;
        }

        public Object Front()
        {
             Object item = "";
             if (!isEmpty())
             {
                  item = front.item;
             }
             else
             {
                  Console.WriteLine("Error! Queue Underflow");
             }
             return item;
        }
     }
}

------------------------------------------------------------------------------------------------------------------------------

Driver Program Using Queue Class

using System;

namespace Queue_Linked_List_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               Queue queue = new Queue();
               Object fruit;

               queue.enqueue("Apple");  // add apple at the rear of the queue
               queue.enqueue("Banana"); // add banana at the rear of the queue
               queue.enqueue("Grape");  // add grape at the rear of the queue

               Console.WriteLine(queue.Front()); // return the item at the front of the queue

               queue.enqueue("Guava");  // add gauva at the rear of the queue
               queue.enqueue("Orange"); // add orange at the rear of the queue
              
               fruit = queue.dequeue(); // return and remove the item at the front of the queue
               Console.WriteLine(fruit.ToString());
               fruit = queue.dequeue(); // return and remove the item at the front of the queue
               Console.WriteLine(fruit.ToString());
               fruit = queue.dequeue(); // return and remove the item at the front of the queue
               Console.WriteLine(fruit.ToString());


               Console.WriteLine("\nPress any key to  continue...");
               Console.ReadKey();
          }
     }
}

Queue ADT - Array Implementation

using System;

namespace Queue_Array_Implementation
{
     class Queue
     {
          private Object[] queue;
          private int rear;
          private int front;
          private int size;
          private int count;

          public Queue(int size)
          {
               this.size = size;
               queue = new Object[size];
               front = 0;
               rear = size - 1;
          }

          public bool isFull()
          {
               return count == size;
          }

          public void enQueue(Object item)
          {
               if (!isFull())
               {
                    rear = (rear + 1) % (size);
                    queue[rear] = item;
                    count++;
               }
               else
               {
                    Console.WriteLine("Queue is full");
               }
          }

          public bool isEmpty()
          {
               return (count == 0);
          }

          public Object Front()
          {
               Object item = null;
               if (!isEmpty())
               {
                    item = queue[front];
               }
               else
               {
                    Console.WriteLine("Queue is Empty");
               }
               return item;
          }

          public Object deQueue()
          {
               Object item = null;
               if (!isEmpty())
               {
                    item = queue[front];
                    front = (front + 1) % (size);
                    count--;

               }
               else
               {
                    Console.WriteLine("Queue is Empty");
               }
               return item;
          }
     }
}
---------------------------------------------------------------------------------------------------------------

Driver Program using Queue Class

using System;

namespace Queue_Array_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               Queue queue = new Queue(5);
               Object fruit;

               queue.enQueue("Apple");  // add apple at the rear of the queue
               queue.enQueue("Banana"); // add banana at the rear of the queue
               queue.enQueue("Grape");  // add grape at the rear of the queue
              
               Console.WriteLine(queue.Front()); // return the item at the front of the queue

               queue.enQueue("Guava");  // add gauva at the rear of the queue
               queue.enQueue("Orange"); // add orange at the rear of the queue
               queue.enQueue("Melon");  // can't add melon. queue is full.

               fruit = queue.deQueue(); // return and remove the item at the front of the queue
               Console.WriteLine(fruit.ToString());
               fruit = queue.deQueue(); // return and remove the item at the front of the queue
               Console.WriteLine(fruit.ToString());
               fruit = queue.deQueue(); // return and remove the item at the front of the queue
               Console.WriteLine(fruit.ToString());
              

               Console.WriteLine("\nPress any key to  continue...");
               Console.ReadKey();
          }
     }
}

Stack ADT - Using Generic List Collection of C#

using System;
using System.Collections.Generic;

namespace Generic_Stack
{
     class Program
     {
          static void Main(string[] args)
          {

               Stack<string> stack = new Stack<string>(); ;
               stack.Push("Apple");
               stack.Push("Banana");
               stack.Push("Guava");

               Console.WriteLine(string.Join(",",stack.ToArray()));
               Console.WriteLine(stack.Pop());
               Console.WriteLine(stack.Peek());
               stack.Push("Grape");
               stack.Push("Orange");
               stack.Push("Lemon");
               Console.WriteLine(string.Join(",", stack.ToArray()));
               Console.WriteLine(stack.Pop());

               Console.WriteLine("\nPress any key to continue...");
               Console.ReadKey();
          }
     }
}

Stack ADT - Linked List Implementation

using System;

namespace Stack_Linked_List_Implementation
{
     class Stack
     {
         public class Node
        {
            public object item;
            public Node next;

            public Node() {
            }

            public Node(object item) {
               this.item = item;
            }
        }

        private int length;
        private Node top;

        public Stack()
        {
             length = 0;
             top = null;
        }

        public int Length
        {
            get { return length; }
        }

        public bool isEmpty()
        {
             return top == null;
        }

        public void push(Object item)
        {
             length++;
             top = new Node()
             {
                  next = top,
                  item = item
             };
        }

        public Object pop()
        {
             Object item = "";
             if (!isEmpty())
             {
                  item = top.item;
                  top = top.next;
                  length--;
             }
             else
             {
                  Console.WriteLine("Error! Stack Underflow");
             }
             return item;
        }

        public Object peek()
        {
             Object item = "";
             if (!isEmpty())
             {
                  item = top.item;
             }
             else
             {
                  Console.WriteLine("Error! Stack Underflow");
             }
             return item;
        }

     }
}
-----------------------------------------------------------------------------------------------------------------------

Driver Program Using Stack Class


using System;

namespace Stack_Linked_List_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               Stack stack = new Stack();
               stack.push("Apple");
               stack.push("Banana");
               stack.push("Guava");           

               Console.WriteLine(stack.pop());
               Console.WriteLine(stack.peek());
               stack.push("Grape");
               stack.push("Orange");
               stack.push("Lemon");
               Console.WriteLine(stack.pop());

               Console.WriteLine("\nPress any key to continue...");
               Console.ReadKey();
          }
     }
}

List ADT - Linked List Implementation

using System;

namespace Linked_List
{
     public class List
    {

        public class Node
        {
            public object item;
            public Node next;

            public Node() {
            }

            public Node(object item) {
               this.item = item;
            }
        }

        private int length;
        private Node head, lastnode;

        public List()
        {
             length = 0;
             head = null;
        }

        public int Length
        {
            get { return length; }
        }

        public bool isEmpty()
        {
             return length == 0;
        }

        public Node search(Object item)
        {
             Node nodeptr = head;
             while (nodeptr != null)
             {
                  if (nodeptr.item.ToString().Equals(item.ToString()))
                  {
                       break;
                  }
                  nodeptr = nodeptr.next;
             }
             return nodeptr;
        }
       
       public  void remove(Object item) {
            Node nodeptr = head;
            Node prevptr = null;

            while (nodeptr != null)
             {
                  if (nodeptr.item.ToString().Equals(item.ToString()))
                  {
                       break;
                  }
                  prevptr = nodeptr;
                  nodeptr = nodeptr.next;
             }
            if (nodeptr != null)
            {
                 prevptr.next = nodeptr.next;
                 length--;
            }
            else
            {
                 Console.WriteLine("Can't Remove! Item not found.");
            }

       }

       public Object front()
       {
            if (!isEmpty())
            {
                 return head.item;
            }
            else
            {
                 Console.WriteLine("Error! The list is empty.");
                 return "";
            }
       }

       public Object tail()
       {
            if (!isEmpty())
            {
                 return lastnode.item;
            }
            else
            {
                 Console.WriteLine("Error! The list is empty.");
                 return "";
            }
       }

        public void insertAtEnd(object item)
        {
            length++;

            var node = new Node(item);
  
            if (head == null)
            {
                head = node;
            }
            else
            {
                 lastnode.next = node;
            }

            // Makes newly added node the current node
            lastnode = node;
        }

         public void insertAtFront(object item)
         {
            length++;

            head = new Node()
            {
                next = head,
                item = item
            };

            if (length == 1)
               lastnode = head;    
        }

        public override string ToString()
        {
            Node nodeptr = head;
            string nodes = "";

            while (nodeptr != null)
            {
               nodes += nodeptr.item + " ";
               nodeptr = nodeptr.next;
            }
            return nodes;
        }

        public void print()
        {
             Console.WriteLine(ToString());
        }


    }
}
-----------------------------------------------------------------------------------------------------------------
Driver Program Using List Class

using System;

namespace Linked_List
{
     class Program
     {
          static void Main(string[] args)
          {
               List list = new List();
               list.insertAtFront("Banana");
               list.insertAtFront("Apple");
               list.insertAtEnd("Guava");
               list.insertAtEnd("Orange");
               list.print();

               Console.WriteLine(list.front());
  
               Console.WriteLine(list.tail());

               list.remove("Banana");
               list.print();

               Console.WriteLine("\nPress any key to continue..");
               Console.ReadKey(); 
          }
     }
}

Stack ADT - Array Implementation

// List ADT - Array implementation of Stack ADT
// Written by   : Jun Y. Ercia
// Date created : 7 September 2016

using System;

namespace Stack_Array_Implementation
{
     class Stack
     {
          private Object[] stack;
          int top;
          int size;

          public Stack(int size)
          {
               this.size = size;
               stack = new Object[size];
               top = 0;
          }

          public int Count
          {
               get { return top; }
          }

          public bool isEmpty()
          {
               return top == 0;
          }

          public bool isFull()
          {
               return top == size;
          }

          public void push(Object item)
          {
               if (!isFull())
               {
                    stack[top++] = item;
               }
               else
               {
                    Console.Write("Error! Stack Overflow.");
               }
          }

          public Object pop()
          {
               if (!isEmpty())
               {
                     return stack[--top];
               }
               else
               {
                    Console.Write("Error! Stack Underflow.");
                    return "";
               }
          }

          public Object peek()
          {
               if (!isEmpty())
               {
                    return stack[top - 1];
               }
               else
               {
                    Console.Write("Error! Stack Underflow.");
                    return "";
               }
          }
     }
}

-------------------------------------------------------------------------------------------------------------

Driver Program Using Stack Class

using System;

namespace Sorted_List
{
     class Program
     {
          static void Main(string[] args)
          {
               List fruits = new List(5);      //create new list of fruits

               fruits.insert(0, "Banana");    //insert at position 0
               fruits.insert(0, "Apple");     //insert at position 0
               fruits.insert(1, "Grape");     //insert at position 1
               fruits.print();                //print Apple, Grape, Banana

               fruits.insertAtFront("Guava"); //insert at the front of the list
               fruits.insertAtEnd("Orange");  //insert at the end of the list
               fruits.insert(0, "Mango");      //Error! list is full
               fruits.print();                //print Guava, Apple, Grape, Banana, Orange

               Console.WriteLine(fruits.front()); //print "Guava"
               Console.WriteLine(fruits.tail()); //print "Orange"

               fruits.removeAt(0);            //remove "Guava"
               fruits.print();                //print  Apple, Grape, Banana, Orange

               fruits.removeAt("Grape");      //remove "Grape"
               fruits.print();                //print Apple, Banana, Orange

               fruits.makenull();             //make the list empty
               fruits.print();                //print "The List is Empty"
               Console.ReadKey();
          }
     }
}