C# Program to Implement a Binary Search Tree using Linked List
Posted by Superadmin on August 15 2022 07:29:05

C# Program to Implement a Binary Search Tree using Linked List

 

This C# Program Implements Binary Search Tree using Linked List.A Binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as “left” and “right”.

 

Here is source code of the C# Program to Implement Binary Search Tree using Linked List. The C# program is successfully compiled and executed with Microsoft Visual Studio. The program output is also shown below.

  1. /*
  2.  * C# Program to Implement Binary Search Tree using Linked List
  3.  */
  4. using System;
  5. using System.Collections.Generic;
  6. using System.Text;
  7. namespace TreeSort
  8. {
  9.     class Node
  10.     {
  11.         public int item;
  12.         public Node leftc;
  13.         public Node rightc;
  14.         public void display()
  15.         {
  16.             Console.Write("[");
  17.             Console.Write(item);
  18.             Console.Write("]");
  19.         }
  20.     }
  21.     class Tree
  22.     {
  23.         public Node root;
  24.         public Tree()
  25.         { 
  26.             root = null; 
  27.         }
  28.         public Node ReturnRoot()
  29.         {
  30.             return root;
  31.         }
  32.         public void Insert(int id)
  33.         {
  34.             Node newNode = new Node();
  35.             newNode.item = id;
  36.             if (root == null)
  37.                 root = newNode;
  38.             else
  39.             {
  40.                 Node current = root;
  41.                 Node parent;
  42.                 while (true)
  43.                 {
  44.                     parent = current;
  45.                     if (id < current.item)
  46.                     {
  47.                         current = current.leftc;
  48.                         if (current == null)
  49.                         {
  50.                             parent.leftc = newNode;
  51.                             return;
  52.                         }
  53.                     }
  54.                     else
  55.                     {
  56.                         current = current.rightc;
  57.                         if (current == null)
  58.                         {
  59.                             parent.rightc = newNode;
  60.                             return;
  61.                         }
  62.                     }
  63.                 }
  64.             }
  65.         }
  66.         public void Preorder(Node Root)
  67.         {
  68.             if (Root != null)
  69.             {
  70.                 Console.Write(Root.item + " ");
  71.                 Preorder(Root.leftc);
  72.                 Preorder(Root.rightc);
  73.             }
  74.         }
  75.         public void Inorder(Node Root)
  76.         {
  77.             if (Root != null)
  78.             {
  79.                 Inorder(Root.leftc);
  80.                 Console.Write(Root.item + " ");
  81.                 Inorder(Root.rightc);
  82.             }
  83.         }
  84.         public void Postorder(Node Root)
  85.         {
  86.             if (Root != null)
  87.             {
  88.                 Postorder(Root.leftc);
  89.                 Postorder(Root.rightc);
  90.                 Console.Write(Root.item + " ");
  91.             }
  92.         }
  93.     }
  94.     class Program
  95.     {
  96.         static void Main(string[] args)
  97.         {
  98.             Tree theTree = new Tree();
  99.             theTree.Insert(20);
  100.             theTree.Insert(25);
  101.             theTree.Insert(45);
  102.             theTree.Insert(15);
  103.             theTree.Insert(67);
  104.             theTree.Insert(43);
  105.             theTree.Insert(80);
  106.             theTree.Insert(33);
  107.             theTree.Insert(67);
  108.             theTree.Insert(99);
  109.             theTree.Insert(91);            
  110.             Console.WriteLine("Inorder Traversal : ");
  111.             theTree.Inorder(theTree.ReturnRoot());
  112.             Console.WriteLine(" ");
  113.             Console.WriteLine();
  114.             Console.WriteLine("Preorder Traversal : ");
  115.             theTree.Preorder(theTree.ReturnRoot());
  116.             Console.WriteLine(" ");
  117.             Console.WriteLine();
  118.             Console.WriteLine("Postorder Traversal : ");
  119.             theTree.Postorder(theTree.ReturnRoot());
  120.             Console.WriteLine(" ");
  121.             Console.ReadLine();
  122.         }
  123.     }
  124. }

Here is the output of the C# Program:

Inorder Traversal :
15  20  25  33  43  45  67  67  80  91  99
Preorder Traversal :
20  15  25  45  43  33  67  80  67  99  91
Postorder Traversal :
15  33  43  67  91  99  80  67  45  25  20