Creation:
1. To create a binary tree, first create an empty node whose left and right are set to null.
2. For the first time, create a node and read a value and take it as root
3. Next onwards, check whether the element is less than or greater than the root element.
4. If the element is less than root element continue with left sub tree
5. If the element is greater than root element continue with right sub tree
6. Repeat the steps 4 and 5 accordingly till an empty node encounters
7. Create a node and insert it there.
Insertion:
1. First, check whether the element is less than or greater than the root element.
2. If the element is less than root element continue with left sub tree
3. If the element is greater than root element continue with right sub tree
4. Repeat the steps 2 and 3 accordingly till an empty node encounters
5. Create a node and insert it there.
Deletion:
1. Consider three cases for deleting a node
4 Deleting a node with no children
4 Deleting a node with one child
4 Deleting a node with two children
2. If the tree is ‘null’, print the message accordingly.
3. First, search for that starting from the root. i.e. move to left if the element is less than the parent or right till the element is encountered or an empty node is encountered
4. If empty node is encountered, print “no element”
5. Otherwise, if the node has no children, delete it directly.
6. If the node has only left child, parent node must be linked to its left before deleting the node
7. If the node has only right child, parent node must be linked to its right before deleting the node
8. If a node to be deleted has two children, find minimum value in its right sub-tree. Replace the element to be deleted with the minimum element and repeat the same process to delete the node containing minimum element.
Program to create a binary tree and print the elements in different traversals
class tree
{
int x;
tree left;
tree right;
}
class BTree
{
private tree t;
BTree()
{
t=null;
}
public void insert(int v)
{
t=insert(t,v);
}
public void showLVR()
{
System.out.println("\nLVR :\n");
LVR(t);
}
public void showVLR()
{
System.out.println("\nVLR :\n");
VLR(t);
}
public void showLRV()
{
System.out.println("\nLRV :\n");
LRV(t);
}
tree insert(tree t, int v)
{
if(t==null)
{
t = new tree();
t.x = v;
t.left = null;
t.right = null;
}
else if(v
t.left = insert(t.left,v);
else if(v>t.x)
t.right = insert(t.right,v);
return t;
}
public void LVR(tree t)
{
if(t!=null)
{
LVR(t.left);
System.out.print("\t"+t.x);;
LVR(t.right);
}
}
public void LRV(tree t)
{
if(t!=null)
{
LRV(t.left);
LRV(t.right);
System.out.print("\t"+t.x);
}
}
public void VLR(tree t)
{
if(t!=null)
{
System.out.print("\t"+t.x);
VLR(t.left);
VLR(t.right);
}
}
}
class BTreeTest
{
public static void main(String as[])
{
BTree t1=new BTree();
t1.insert(30);
t1.insert(20);
t1.insert(10);
t1.insert(40);
t1.showLVR();
t1.showVLR();
t1.showLRV();
}
}
/* Output */
LVR :
10 20 30 40
VLR :
30 20 10 40
LRV :
10 20 40 30
Assume the elements to be:
Input: 45,20,80,15, 30,70, 90
|
| |
| 45 |
| 80 |
| 70 |
| 15 |
| 30 |
| Binary tree for the sample elements |
LVR :
15 20 30 45 70 80 90
VLR :
45 20 15 30 80 70 90
LRV :
15 30 20 70 90 80 45
0 comments:
Post a Comment