Hi all.
I've been working on a Binary Search Tree as a beginner and have the majority of functions working, however in the program I need to give the option to choose how to traverse the contents and then display them in that order. I've got the traversal methods, however I can't get my balancing to work properly and so the results don't come out in the right order.
I've been changing things around trying to get it to work, here's how i've got it the moment, in which when requesting a traversal I get an error in the command line saying "Object reference not set to an instance of an object." The main problem i've been having is how and where to invoke the balance method in order to sort and traverse.
I've searched all over the place but can't seem to find anything that I can get working in my code.
Below are my classes - could any of you give me a hand with how to get this working please? Apologies for the lack of comments in the code.
Here is my BinaryTree class:
//‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
///
/// Binary Tree data structure
/// Begin Binary Tree structure definition
///
// ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐
using System;
using csKicksTreeApp;
class BinaryTree
{
private BinaryTreeNode head;
private int size;
//private int depth;
///
/// Constructor ‐ Creates a new instance of a Binary Tree
///
public BinaryTree()
{
head = null;
size = 0;
}
///
/// Gets or sets the root of the tree (the top‐most node)
///
public BinaryTreeNode Root
{
get { return head; }
set { head = value; }
}
///
/// Gets the number of elements stored in the tree
///
public int Count
{
get { return size; }
}
///
/// Adds a new element to the tree
///
public void Add(Int32 value)
{
BinaryTreeNode node = new BinaryTreeNode(value);
this.Add(node);
}
///
/// Adds a node to the tree
///
public void Add(BinaryTreeNode node) //Do I need to invoke the balance method for this?
{
if (this.head == null) //'this' is the tree, check if empty
{
this.head = node; //set node as root of the tree
//node.Parent = this.head; //its parent points to itself
size++;
}
else
{
if (node.Parent == null)
node.Parent = head; //start at head
//Node is inserted on the left side if it is smaller or equal to the parent
bool insertLeftSide = false;
if (node.Value < node.Parent.Value)
{
insertLeftSide = true;
}
if (insertLeftSide) //insert on the left
{
if (node.Parent.LeftChild == null)
{
node.Parent.LeftChild = node; //insert in left
size++;
}
else
{
node.Parent = node.Parent.LeftChild; //scan down to left child
this.Add(node); //recursive call
}
}
else //insert on the right
{
if (node.Parent.RightChild == null)
{
node.Parent.RightChild = node; //insert in right
size++;
}
else
{
node.Parent = node.Parent.RightChild;
this.Add(node);
}
}
}
}
///
/// Returns the first node in the tree with the parameter value.
///
public BinaryTreeNode Find(Int32 value)
{
BinaryTreeNode node = this.head; //start at head
while (node != null)
{
if (node.Value.Equals(value)) //parameter value found
return node;
else
{
//Search left if the value is smaller than the current node
bool searchLeft = false;
if (node.Value > value)
{
searchLeft = true;
}
if (searchLeft)
node = node.LeftChild; //search left
else
node = node.RightChild; //search right
}
}
return null; //not found
}
///
/// Removes a value from the tree and returns whether the removal was successful.
///
public bool Remove(Int32 value)
{
BinaryTreeNode removeNode = Find(value);
return this.Remove(removeNode);
}
///
/// Removes a node from the tree and returns whether the removal was successful.
///>
///
public bool Remove(BinaryTreeNode removeNode)
{
if (removeNode == null)
return false; //value doesn't exist or not of this tree
//Note whether the node to be removed is the root of the tree
bool wasHead = (removeNode == head);
if (this.Count == 1)
{
this.head = null; //only element was the root
size--; //decrease total element count
}
else if (removeNode.IsLeaf) //Case 1: No Children
{
//Remove node from its parent
if (removeNode.IsLeftChild)
{
removeNode.Parent.LeftChild = null;
}
else
{
removeNode.Parent.RightChild = null;
}
removeNode.Parent = null;
size--; //decrease total element count
}
else if (removeNode.ChildCount == 1) //Case 2: One Child
{
if (removeNode.HasLeftChild)
{
//Put left child node in place of the node to be removed
removeNode.LeftChild.Parent = removeNode.Parent; //update parent
if (wasHead)
{
this.Root = removeNode.LeftChild; //update root reference if needed
}
if (removeNode.IsLeftChild) //update the parent's child reference
{
removeNode.Parent.LeftChild = removeNode.LeftChild;
}
else
{
removeNode.Parent.RightChild = removeNode.LeftChild;
}
}
else //Has right child
{
//Put left node in place of the node to be removed
removeNode.RightChild.Parent = removeNode.Parent; //update parent
if (wasHead)
{
this.Root = removeNode.RightChild; //update root reference if needed
}
if (removeNode.IsLeftChild) //update the parent's child reference
{
removeNode.Parent.LeftChild = removeNode.RightChild;
}
else
{
removeNode.Parent.RightChild = removeNode.RightChild;
}
}
removeNode.Parent = null;
removeNode.LeftChild = null;
removeNode.RightChild = null;
size--; //decrease total element count
}
else //Case 3: Two Children
{
//Find inorder predecessor (right‐most node in left subtree)
BinaryTreeNode successorNode = removeNode.LeftChild;
while (successorNode.RightChild != null)
{
successorNode = successorNode.RightChild;
}
removeNode.Value = successorNode.Value; //replace value
this.Remove(successorNode); //recursively remove the inorder predecessor
}
return true;
}
//-----------------------------------
// balancing the binary tree
// after the tree has been built
//
// WARNING! This code has not been checked...
// and you may need to change it
// depending on your tree design
//------------------------------------
public void balance(BinaryTreeNode node)
{
if (node != null)
{
BinaryTree tree = new BinaryTree();
if (node.RightChild.level - node.LeftChild.level > 1)
{
if (node.RightChild.level > node.LeftChild.level)
{
node = rotateL(node);
node = rotateR(node);
}
else
{
node = rotateL(node);
}
}
else
{
if (node.LeftChild.level > node.RightChild.level)
{
node = rotateR(node);
node = rotateL(node);
}
else
{
node = rotateR(node);
}
}
balance(node.LeftChild);
balance(node.RightChild);
}
}
// depth from node to left
public int heightL(BinaryTreeNode node)
{
if (node == null)
return 0;
return node.LeftChild.level + 1;
}
// depth from node from the right
public int heightR(BinaryTreeNode node)
{
if (node == null)
return 0;
return node.RightChild.level + 1;
}
// left rotation around node
public BinaryTreeNode rotateL(BinaryTreeNode node)
{
if (node == null)
return null;
else
{
BinaryTreeNode newRoot = node.RightChild;
node.RightChild = newRoot.leftChild;
newRoot.leftChild = node;
return newRoot;
}
}
// right rotation around node
public BinaryTreeNode rotateR(BinaryTreeNode node)
{
if (node == null)
return null;
else
{
BinaryTreeNode newRoot = node.LeftChild;
node.LeftChild = newRoot.RightChild;
newRoot.RightChild = node;
return newRoot;
}
}
//-------------------------------------
// TraverseInOrder
// Traverses the tree in this order:
// Left, Root, Right
// Calls the private function InOrder
//-------------------------------------
public void TraverseInOrder()
{
InOrder(ref head);
}
private void InOrder(ref BinaryTreeNode node)
{
balance(node); //Where I was attempting to balance before traversing which I think is what throws the error.
if (node == null)
return;
if (node.LeftChild != null)
{
InOrder(ref node.leftChild);
}
Console.WriteLine(node.value);
if (node.RightChild != null)
{
InOrder(ref node.rightChild);
}
}
//-------------------------------------
// TraversePreOrder
// Traverses the tree in this order:
// Root, Left, Right
//-------------------------------------
public void TraversePreOrder()
{
PreOrder(ref head);
}
private void PreOrder(ref BinaryTreeNode node)
{
if (node == null)
return;
Console.WriteLine(node.value);
if (node.LeftChild != null)
{
InOrder(ref node.leftChild);
}
if (node.RightChild != null)
{
InOrder(ref node.rightChild);
}
}
//-------------------------------------
// TraversePostOrder
// Traverses the tree in this order:
// Left, Right, Root
//-------------------------------------
public void TraversePostOrder()
{
PostOrder(ref head);
}
private void PostOrder(ref BinaryTreeNode node)
{
if (node == null)
return;
if (node.LeftChild != null)
{
InOrder(ref node.leftChild);
}
if (node.RightChild != null)
{
InOrder(ref node.rightChild);
}
Console.WriteLine(node.value);
}
}BinaryTreeNode class:
//====================================================
//| Inspired by and Modified from: |
//| Visual C# Kicks ‐ http://www.vcskicks.com/ |
//| License ‐ http://www.vcskicks.com/license.html |
//====================================================
using System;
using System.Collections;
using System.Text;
namespace csKicksTreeApp
{
///
/// A Binary Tree node that holds an element and references to other tree nodes
///
/// Binary Tree Node class
class BinaryTreeNode
{
public Int32 value;
internal int level;
public BinaryTreeNode leftChild;
public BinaryTreeNode rightChild;
public BinaryTreeNode parent;
///
/// Creates a new instance of an empty node
///
public BinaryTreeNode()
{
this.level = 0;
this.parent = null;
this.leftChild = null;
this.rightChild = null;
//deleted = null;
}
///
/// Create a new instance of a Binary Tree node
///
public BinaryTreeNode(Int32 value)
{
this.level = 1;
this.value = value;
this.parent = null;
this.leftChild = null;
this.rightChild = null;
}
///
/// The value stored at the node
///
public Int32 Value
{
get { return value; }
set { this.value = value; }
}
///
/// Gets or sets the left child node
///
public BinaryTreeNode LeftChild
{
get { return leftChild; }
set { leftChild = value; }
}
///
/// Gets or sets the right child node
///
public BinaryTreeNode RightChild
{
get { return rightChild; }
set { rightChild = value; }
}
///
/// Gets or sets the parent node
///
public BinaryTreeNode Parent
{
get { return parent; }
set { parent = value; }
}
///
/// Gets whether the node is a leaf (has no children)
///
public bool IsLeaf
{
get { return this.ChildCount == 0; }
}
///
/// Gets whether the node is internal (has children nodes)
///
public bool IsInternal
{
get { return this.ChildCount > 0; }
}
///
/// Gets whether the node is the left child of its parent
///
public virtual bool IsLeftChild
{
get { return this.Parent != null && this.Parent.LeftChild == this; }
}
///
/// Gets whether the node is the right child of its parent
///
public virtual bool IsRightChild
{
get { return this.Parent != null && this.Parent.RightChild == this; }
}
///
/// Gets the number of children this node has
///
public int ChildCount
{
get
{
int count = 0;
if (this.LeftChild != null)
count++;
if (this.RightChild != null)
count++;
return count;
}
}
///
/// Gets whether the current node has a left child node
///
public bool HasLeftChild
{
get { return (this.LeftChild != null); }
}
///
/// Gets whether the current node has a right child node
///
public bool HasRightChild
{
get { return (this.RightChild != null); }
}
}
}// end of binary tree node classAnd finally my program:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace csKicksTreeApp
{
class Program
{
static void Main(string[] args)
{
string input;
int value;
bool flag = true;
while (flag)
{
try
{
Random randomGenerator = new Random();
generate myRand = new generate(randomGenerator);
BinaryTree tree = new BinaryTree();
Console.WriteLine("Welcome to the Binary Search Tree.\n");
Options:
Console.WriteLine("\nWhat would you like to do?\nPress \"I\" to insert a node.\nPress \"D\" to delete a node.\nPress \"A\" to traverse in-order.\nPress \"B\" to traverse pre-order.\nPress \"C\" to traverse post-order.\nPress \"E\" to end the program.\n");
input = Console.ReadLine();
if (input == "i" || input == "I")
{
Console.WriteLine("\nPress \"I\" again if you would like to input your own value or any other key to input a random number.");
input = Console.ReadLine();
if (input == "i" || input == "I")
{
Console.WriteLine("\nPlease enter the value you would like to insert and press enter");
value = Convert.ToInt32(Console.ReadLine());
}
else
{
Console.WriteLine("\nGenerating random number...");
value = myRand.GetRandom();
}
tree.Add(value);
// rootNode = tree.Root;
Console.WriteLine("The value {0} was entered into the Tree.\n", value);
goto Options;
}
else if (input == "d" || input == "D")
{
Console.WriteLine("\nPlease enter the value you would like removing\n");
value =Convert.ToInt32(Console.ReadLine());
tree.Remove(value);
Console.WriteLine("The value {0} was removed from the Tree.\n", value);
Console.WriteLine("\nPress any key to return to the options.\n");
Console.ReadLine();
goto Options;
}
else if (input == "a" || input == "A")
{
Console.WriteLine("\nBelow are the contents of the Binary Search Tree, shown In Order. Press any key to return to Options.\n");
tree.TraverseInOrder();
Console.ReadLine();
goto Options;
}
else if (input == "b" || input == "B")
{
Console.WriteLine("\nBelow are the contents of the Binary Search Tree, shown Pre Order. Press any key to return to Options.\n");
tree.TraversePreOrder();
Console.ReadLine();
goto Options;
}
else if (input == "c" || input == "C")
{
Console.WriteLine("\nBelow are the contents of the Binary Search Tree, shown Post Order. Press any key to return to Options.\n");
tree.TraversePostOrder();
Console.ReadLine();
goto Options;
}
else if (input == "e" || input == "E")
{
goto End;
}
else
{
Console.WriteLine("\nInvalid command. Please choose one of the options listed.");
Console.ReadLine();
goto Options;
}
End:
Console.WriteLine("\nWould you like to exit or restart the program? Press \"E\" again to exit, \"R\" to restart or \"C\" to cancel.\n");
string newop = Console.ReadLine();
flag = false;
if (newop == "r" || newop == "R")
{
flag = true;
Console.WriteLine();
}
else if (newop == "c" || newop == "C")
{
goto Options;
}
}
catch (FormatException e)
{
Console.WriteLine(e.Message);
}
catch (OutOfMemoryException e)
{
Console.WriteLine(e.Message);
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
}
}
}
class generate
{
private Random _randomGenerator;
private int _maxResult = 100;
public int maxResult
{
get
{
return _maxResult;
}
}
public generate()
{
throw new Exception("Needs a random object to be passed");
}
public generate(Random randomGenerator)
{
//Initialise the random number generator
_randomGenerator = randomGenerator;
}
private int _generateRandom()
{
return _randomGenerator.Next(1, _maxResult + 1);
}
public int GetRandom()
{
return _generateRandom();
}
}
}I've included all the code because i'm a beginner and have no idea where the problems may lie in the code. Any help would be greatly appreciated.
Thank you!
