Skip to content

Instantly share code, notes, and snippets.

@DeepSky8

DeepSky8/BinarySearchTree.cs

Last active February 25, 2016 19:47
Download ZIP

Revisions

  1. DeepSky8 revised this gist Feb 25, 2016. 1 changed file with 120 additions and 74 deletions.
    194 changes: 120 additions & 74 deletions BinarySearchTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -10,131 +10,177 @@ class Program
    {
    static void Main(string[] args)
    {
    var newBST = new BSTNode<int>();
    var newBST = BSTNode<int>.Create(12);
    //newBST.Add(12);
    newBST.Add(12);
    newBST.Add(6);
    newBST.Add(18);
    newBST.Add(3);
    newBST.Add(14);
    newBST.Add(9);
    newBST.Add(17);
    newBST.Add(19);
    newBST.Add(0);
    newBST.Add(14);

    //var secondBST = BSTNode<string>.Create("purple");

    Console.WriteLine(newBST.DepthTraverse());

    Console.WriteLine(newBST.TraverseBST());
    Console.WriteLine(newBST.BreadthTraverse());
    }
    }

    public class God
    {
    private static God instance;

    public static God Create()
    {
    if (instance == null)
    {
    instance = new God();
    }
    return instance;
    }

    private God()
    {
    }

    public void PrayTo()
    {
    }


    }


    public class BSTNode<T> where T : IComparable<T>
    {
    public T Value { get; set; }
    public T Value { get; protected set; }
    public BSTNode<T> Right { get; protected set; }
    public BSTNode<T> Left { get; protected set; }
    public bool Unprinted { get; protected set; } = true;
    public int Count { get; protected set; } = 0;

    public void Add(T newValue)
    public static BSTNode<T> Create(T value)
    {
    return new BSTNode<T> { Value = value };
    }

    var newNode = new BSTNode<T>();


    //If this node does not hold a value, set it to the value currently being added. If the node equals 0, increment the Count at this node.
    if (Value == null || Value.Equals(0))
    public void Add(T newValue)
    {
    //If current node does not hold a value, set it to the value currently being added. If the node equals 0, increment the Count at this node.
    switch (Value.CompareTo(newValue))
    {
    if (Value.Equals(newValue))
    {
    case 0:
    Count += 1;
    }
    Value = newValue;
    }
    //If there is a value in the node, or the base node value is not 0, compare the new value to the current node value.
    //Either increment the count by 1, or determine if child node [left or right] exists.
    //Call Add with the newValue on the (possibly newly created) [left or right] node.
    else
    {
    switch (Value.CompareTo(newValue))
    {
    case 0:
    Count += 1;
    break;
    case -1:
    if (Left == null)
    {
    Left = newNode;
    }
    Left.Add(newValue);
    break;
    case 1:
    if (Right == null)
    {
    Right = newNode;
    }
    break;
    case -1:
    if (Right == null)
    {
    Right = new BSTNode<T> { Value = newValue };
    }
    else
    {
    Right.Add(newValue);
    break;
    default:
    break;
    }
    }

    break;
    case 1:
    if (Left == null)
    {
    Left = new BSTNode<T> { Value = newValue };
    }
    else
    {
    Left.Add(newValue);
    }
    break;
    default:
    break;
    }
    }

    public string TraverseBST()
    public string DepthTraverse()
    {
    var addToString = new StringBuilder();

    //Check if left node exists to determine if on leaf or node
    //If a left child exists, confirm that it has not been printed
    if (Left != null && Left.Unprinted)
    {
    //call TraverseBST on the left child, and put the information at the beginning of the string builder
    addToString.Insert(0, (Left.TraverseBST()+","), 1);
    }
    else
    if (Left != null)
    {
    if (Unprinted)
    {
    var localStringArray = new T[Count];
    //call DepthTraverse on the left child, and put the information at the beginning of the string builder
    addToString.Append(Left.DepthTraverse());
    addToString.Append(',');

    for (int i = 0; i < Count; i++)
    {
    localStringArray[i] = Value;
    }
    //addToString.Insert(0, (Left.DepthTraverse()+", " + printCount(Value) + ", "), 1);
    //addToString.Append(Left.DepthTraverse() + ", ");
    }

    addToString.Append(string.Join(",", localStringArray));
    addToString.Append(Value.ToString());

    Unprinted = false;
    }

    }

    //Check if right node exists to determine if on leaf or node
    //If a right child exists, confirm that it has not been printed
    if (Right != null && Right.Unprinted)
    if (Right != null)
    {
    //call TraverseBST on the right child, and put the information at the end of the string builder
    addToString.Append(Right.TraverseBST());
    Right.Unprinted = false;
    //call DepthTraverse on the right child, and put the information at the end of the string builder
    addToString.Append(',');
    addToString.Append(Right.DepthTraverse());
    }
    //else
    //{
    // if (Unprinted)
    // {
    // var localStringArray = new T[Count];

    // for (int i = 0; i < Count; i++)
    // {
    // localStringArray[i] = Value;
    // }
    return addToString.ToString();
    }

    // addToString.Append(string.Join(",", localStringArray));
    public string BreadthTraverse()
    {
    var addToString = new StringBuilder();
    var childrenNodeList = new List<BSTNode<T>>();

    //Put the first node in the list
    childrenNodeList.Add(this);

    // Unprinted = false;
    // }
    //While there are still elements in the list (the tree still exists) continue to iterate over the nodes being fed into childrenNodeList
    while (childrenNodeList != null)
    {
    //Use the current number of nodes in childrenNodeList to determine later operations
    var listCount = childrenNodeList.Count;

    //For each node, append its value to addToString. Then add (left then right) any children of the current node. Iterates through each previously-added node from a While cycle.
    for (int i = 0; i < listCount; i++)
    {
    addToString.Append((childrenNodeList.ElementAt(i)).Value.ToString());
    addToString.Append(", ");

    //}
    var leftChild = childrenNodeList.ElementAt(i).Left;
    var rightChild = childrenNodeList.ElementAt(i).Right;

    if (leftChild != null)
    {
    childrenNodeList.Add(leftChild);
    }

    if (rightChild != null)
    {
    childrenNodeList.Add(rightChild);
    }
    }

    childrenNodeList.RemoveRange(0, listCount);
    }
    return addToString.ToString();
    }







    }


  2. DeepSky8 revised this gist Feb 18, 2016. 1 changed file with 43 additions and 19 deletions.
    62 changes: 43 additions & 19 deletions BinarySearchTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -19,7 +19,7 @@ static void Main(string[] args)
    newBST.Add(9);
    newBST.Add(17);

    newBST.PrintString();
    Console.WriteLine(newBST.TraverseBST());
    }
    }

    @@ -28,7 +28,7 @@ public class BSTNode<T> where T : IComparable<T>
    public T Value { get; set; }
    public BSTNode<T> Right { get; protected set; }
    public BSTNode<T> Left { get; protected set; }
    public bool Printed { get; protected set; }
    public bool Unprinted { get; protected set; } = true;
    public int Count { get; protected set; } = 0;

    public void Add(T newValue)
    @@ -75,39 +75,63 @@ public void Add(T newValue)
    }
    }

    public string PrintString()
    public string TraverseBST()
    {
    var toPrint = new StringBuilder();
    if (Left != null)
    var addToString = new StringBuilder();

    //Check if left node exists to determine if on leaf or node
    //If a left child exists, confirm that it has not been printed
    if (Left != null && Left.Unprinted)
    {
    Left.PrintString();
    //call TraverseBST on the left child, and put the information at the beginning of the string builder
    addToString.Insert(0, (Left.TraverseBST()+","), 1);
    }
    else
    {
    for (int i = Count; i > 0; i--)
    {
    toPrint.Append(Value + ", ");
    }
    if (Right != null)
    if (Unprinted)
    {
    Right.PrintString();
    }
    else
    {
    for (int i = Count; i > 0; i--)
    var localStringArray = new T[Count];

    for (int i = 0; i < Count; i++)
    {
    toPrint.Append(Value + ", ");
    localStringArray[i] = Value;
    }

    addToString.Append(string.Join(",", localStringArray));

    Unprinted = false;
    }

    }

    //Check if right node exists to determine if on leaf or node
    //If a right child exists, confirm that it has not been printed
    if (Right != null && Right.Unprinted)
    {
    //call TraverseBST on the right child, and put the information at the end of the string builder
    addToString.Append(Right.TraverseBST());
    Right.Unprinted = false;
    }
    //else
    //{
    // if (Unprinted)
    // {
    // var localStringArray = new T[Count];

    // for (int i = 0; i < Count; i++)
    // {
    // localStringArray[i] = Value;
    // }

    return toPrint.ToString();
    }
    // addToString.Append(string.Join(",", localStringArray));

    // Unprinted = false;
    // }

    //}

    return addToString.ToString();
    }



  3. DeepSky8 revised this gist Feb 11, 2016. 1 changed file with 4 additions and 0 deletions.
    4 changes: 4 additions & 0 deletions BinarySearchTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -90,6 +90,10 @@ public string PrintString()
    }
    if (Right != null)
    {
    Right.PrintString();
    }
    else
    {
    for (int i = Count; i > 0; i--)
    {
    toPrint.Append(Value + ", ");
  4. DeepSky8 revised this gist Feb 11, 2016. 1 changed file with 90 additions and 18 deletions.
    108 changes: 90 additions & 18 deletions BinarySearchTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -10,46 +10,118 @@ class Program
    {
    static void Main(string[] args)
    {
    var newBST = new BSTNode<string>();
    newBST.Add("purple");
    newBST.Add("green");
    newBST.Add("blue");

    var newBST = new BSTNode<int>();
    newBST.Add(12);
    newBST.Add(6);
    newBST.Add(18);
    newBST.Add(3);
    newBST.Add(14);
    newBST.Add(9);
    newBST.Add(17);

    newBST.PrintString();
    }
    }

    public class BSTNode<T> where T : IComparable<T>
    {
    public T Value { get; set; }
    public BSTNode<T> Right { get; set; }
    public BSTNode<T> Left { get; set; }
    public bool Printed { get; set; }
    public int Count { get; set; } = 1;
    public BSTNode<T> Right { get; protected set; }
    public BSTNode<T> Left { get; protected set; }
    public bool Printed { get; protected set; }
    public int Count { get; protected set; } = 0;

    public void Add(T newValue)
    {
    //If this node does not hold a value, set it to the value currently being added
    if (Value == null)

    var newNode = new BSTNode<T>();

    //If this node does not hold a value, set it to the value currently being added. If the node equals 0, increment the Count at this node.
    if (Value == null || Value.Equals(0))
    {
    if (Value.Equals(newValue))
    {
    Count += 1;
    }
    Value = newValue;
    }
    //If there is a value in the node, compare the new value to the current node value. Either increment the count by 1, or create a child node (left or right) based on how the new value compares to the current node value.
    //If there is a value in the node, or the base node value is not 0, compare the new value to the current node value.
    //Either increment the count by 1, or determine if child node [left or right] exists.
    //Call Add with the newValue on the (possibly newly created) [left or right] node.
    else
    {
    switch (Value.CompareTo(newValue))
    {
    case 0:
    Count += 1;
    break;
    case -1:
    if (Left == null)
    {
    Left = newNode;
    }
    Left.Add(newValue);
    break;
    case 1:
    if (Right == null)
    {
    Right = newNode;
    }
    Right.Add(newValue);
    break;
    default:
    break;
    }
    }
    }

    public string PrintString()
    {
    var toPrint = new StringBuilder();
    if (Left != null)
    {
    Left.PrintString();
    }
    else
    {
    //This var will hold one of three options, as defined by IComparable: less than zero, zero, or greater than zero
    var compared = Value.CompareTo(newValue);
    if (compared == 0) { Count += 1; }
    if (compared == -1) { Left = new BSTNode<T>(); Left.Add(newValue); }
    if (compared == +1) { Right = new BSTNode<T>(); Right.Add(newValue); }
    for (int i = Count; i > 0; i--)
    {
    toPrint.Append(Value + ", ");
    }
    if (Right != null)
    {
    for (int i = Count; i > 0; i--)
    {
    toPrint.Append(Value + ", ");
    }
    }
    }



    return toPrint.ToString();
    }






    }
















    }
    }
  5. DeepSky8 revised this gist Feb 10, 2016. 1 changed file with 20 additions and 55 deletions.
    75 changes: 20 additions & 55 deletions BinarySearchTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -10,81 +10,46 @@ class Program
    {
    static void Main(string[] args)
    {
    var newList = new BinarySearchTree<string>();
    newList.Add("purple");

    Console.WriteLine(newList.ToString()
    );
    var newBST = new BSTNode<string>();
    newBST.Add("purple");
    newBST.Add("green");
    newBST.Add("blue");


    }
    }

    public class Node<T> where T : IComparable<T>
    public class BSTNode<T> where T : IComparable<T>
    {
    public T Value { get; set; }
    public Node<T> Right { get; set; }
    public Node<T> Left { get; set; }
    public BSTNode<T> Right { get; set; }
    public BSTNode<T> Left { get; set; }
    public bool Printed { get; set; }
    public int Count { get; set; }
    }

    public class BinarySearchTree<T> where T : IComparable<T>
    {
    private Node<T> Root { get; set; }
    public Node<T> Current { get; set; }
    public int Count { get; set; } = 1;

    public void Add(T value)
    public void Add(T newValue)
    {
    var pointer = Current;

    //Need some way to use Add recursively. Must start at root, but must also be able to interact with a mutable node selector

    //If this is a new tree, set the pointer at Root
    if (Root == null)
    {
    pointer = Root;
    }

    //If the pointer is not on a null node, compare the value being added to the value currently present
    if (pointer != null)
    //If this node does not hold a value, set it to the value currently being added
    if (Value == null)
    {
    //This var will hold one of three options, as defined by IComparable: less than zero, zero, or greater than zero
    var compared = Compared(value, pointer);
    if (compared == 0) { Current.Count += 1; }
    if (compared == -1) { Current = pointer.Left; }
    if (compared == +1) { Current = pointer.Right; }

    Value = newValue;
    }
    //If the pointer is on a null node, add data to that node. This should allow Add to be called recursively.
    //If there is a value in the node, compare the new value to the current node value. Either increment the count by 1, or create a child node (left or right) based on how the new value compares to the current node value.
    else
    {
    pointer.Value = value;
    //This var will hold one of three options, as defined by IComparable: less than zero, zero, or greater than zero
    var compared = Value.CompareTo(newValue);
    if (compared == 0) { Count += 1; }
    if (compared == -1) { Left = new BSTNode<T>(); Left.Add(newValue); }
    if (compared == +1) { Right = new BSTNode<T>(); Right.Add(newValue); }
    }
    }

    public int Compared(T value, Node<T> node)
    {
    return value.CompareTo(node.Value);
    }





    }















    }
    }
  6. DeepSky8 revised this gist Feb 10, 2016. 2 changed files with 90 additions and 69 deletions.
    90 changes: 90 additions & 0 deletions BinarySearchTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,90 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace BinaryTree
    {
    class Program
    {
    static void Main(string[] args)
    {
    var newList = new BinarySearchTree<string>();
    newList.Add("purple");

    Console.WriteLine(newList.ToString()
    );

    }
    }

    public class Node<T> where T : IComparable<T>
    {
    public T Value { get; set; }
    public Node<T> Right { get; set; }
    public Node<T> Left { get; set; }
    public bool Printed { get; set; }
    public int Count { get; set; }
    }

    public class BinarySearchTree<T> where T : IComparable<T>
    {
    private Node<T> Root { get; set; }
    public Node<T> Current { get; set; }

    public void Add(T value)
    {
    var pointer = Current;

    //Need some way to use Add recursively. Must start at root, but must also be able to interact with a mutable node selector

    //If this is a new tree, set the pointer at Root
    if (Root == null)
    {
    pointer = Root;
    }

    //If the pointer is not on a null node, compare the value being added to the value currently present
    if (pointer != null)
    {
    //This var will hold one of three options, as defined by IComparable: less than zero, zero, or greater than zero
    var compared = Compared(value, pointer);
    if (compared == 0) { Current.Count += 1; }
    if (compared == -1) { Current = pointer.Left; }
    if (compared == +1) { Current = pointer.Right; }

    }
    //If the pointer is on a null node, add data to that node. This should allow Add to be called recursively.
    else
    {
    pointer.Value = value;
    }
    }

    public int Compared(T value, Node<T> node)
    {
    return value.CompareTo(node.Value);
    }





    }















    }
    69 changes: 0 additions & 69 deletions BinaryTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,69 +0,0 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

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

    public class Node<T>
    {
    public T Value { get; set; }
    public Node<T> Right { get; set; }
    public Node<T> Left { get; set; }
    public bool Printed { get; set; }
    public int Count { get; set; }
    }

    public class BinaryTree<T>
    {
    private Node<T> root { get; set; }
    private Node<T> pointer { get; set; }

    public void Add(T value)
    {
    if (root == null)
    {
    root.Value = value;
    pointer = root;
    }
    else
    {
    if (root.Value == value)
    {

    }
    }

    }







    }















    }
  7. DeepSky8 created this gist Feb 9, 2016.
    69 changes: 69 additions & 0 deletions BinaryTree.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,69 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

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

    public class Node<T>
    {
    public T Value { get; set; }
    public Node<T> Right { get; set; }
    public Node<T> Left { get; set; }
    public bool Printed { get; set; }
    public int Count { get; set; }
    }

    public class BinaryTree<T>
    {
    private Node<T> root { get; set; }
    private Node<T> pointer { get; set; }

    public void Add(T value)
    {
    if (root == null)
    {
    root.Value = value;
    pointer = root;
    }
    else
    {
    if (root.Value == value)
    {

    }
    }

    }







    }















    }