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();
          }
     }
}