SHARE
TWEET

Untitled

a guest Jun 25th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. /// <summary>
  4. /// My implementation of BST. It has two classes. Node & BSTree.
  5. /// </summary>
  6. namespace BinarySearchTree
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             //Random rnd = new Random();
  13.             //BSTree bst = new BSTree(new Node(rnd.Next(0,100)));
  14.             //bst.Insert(new Node(rnd.Next(0, 100)));
  15.  
  16.             BSTree bst = new BSTree(new Node(20));
  17.             bst.Insert(new Node(15));
  18.             bst.Insert(new Node(25));
  19.             bst.Insert(new Node(18));
  20.             bst.Insert(new Node(10));
  21.             bst.Insert(new Node(19));
  22.             bst.Insert(new Node(16));
  23.             bst.Insert(new Node(17));
  24.             /*
  25.                   20
  26.                  /  
  27.                 15  25
  28.                /  
  29.               10  18
  30.                  /  
  31.                 16  19
  32.                  
  33.                   17
  34.             */
  35.  
  36.             bst.PrintTraversedTree(BSTree.TreeTraversalForm.BreathFirstSearch);
  37.  
  38.             Console.WriteLine("Searching for node...");
  39.             Node devetnajst = bst.BinarySearch(19);
  40.             if (devetnajst != null)
  41.                 Console.WriteLine($"Node value: {devetnajst.value}");
  42.             else
  43.                 Console.WriteLine("Node not found!");
  44.  
  45.             Console.WriteLine("Searching for node...");
  46.             Node stNiVDrevesu = bst.BinarySearch(23);
  47.             if(stNiVDrevesu!=null)
  48.                 Console.WriteLine($"Node value: {stNiVDrevesu.value}");
  49.             else
  50.                 Console.WriteLine("Node not found!");
  51.         }
  52.     }
  53.  
  54.     /// <summary>
  55.     /// class Node represents nodes of the binary three.
  56.     /// </summary>
  57.     class Node
  58.     {
  59.         public Node(int value)
  60.         {
  61.             this.value = value;
  62.         }
  63.         public int value { get; set; }
  64.         public Node left { get; set; } = null;
  65.         public Node right { get; set; } = null;
  66.  
  67.     }
  68.  
  69.     /// <summary>
  70.     /// class BSTree represent Binary Search Tree.
  71.     /// </summary>
  72.     class BSTree
  73.     {
  74.         Node _root=null; // tree root
  75.         int[] _treeTraversal; //three traversal -- dynamic programing
  76.         int _nodeCounter=0; //nr of nodes - used to declare _treeTraversal size
  77.         int _treeTraversalIndex = 0; //used to position node in array _treeTraversal
  78.         int _currentTraverseForm = -1; //if -1 -> no valid traverse of tree
  79.  
  80.         public BSTree(Node root) {
  81.             _root = root;
  82.             _nodeCounter++;
  83.         }
  84.  
  85.         /// <summary>
  86.         /// Insert Node into tree
  87.         /// </summary>
  88.         /// <param name="node">Node to be inserted.</param>
  89.         /// <param name="root"></param>
  90.         public void Insert(Node node, Node root=null)
  91.         {
  92.             if (root == null)
  93.             {
  94.                 root = _root; // if no root is specified use tree root
  95.             }
  96.  
  97.             if (node.value == root.value)
  98.             {
  99.                 Console.WriteLine($"Unable to insert! Value {node.value} allready exist!");
  100.                 return;
  101.             }
  102.  
  103.             if (node.value<root.value)
  104.             {
  105.                 if (root.left == null)
  106.                 {
  107.                     root.left = node;
  108.                     _nodeCounter++;
  109.                     _currentTraverseForm = -1; // when you insert new node current stored traverse is not valid anymore
  110.                 }
  111.                 else
  112.                 {
  113.                     Insert(node, root.left);
  114.                 }
  115.             }
  116.             else
  117.             {
  118.                 if (root.right == null)
  119.                 {
  120.                     root.right = node;
  121.                     _nodeCounter++;
  122.                     _currentTraverseForm = -1;
  123.                 }
  124.                 else
  125.                 {
  126.                     Insert(node, root.right);
  127.                 }
  128.             }
  129.  
  130.         }
  131.  
  132.         /// <summary>
  133.         /// Binary Search throught the tree for value
  134.         /// </summary>
  135.         /// <param name="value">searched value</param>
  136.         /// <param name="root"></param>
  137.         /// <returns>Node if found, otherwise returns null</returns>
  138.         public Node BinarySearch(int value, Node root = null)
  139.         {
  140.             if (root == null)
  141.             {
  142.                 root = _root;
  143.             }
  144.  
  145.             if (value == root.value)
  146.             {
  147.                 return root;
  148.             }
  149.  
  150.             if (value < root.value)
  151.             {
  152.                 if (root.left != null)
  153.                 {
  154.                     return BinarySearch(value, root.left);
  155.                 }
  156.                 else
  157.                 {
  158.                     return null;
  159.                 }
  160.             }
  161.             else
  162.             {
  163.                 if (root.right != null)
  164.                 {
  165.                     return BinarySearch(value, root.right);
  166.                 }
  167.                 else
  168.                 {
  169.                     return null;
  170.                 }
  171.             }
  172.  
  173.  
  174.         }
  175.  
  176.         /// <summary>
  177.         /// enum specifaing posible tree traversal forms
  178.         /// DFS - Depth-first search
  179.         /// </summary>
  180.         public enum TreeTraversalForm
  181.         {
  182.             DFSpreorder,
  183.             DFSinorder,
  184.             DFSoutorder,
  185.             DFSpostorder,
  186.             BreathFirstSearch
  187.         };
  188.  
  189.         /// <summary>
  190.         /// Maps the tree traversal form with appropriate method
  191.         /// </summary>
  192.         /// <param name="traversalForm"></param>
  193.         /// <returns></returns>
  194.         public int[] TraverseTree(TreeTraversalForm traversalForm)
  195.         {
  196.  
  197.             //if tree is already traversed -> dont do it again
  198.             if ((int)traversalForm != _currentTraverseForm)
  199.             {
  200.                 switch (traversalForm)
  201.                 {
  202.                     case TreeTraversalForm.DFSinorder:
  203.                         this.Inorder();
  204.                         break;
  205.                     case TreeTraversalForm.DFSoutorder:
  206.                         this.Outorder();
  207.                         break;
  208.                     case TreeTraversalForm.DFSpostorder:
  209.                         this.Postorder();
  210.                         break;
  211.                     case TreeTraversalForm.DFSpreorder:
  212.                         this.Preorder();
  213.                         break;
  214.                     case TreeTraversalForm.BreathFirstSearch:
  215.                         this.BreathFirstSearch();
  216.                         break;
  217.                     default:
  218.                         Console.WriteLine("Unknown form!");
  219.                         break;
  220.                 }
  221.             }
  222.  
  223.             return _treeTraversal;
  224.         }
  225.  
  226.         /// <summary>
  227.         /// Prints traversed tree to Console
  228.         /// </summary>
  229.         /// <param name="traversalForm"></param>
  230.         public void PrintTraversedTree(TreeTraversalForm traversalForm)
  231.         {
  232.  
  233.             //if tree is already traversed -> dont do it again
  234.             if ((int)traversalForm != _currentTraverseForm)
  235.             {
  236.                 this.TraverseTree(traversalForm);
  237.             }
  238.  
  239.             Console.Write(traversalForm.ToString() + ": ");
  240.             foreach (int val in _treeTraversal)
  241.             {
  242.                 Console.Write($"{val} ");
  243.             }
  244.             Console.WriteLine();
  245.         }
  246.  
  247.         /// <summary>
  248.         /// Creates DFS - Pre-order traverse and stors it in _treeTraversal
  249.         /// </summary>
  250.         /// <param name="root"></param>
  251.         void Preorder(Node root = null)
  252.         {
  253.             if (root == null)
  254.             {
  255.                 root = _root;
  256.                 _treeTraversal = new int[_nodeCounter];
  257.                 _treeTraversalIndex = 0;
  258.                 _currentTraverseForm = (int)TreeTraversalForm.DFSpreorder;
  259.             }
  260.  
  261.             _treeTraversal[_treeTraversalIndex] = root.value;
  262.             _treeTraversalIndex++;
  263.  
  264.             if (root.left != null)
  265.                 Preorder(root.left);
  266.  
  267.             if (root.right != null)
  268.                 Preorder(root.right);
  269.         }
  270.  
  271.         /// <summary>
  272.         /// Creates DFS - In-order traverse and stors it in _treeTraversal
  273.         /// </summary>
  274.         /// <param name="root"></param>
  275.         void Inorder(Node root = null)
  276.         {
  277.             if (root == null)
  278.             {
  279.                 root = _root;
  280.                 _treeTraversal = new int[_nodeCounter];
  281.                 _treeTraversalIndex = 0;
  282.                 _currentTraverseForm = (int)TreeTraversalForm.DFSinorder;
  283.             }
  284.  
  285.  
  286.             if (root.left != null)
  287.                 Inorder(root.left);
  288.  
  289.             _treeTraversal[_treeTraversalIndex] = root.value;
  290.             _treeTraversalIndex++;
  291.  
  292.             if (root.right != null)
  293.                 Inorder(root.right);
  294.         }
  295.  
  296.         /// <summary>
  297.         /// Creates DFS - Post-order traverse and stors it in _treeTraversal
  298.         /// </summary>
  299.         /// <param name="root"></param>
  300.         void Postorder(Node root = null)
  301.         {
  302.             if (root == null)
  303.             {
  304.                 root = _root;
  305.                 _treeTraversal = new int[_nodeCounter];
  306.                 _treeTraversalIndex = 0;
  307.                 _currentTraverseForm = (int)TreeTraversalForm.DFSpostorder;
  308.             }
  309.  
  310.  
  311.             if (root.left != null)
  312.                 Postorder(root.left);
  313.  
  314.             if (root.right != null)
  315.                 Postorder(root.right);
  316.  
  317.             _treeTraversal[_treeTraversalIndex] = root.value;
  318.             _treeTraversalIndex++;
  319.         }
  320.  
  321.         /// <summary>
  322.         /// Creates DFS - Out-order traverse and stors it in _treeTraversal
  323.         /// </summary>
  324.         /// <param name="root"></param>
  325.         void Outorder(Node root = null)
  326.         {
  327.             if (root == null)
  328.             {
  329.                 root = _root;
  330.                 _treeTraversal = new int[_nodeCounter];
  331.                 _treeTraversalIndex = 0;
  332.                 _currentTraverseForm = (int)TreeTraversalForm.DFSoutorder;
  333.             }
  334.  
  335.  
  336.             if (root.right != null)
  337.                 Outorder(root.right);
  338.  
  339.             _treeTraversal[_treeTraversalIndex] = root.value;
  340.             _treeTraversalIndex++;
  341.  
  342.             if (root.left != null)
  343.                 Outorder(root.left);
  344.  
  345.         }
  346.  
  347.         /// <summary>
  348.         /// Creates BFS - BreathFirstSearch traverse and stors it in _treeTraversal
  349.         /// </summary>
  350.         /// <param name="root"></param>
  351.         void BreathFirstSearch(Node root = null)
  352.         {
  353.             if (root == null)
  354.             {
  355.                 root = _root;
  356.                 _treeTraversal = new int[_nodeCounter];
  357.                 _treeTraversalIndex = 0;
  358.                 _currentTraverseForm = (int)TreeTraversalForm.BreathFirstSearch;
  359.  
  360.                 _treeTraversal[_treeTraversalIndex] = root.value;
  361.                 _treeTraversalIndex++;
  362.             }
  363.  
  364.             if (root.left != null)
  365.             {
  366.                 _treeTraversal[_treeTraversalIndex] = root.left.value;
  367.                 _treeTraversalIndex++;
  368.             }
  369.  
  370.             if (root.right != null)
  371.             {
  372.                 _treeTraversal[_treeTraversalIndex] = root.right.value;
  373.                 _treeTraversalIndex++;
  374.             }
  375.  
  376.             if (root.left != null)
  377.                 BreathFirstSearch(root.left);
  378.             if (root.right != null)
  379.                 BreathFirstSearch(root.right);
  380.         }
  381.     }
  382. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top