Skip to content

Instantly share code, notes, and snippets.

@DeepSky8
Last active February 25, 2016 19:47
Show Gist options
  • Save DeepSky8/147bcd0955ebe368685f to your computer and use it in GitHub Desktop.
Save DeepSky8/147bcd0955ebe368685f to your computer and use it in GitHub Desktop.
BreadthTraverse gets stuck somewhere. When I use the debug feature, Visual Studio hits an error and closes after line 173.
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 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.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; 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 static BSTNode<T> Create(T value)
{
return new BSTNode<T> { Value = value };
}
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))
{
case 0:
Count += 1;
break;
case -1:
if (Right == null)
{
Right = new BSTNode<T> { Value = newValue };
}
else
{
Right.Add(newValue);
}
break;
case 1:
if (Left == null)
{
Left = new BSTNode<T> { Value = newValue };
}
else
{
Left.Add(newValue);
}
break;
default:
break;
}
}
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)
{
//call DepthTraverse on the left child, and put the information at the beginning of the string builder
addToString.Append(Left.DepthTraverse());
addToString.Append(',');
//addToString.Insert(0, (Left.DepthTraverse()+", " + printCount(Value) + ", "), 1);
//addToString.Append(Left.DepthTraverse() + ", ");
}
addToString.Append(Value.ToString());
//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)
{
//call DepthTraverse on the right child, and put the information at the end of the string builder
addToString.Append(',');
addToString.Append(Right.DepthTraverse());
}
return addToString.ToString();
}
public string BreadthTraverse()
{
var addToString = new StringBuilder();
var childrenNodeList = new List<BSTNode<T>>();
//Put the first node in the list
childrenNodeList.Add(this);
//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();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment