Binary
Search Tree in ASP .Net
To create
Binary Search Tree(BST) in Asp.net application
first you need to create a Node class. Something like following :
class Node
{
public
String data;
public
int freq = 0;
public
Node left, right;
public
Node()
{ }
public
Node(String data)
{
this.data = data;
left = null;
right = null;
}
}
Next You need to create a class including different
functions.Like
class BinaryTreeImp
{
Node root;
String outputfreq = "";
static int count = 0;
public BinaryTreeImp()
{
root
= null;
}
public Node
CreateNode(String s)
{
Node Temp = new Node();
Temp.data = s;
Temp.left = null;
Temp.right = null;
return Temp;
}
public Node
CreateBTree()
{
Node root = null;
return root;
}
public Node
insertNode(Node root, String data)
{
Node temp;
temp
= root;
if (root == null)
{
root = new Node(data);
root.freq = 1;
return root;
}
if (data.CompareTo(temp.data) == 0)
{
//Node newNode = new Node(data);
temp.freq++;
}
else if (data.CompareTo(temp.data) < 0)
{
Node newNode = new
Node(data);
if (temp.left == null)
{
temp.left = newNode;
newNode.freq = 1;
return temp;
}
else
{
temp = temp.left;
insertNode(temp, data);
}
}
else if
(data.CompareTo(temp.data) > 0)
{
Node newNode = new
Node(data);
if (temp.right == null)
{
temp.right = newNode;
newNode.freq = 1;
return temp;
}
else
{
temp = temp.right;
insertNode(temp, data);
}
}
return root;
}
public String
displayTree(Node root)
{
Node temp;
temp
= root;
if (temp == null)
return null;
displayTree(root.right);
outputfreq += temp.freq + " "
+ temp.data + " ";
displayTree(root.left);
// return temp.freq +" "+ displayTree(temp.left)
+ displayTree(temp.right);
return outputfreq;
}
public int countNode(Node root)
{
if (root == null)
return 0;
else
if (root.left == null
&& root.right == null)
return 1;
else
return (countNode(root.left) +
countNode(root.right) + 1);
}
}
Class mainly have Three functions insertNode, displayNode,
CountNode.
InsertNode() is used to insert different text inputs in tree based on string comparison.
dispalayNode() is used to return all nodes values to calling
function. In this we dont take output on console but on make a long string of
all Tree nodes.
CountNode() function is used to count no of nodes in Tree.
You may use all these Classes as following:
BinaryTreeImp tree = new
BinaryTreeImp(); // create a null tree
Node root = tree.CreateBTree(); // create a root node
of tree having null value.
Here i have an Array of words, and using for loop i stored
all the values in tree.
for (int g = 0; g <
words.Length; g++)
{
root
= tree.insertNode(root, words[g]);
}//for
You can get all the values from the tree for
further processing:
String freq = tree.displayTree(root);
Or you can get count of tree nodes:
int count=countNode(root);
Hope all this helpful for you if you know the basics of BST and .Net
Comments
Post a Comment