Last active
March 22, 2021 10:31
-
-
Save NovemberDev/887f7cc1f33ec96c50878bbedd78770a to your computer and use it in GitHub Desktop.
Generic Binary Tree implementation I built
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; | |
// Author: NovemberDev | |
public class Program | |
{ | |
/// | |
/// TreeNode baseclass | |
/// | |
public class TreeNode<T> | |
{ | |
/// This TreeNode's Value | |
public T Value; | |
/// This TreeNode's ParentNode | |
public TreeNode<T> Parent; | |
/// This TreeNode's ChildNodes | |
public List<TreeNode<T>> Children = new List<TreeNode<T>>(); | |
/// Creates a new TreeNode with an initial value and an amount of ChildNodes to parent | |
/// during construction | |
public TreeNode(T initialValue, params TreeNode<T>[] childNodes) | |
{ | |
Value = initialValue; | |
foreach(TreeNode<T> childNode in childNodes) | |
AddChild(childNode); | |
// Note: the params can be removed in favor of a left and right ChildNode approach but | |
// I like to leave it as it is, since you can then customize it to hold as many children | |
// as you need there to be, make sure to remove the exception in AddChild as well | |
} | |
/// Recursively returns the leaf TreeNode by taking in a comparison function, | |
/// which compares all children | |
public TreeNode<T> Traverse(Func<TreeNode<T>, TreeNode<T>, bool> comparisonFunction) | |
{ | |
if(Children.Count < 1) | |
return this; | |
TreeNode<T> currentNode = null; | |
foreach(TreeNode<T> childNode in Children) | |
{ | |
if(currentNode == null) | |
{ | |
currentNode = childNode; | |
continue; | |
} | |
if(comparisonFunction.Invoke(currentNode, childNode)) | |
currentNode = childNode; | |
} | |
Console.WriteLine("Traverse -> " + currentNode.Value); | |
return currentNode.Traverse(comparisonFunction); | |
} | |
/// Recursively returns the Root-TreeNode | |
public TreeNode<T> TraverseToRoot() | |
{ | |
if(Parent != null) | |
return Parent.TraverseToRoot(); | |
return this; | |
} | |
/// Adds a child and sets it's Parent property to the current TreeNode | |
/// Throws an exception if more than 2 children exist | |
public void AddChild(TreeNode<T> childNode) | |
{ | |
childNode.Parent = this; | |
if(Children.Count > 1) | |
throw new ArgumentOutOfRangeException("TreeNode cannot hold more than 2 ChildNodes"); | |
Children.Add(childNode); | |
} | |
// Check if TreeNode is a child node | |
public bool IsLeaf() | |
{ | |
return Children.Count == 0; | |
} | |
/// Check if TreeNode is a root node | |
public bool IsRoot() | |
{ | |
return Parent == null; | |
} | |
} | |
public static void Main() | |
{ | |
TreeNode<int> rootNode = new TreeNode<int>( | |
100, | |
new TreeNode<int>( | |
10, | |
new TreeNode<int>( | |
5, | |
new TreeNode<int>(2), | |
new TreeNode<int>(3) | |
), | |
new TreeNode<int>( | |
2, | |
new TreeNode<int>(2), | |
new TreeNode<int>(3) | |
) | |
), | |
new TreeNode<int>( | |
11, | |
new TreeNode<int>( | |
1, | |
new TreeNode<int>(5), | |
new TreeNode<int>(6) | |
), | |
new TreeNode<int>( | |
3, | |
new TreeNode<int>(7), | |
new TreeNode<int>(8) | |
) | |
) | |
); | |
TreeNode<int> leafNode = rootNode.Traverse((t1, t2) => t1.Value < t2.Value); | |
Console.WriteLine("Result = " + leafNode.Value); | |
Console.WriteLine("Root = " + leafNode.TraverseToRoot().Value); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment