using System;
using System.Collections.Generic;
namespace BinaryTreeLib
{
public class BinaryTree<T> : IBinaryTree<T> where T: IComparable
{
private Node<T> root; //keep track of the root
private Node<T> _root; //used later
public void Insert(T nodeValue) //used to insert Node in non-blanaced binary search tree
{
Console.WriteLine("***Adding "+nodeValue+" to tree...");
if (root == null)
{
Console.WriteLine("Tree is empty, so let's make a root...");
root = new Node<T>(nodeValue);
Console.WriteLine("Root is "+root.Value);
}
else
{
Node<T> currentNode = root;
Node<T> previousNode = root;
while (currentNode != null)
{
if (currentNode.CompareTo(nodeValue) < 0)
{//if current node is less, then goto next node (previous = current, current = previous's left child)
previousNode = currentNode;
currentNode = previousNode.LeftChild;
//LeftChild.Insert(newNode);
}
else if (currentNode.CompareTo(nodeValue) > 0)
{//if current node is greater, then goto next node (previous = current, current = previous's right child)
previousNode = currentNode;
currentNode = previousNode.RightChild;
// Console.WriteLine(nodeValue+" is greater than "+previousNode.Value+"...");
}
}
//update the node's parents
if (previousNode.CompareTo(nodeValue) < 0)
{
Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value);
previousNode.LeftChild = new Node<T>(nodeValue, previousNode);
}
else
{
Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value);
previousNode.RightChild = new Node<T>(nodeValue, previousNode);
}
}
}
public void Insert2(T nodeValue) //used to insert nodes in AVL balanced tree
{
Node<T> newNode = new Node<T>(nodeValue);
Console.WriteLine("***Adding "+nodeValue+" to tree...");
if (root == null)
{
Console.WriteLine("Tree is empty, so let's make a root...");
root = newNode;//new Node<T>(nodeValue);
Console.WriteLine("Root is "+root.Value);
}
else
{
Node<T> currentNode = root; //used to traverse through each node
Node<T> previousNode = root; //used to store the last used node
while (currentNode != null)
{
if (currentNode.CompareTo(nodeValue) < 0)
{//if current node is less, then goto next node (previous = current, current = previous's left child)
previousNode = currentNode;
currentNode = previousNode.LeftChild;
//LeftChild.Insert(newNode);
}
else if (currentNode.CompareTo(nodeValue) > 0)
{//if current node is greater, then goto next node (previous = current, current = previous's right child)
previousNode = currentNode;
currentNode = previousNode.RightChild;
}
}
//update node's parents
if (previousNode.CompareTo(nodeValue) < 0)
{
//Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value);
previousNode.LeftChild = new Node<T>(nodeValue, previousNode);
}
else
{
//Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value);
previousNode.RightChild = new Node<T>(nodeValue, previousNode);
}
ReBalance(previousNode);
}
}
private void ReBalance(Node<T> node)
{
Node<T> parent = node.Parent;
while (parent != null)
{
int balance = GetBalance(parent);
if (Math.Abs(balance) == 2)
{
BalanceAt(parent, balance);
}
parent = parent.Parent;
}
}
private void BalanceAt(Node<T> node, int balance)
{
if (balance == 2) //if balance factor is 2, then tree is unbalanced
{
int rightBalance = GetBalance(node.RightChild);
if (rightBalance == 1 || rightBalance == 0)
{
RotateLeft(node);
}
else if (rightBalance == -1)
{
Console.WriteLine("Performing Complex R-L rotation at node " +node.Value);
RotateRight(node.RightChild);
RotateLeft(node);
}
}
else if (balance == -2) //if balance factor is -2, then tree is unbalanced
{
int leftBalance = GetBalance(node.LeftChild);
if (leftBalance == -1 || leftBalance == 0)
{
RotateRight(node);
}
else if (leftBalance == 1)
{
Console.WriteLine("Performing complex L-R Rotation at node " + node.Value);
RotateLeft(node.LeftChild);
RotateRight(node);
}
}
}
private int GetHeight(Node<T> node)
{
if (node!=null)
{
return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild)));
}
else return 0;
}
private int GetBalance(Node<T> node)
{
if (node != null)
{
return (GetHeight(node.RightChild) - GetHeight(node.LeftChild));
}
else return 0;
}
private void RotateLeft(Node<T> node)
{
if (node == null)
{
return;
}
Node<T> pivot = node.RightChild;
if (pivot == null)
{
return;
}
else
{
Console.WriteLine("Performing Basic Left Rotation at node " + node.Value);
Node<T> nodesParent = node.Parent;
bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node;
bool makeTreeRoot = (_root == node);
node.RightChild = pivot.LeftChild;
pivot.LeftChild = node;
node.Parent = pivot;
pivot.Parent = nodesParent;
if (node.RightChild != null)
{
node.RightChild.Parent = node;
}
if (makeTreeRoot)
{
_root = pivot;
}
if (isLeftChild)
{
nodesParent.LeftChild = pivot;
}
else
{
if (nodesParent != null)
{
nodesParent.RightChild = pivot;
}
}
}
}
private void RotateRight(Node<T> node)
{
if (node == null)
{
return;
}
Node<T> pivot = node.LeftChild;
if (pivot==null)
{
return;
}
else
{
Console.WriteLine("Performing Basic Right Rotation at node " + node.Value);
Node<T> nodesParent = node.Parent;
bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node;
bool makeTreeRoot = (_root == node);
root.LeftChild = pivot.RightChild;
pivot.RightChild = node;
node.Parent = pivot;
pivot.Parent = nodesParent;
if (node.LeftChild != null)
{
node.LeftChild.Parent = node;
}
if (makeTreeRoot)
{
_root = pivot;
}
if (isLeftChild)
{
nodesParent.LeftChild = pivot;
}
else
{
if (nodesParent != null)
{
nodesParent.RightChild = pivot;
}
}
}
}
public void Delete(T nodeValue)
{
}
/// <summary>
/// START PREORDER
/// </summary>
public void Preorder()
{
PreorderTraverse(root);
}
private void PreorderTraverse(Node<T> node)
{
if (node == null)
return;
Console.WriteLine(node.Value);
PreorderTraverse(node.LeftChild);
PreorderTraverse(node.RightChild);
}
/// <summary>
/// START INORDER
/// </summary>
public void Inorder()
{
InorderTraversal(root);
}
private void InorderTraversal(Node<T> node)
{
if (node == null)
return;
InorderTraversal(node.LeftChild);
Console.WriteLine(node.Value);
InorderTraversal(node.RightChild);
}
/// <summary>
/// START POSTORDER
/// </summary>
public void Postorder()
{
PostorderTraversal(root);
}
private void PostorderTraversal(Node<T> node)
{
if (node == null)
return;
PostorderTraversal(node.LeftChild);
PostorderTraversal(node.RightChild);
Console.WriteLine(node.Value);
}
public void MakeNull()
{ //just deleting the root for now...eventually will delete from leaf nodes up
if (root != null)
{
//PostOrderDelete(root);
root = null;
}
}
private void PostOrderACE(Node<T> node, int currentLevel, List<int> levelCounts)
{
if (node.LeftChild != null)
{
PostOrderACE(node.LeftChild, currentLevel + 1, levelCounts);
}
if (node.RightChild != null)
{
PostOrderACE(node.RightChild, currentLevel +1, levelCounts);
}
levelCounts.Add(currentLevel);
}
public float ACE
{
get
{
if (root != null)
{
List<int> levelCounts = new List<int>();
PostOrderACE(root, 1, levelCounts);
float total = 0.0F;
float nodeCount = (float)levelCounts.Count;
foreach (int i in levelCounts)
{
total += (float)i;
}
return total / nodeCount;
}
else return 0.0F;
}
}
}
}
Offline 
Marked 
