Last active
February 25, 2016 19:47
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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