188-binary-search-tree-implementation-in-c

Major property of the binary search tree is self-similarity (every leaf can be root for another smaller binary search tree). For that reason, in BST we can use recursive functions to find or count the data. Searching through BST is very efficient, since all of the data are indexed. Binary search tree implementation in C# is subject of this article. First thing we need to implement binary search tree is to define node class.

public class node_in_sbt
{

public int data_value;
public node_in_sbt left, right;
public node_in_sbt(int a)
{

this.data_value = a;
left = null;
right = null;

}

}

Next class we need to have is class for binary search tree.

public class Tree
{

public node_in_sbt root_of_the_tree;
public Tree()
{

root_of_the_tree = null;

}

Apart from constructor Tree() with no parameters, we can use polymorphism and add another constructor that takes array as input parameter. Code that insert node in binary search tree is following:

public Tree(int[] input)
{

root_of_the_tree = null;
for (int i = 0; i < input.Length; i++)
{

this.insert(this.root_of_the_tree, this.addNode(input[i]));

}

}

Method insert used in the constructor with an array as input parameter must have two parameters:

  • node that is root of the tree
  • integer number that will be added by another method called addNode that has return value with type of an node of the tree, and takes int as input parameter.

public node_in_sbt addNode(int int_data)
{

node_in_sbt temp = new node_in_sbt(int_data);
if (root_of_the_tree == null) root_of_the_tree = temp;
return temp;

}

addNode simply create and return node back to the tree. If there was no root of the tree this node becomes the root. Otherwise, method insert will do the right positioning.

public void insert(node_in_sbt root, node_in_sbt newNode)
{

while (root != null)
{

if (newNode.data_value > root.data_value)
{

if (root.right == null)
{

root.right = newNode;
MessageBox.Show(root.right.data_value.ToString(), “Right”);
break;

}
root = root.right;
MessageBox.Show(root.data_value.ToString(), “new root Right”);

}
else
{

if (root.left == null)
{

root.left = newNode;
MessageBox.Show(newNode.data_value.ToString(), “Left”);
break;

}
root = root.left;
MessageBox.Show(root.data_value.ToString(), “new root Left”);

}

}

}

So method insert takes two parameters (both of the node type) and returns nothing, since it is member of the tree class. Another method would be useful for presenting ordered data (showing values from the left, then root, then right, then next root and so forth. This method must be called recursively (when called).

public void ordered(node_in_sbt root)
{

string str_return = “”;
if (root != null)
{

ordered(root.left);
str_return += root.data_value.ToString() + ” “;
MessageBox.Show(str_return);
ordered(root.right);

}

}

With this code, we can now implement binary search tree in C#, on following array

int[] input = { 53, 72, 14, 7, 17, 12, 1};
Tree bst = new Tree(input);
bst.ordered(bst.root_of_the_tree);

External links:

Binary Search Tree Implementation on bluesharktutorials
Binary Search Tree Implementation on codereview.stackexchange.com
Binary Search Tree Implementation on vcskicks
Binary Search Tree Implementation on c-sharpcorner.com
Binary Search Tree Implementation on introprogramming
Binary Search Tree Implementation on stackoverflow.com

Posted in c-sharp-code-examples

Leave a Reply

Your email address will not be published. Required fields are marked *

*