Test Qu: Some Binary Search Tree Illustrations

The following was toss together for the sake of coding up example questions  (no testing code written because I would prefer to code up a red-black implementation and that’s an exercise). See one of many examples on the web.

 

Code Snippet
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Data;
  4. using System.Linq;
  5. using System.Text;
  6.  
  7. namespace ConsoleApplication1
  8. {
  9.   public class BSTNode
  10.   {
  11.     /// <summary>
  12.     /// Low Value
  13.     /// </summary>
  14.     public BSTNode LeftNode { get; set;}
  15.     /// <summary>
  16.     /// Low Value
  17.     /// </summary>
  18.     public BSTNode RightNode { get; set; }
  19.     /// <summary>
  20.     /// Value or Object
  21.     /// </summary>
  22.     public int Value { get; set; }
  23.     public object Object { get; set; }
  24.   }
  25.   public class BinarySearchTree
  26.   {
  27.     private BSTNode _Root;
  28.     public BinarySearchTree(BSTNode root)
  29.     {
  30.       _Root = root;
  31.     }
  32.     public BSTNode ExactFind(int lookupvalue)
  33.     {
  34.       if (_Root == null)
  35.       {
  36.         return null;
  37.       }
  38.       var active = _Root;
  39.       while (active != null)
  40.       {
  41.         if (active.Value == lookupvalue)
  42.         {
  43.           break;
  44.         }
  45.         if (active.Value > lookupvalue)
  46.         {
  47.           active = active.LeftNode;
  48.         }
  49.         else // Must be <, no need to test
  50.         {
  51.           active = active.RightNode;
  52.         }
  53.       }
  54.       return active;
  55.     }
  56.     public BSTNode MinValue()
  57.     {
  58.       if (_Root == null)
  59.       {
  60.         return null;
  61.       }
  62.        var active = _Root;     
  63.       while (active.LeftNode != null)
  64.       {
  65.         active = active.LeftNode;
  66.       }
  67.       return active;
  68.     }
  69.     public BSTNode MaxValue()
  70.     {
  71.       if (_Root == null)
  72.       {
  73.         return null;
  74.       }
  75.       var active = _Root;
  76.       while (active.RightNode != null)
  77.       {
  78.         active = active.RightNode;
  79.       }
  80.       return active;
  81.     }
  82.  
  83.     public BSTNode NextNode(BSTNode node)
  84.     {
  85.       if (node == null)
  86.       {
  87.         return MinValue();
  88.       }
  89.       return NextNode(node.Value);
  90.     }
  91.  
  92.     public BSTNode NextNode(int lookupvalue)
  93.     {
  94.       var path=new Stack<BSTNode>();
  95.       if (_Root == null)
  96.       {
  97.         return null;
  98.       }
  99.       var active = _Root;
  100.       while (true)
  101.       {
  102.         path.Push(active);
  103.         if (active.Value == lookupvalue)
  104.         {
  105.           break;
  106.         }
  107.         if (active.Value > lookupvalue)
  108.         {
  109.           if (active.LeftNode == null)
  110.             return active;
  111.           active = active.LeftNode;
  112.         }
  113.         else // Must be <, no need to test
  114.         {
  115.           if (active.RightNode == null)
  116.             return active;
  117.           active = active.RightNode;
  118.         }
  119.       }
  120.       var last = path.Pop();
  121.       while(last.RightNode==null && path.Count > 0)
  122.       {
  123.         last = path.Pop();
  124.       }
  125.       return last.RightNode;
  126.     }
  127.     /// <summary>
  128.     /// Find the node where a node would be inserted
  129.     /// Not a red-black (balanced tree) implementation
  130.     /// </summary>
  131.     /// <param name="lookupvalue"></param>
  132.     /// <returns></returns>
  133.     public BSTNode ParentFind(int lookupvalue)
  134.     {
  135.       if (_Root == null)
  136.       {
  137.         return null;
  138.       }
  139.       var active = _Root;
  140.       while (active != null)
  141.       {
  142.         if (active.Value == lookupvalue)
  143.         {
  144.           throw new DataException("Node with this value already exists");
  145.         }
  146.         if (active.Value > lookupvalue)
  147.         {
  148.           if(active.LeftNode==null)
  149.             return active;
  150.           active = active.LeftNode;
  151.         }
  152.         else // Must be <, no need to test
  153.         {
  154.           if (active.RightNode == null)
  155.             return active;          
  156.           active = active.RightNode;
  157.         }
  158.       }
  159.       return active;
  160.     }
  161.   }
  162. }

Comments

Popular posts from this blog

Yet once more into the breech (of altered programming logic)

Simple WP7 Mango App for Background Tasks, Toast, and Tiles: Code Explanation

How to convert SVG data to a Png Image file Using InkScape