Binary Tree
Binary search Tree is a Data Structure having following Properties .
1. Left Node value must be less than root node value
2. Right Node value must be greater than root node value
3. Each Node must be Unique.
Normally this algorithm is used to search the Data present in the collection.
This binary Tree have three traversal to visit the nodes. PreOrder, PostOrder,InOrder to iterate the elements from collections, Normally it is used to search the item. When using Binary Search we can reduce the search time to O(Log n),
Now we See the Count Property, Insert, Exists, Search, PreOrder, PostOrder, InOrder Traversal Methods.
Insert the int data into the Tree in the order : 8,3,4,12,10,13,1
InOrder
1. First visit the Left Child
2. Second visit the parent node
3. Third visit the Right Child
PostOder
1. First visit the Left Child
2. Second visit the Right Child
3. Third visit the Parent node.
PreOrder
1. First visit the Parent node
2. Second visit the Left Child
3. Third visit the Right Child
Output :
Let we see now the Implementation of BinaryTreeNode<T>
enum Child
{
Left,
Right
}
enum Order
{
InOrder,
PostOrder,
PreOrder
}
[Serializable]
class BinaryTreeNode<T>
{
public T Value
{
set;
get;
}
public BinaryTreeNode<T>Left;
public BinaryTreeNode<T>Right;
public BinaryTreeNode(T value)
{
this.Value = value;
}
}
Now the Implementation of the Calling Part of the Collection.
class Program
{
static void Main(string[] args)
{
BinarySearchTree<int> tree = new BinarySearchTree<int>();
tree.Insert(8);
tree.Insert(3);
tree.Insert(4);
tree.Insert(12);
tree.Insert(10);
tree.Insert(13);
tree.Insert(1);
Console.WriteLine("Total Nodes in Tree is {0}", tree.Count);
BinaryTreeNode
Console.WriteLine("\nSearch Node {0} : Left Child : {1}, Right Child : {2}",
searchnode.Value, searchnode.Left.Value, searchnode.Right.Value);
Console.WriteLine("\n{0} Node Exists in Tree {1} : ", 13, tree.Exists(13));
Console.WriteLine("\nInOrder Traversal");
foreach (BinaryTreeNode
{
Console.WriteLine("Node : "+v.Value);
}
Console.WriteLine();
Console.WriteLine("PreOrder Traversal");
foreach (BinaryTreeNode
{
Console.WriteLine("Node : "+v.Value);
}
Console.WriteLine();
Console.WriteLine("PostOrder Traversal");
foreach (BinaryTreeNode
{
Console.WriteLine("Node : "+v.Value);
}
Console.Read();
}
}
Now the Implementation Of BinaryTree With Insert, PostOrder, PreOrder, InOrder, Search, Exists Methods and Count Property
[Serializable]
class BinarySearchTree<T>where T : IComparable<T>
{
private BinaryTreeNode<T> root;
public int Count { set; get; }
public void Insert(T value)
{
BinaryTreeNode<T> node = new BinaryTreeNode<T> (value);
if (root == null)
{
root = node;
}
else
{
PlaceNode(root, node);
}
Count++;
}
public void PlaceNode(BinaryTreeNode<T> root, BinaryTreeNode<T> newnode)
{
BinaryTreeNode<T> ponode=root;
BinaryTreeNode<T> tree = null;
Child pos = Child.Left;
do
{
pos = CheckNode(ponode, newnode);
tree = ponode;
if (pos == Child.Left)
{
ponode = tree.Left;
}
else
{
ponode = tree.Right;
}
}
while (ponode != null);
if(pos==Child.Left)
tree.Left = newnode;
else
tree.Right =newnode;
}
private Child CheckNode(BinaryTreeNode<T> root, BinaryTreeNode<T> newnode)
{
if (newnode.Value.CompareTo(root.Value) < 0)
{
return Child.Left;
}
else if (newnode.Value.CompareTo(root.Value) > 0)
{
return Child.Right;
}
else
{
throw new ArgumentException("Node is Duplicated");
}
}
public bool Exists(T value)
{
BinaryTreeNode<T> node=Search(value);
if(node!=null)
return true;
else
return false;
}
public BinaryTreeNode<T> Search(T value)
{
BinaryTreeNode<T> node = root;
while (node != null)
{
if (node.Value.CompareTo(value) == 0)
{
return node;
}
else if (node.Value.CompareTo(value) > 0)
{
node = node.Left;
}
else
{
node = node.Right;
}
}
return null;
}
private IEnumerable<BinaryTreeNode<T> > Ordering(BinaryTreeNode<T> node,Order ord)
{
BinaryTreeNode<T> first = null;
BinaryTreeNode<T> secon = null;
BinaryTreeNode<T> third = null;
if (node != null)
{
if (ord == Order.InOrder)
{
foreach (BinaryTreeNode<T> firstiter in Ordering(node.Left, ord))
{
yield return firstiter;
}
yield return node;
foreach (BinaryTreeNode<T> firstiter in Ordering(node.Right, ord))
{
yield return firstiter;
}
}
else if(ord == Order.PostOrder)
{
foreach (BinaryTreeNode<T> firstiter in Ordering(node.Left, ord))
{
yield return firstiter;
}
foreach (BinaryTreeNode<T> firstiter in Ordering(node.Right, ord))
{
yield return firstiter;
}
yield return node;
}
else if (ord == Order.PreOrder)
{
yield return node;
foreach (BinaryTreeNode<T> firstiter in Ordering(node.Left, ord))
{
yield return firstiter;
}
foreach (BinaryTreeNode<T> firstiter in Ordering(node.Right, ord))
{
yield return firstiter;
}
}
}
}
public IEnumerable<BinaryTreeNode<T> > PreOrder()
{
return Ordering(root, Order.PreOrder);
}
public IEnumerable<BinaryTreeNode<T> > PostOrder()
{
return Ordering(root, Order.PostOrder);
}
public IEnumerable<BinaryTreeNode<T> > InOrder()
{
return Ordering(root, Order.InOrder);
}
}
From this article we can learn how to create a traversal in Binary Tree and Insert Method and Exists Method.
