Click here to Skip to main content
14,304,866 members

BST Deletion

Rate this:
1.56 (8 votes)
Please Sign up or sign in to vote.
1.56 (8 votes)
24 Sep 2006
It is for the deletion of the node from the BST Tree

Introduction

It is a project which will work amizinzaly for deletion of the node from the BST tree. It will take the node values from the main class and when u will use the function of the BST Deletion it will delete the node from the tree according to the rule of the BST tree. It will also have the ability of the inner class means u will see that node class is more protected through the inner class concept. I hope u people will enjoy this small effort . thanx

these functions are use for the node specification and for root specification

class BinTree

{

class Node

{

public int info;

public Node left, right;

public Node(int i)

{

info = i;

left = null;

right = null;

}

}

Node root;

public BinTree()

{

root = null;

}

For inserting the node in the BST tree

public void BST(int val)

{

Node p = root;

Node prev = root;

while (p != null)

{

if (val > p.info)

{

prev = p;

p = p.right;

}

else if (val < p.info)

{

prev = p;

p = p.left;

}

}

if ((prev.info) > val)

prev.left = new Node(val);

else

prev.right = new Node(val);

}

now for the deletion of the node from the BST tree

this function will use by the user directely

public void bdel(int i)

{

BST_DELTEE(i);

}

this function will call indirectly by the calling for the deletion of the node from the BST tree this is done just for increase the security

void BST_DELTEE(int ITEM)

{

Node ptr = root, parent = null;

bool flag = false;

while (ptr != null && !flag)

{

if (ITEM < ptr.info)

{

parent = ptr;

ptr = ptr.left;

}

else if (ITEM > ptr.info)

{

parent = ptr;

ptr = ptr.right;

}

else if (ptr.info == ITEM)

flag = true;

}

int Case = 0;

if (!flag)

Console.WriteLine("ITEM does not exist: No deletion");

else if (ptr.left == null && ptr.right == null)

Case = 1;

else if (ptr.left != null && ptr.right != null)

Case = 3;

else

Case = 2;

if (Case == 1)

{

if (parent.left == ptr)

parent.left = null;

else

parent.right = null;

}

else if (Case == 2)

{

if (parent.left == ptr)

{

if (ptr.left == null)

parent.left = ptr.right;

else

parent.left = ptr.left;

}

else

{

if (parent.right == ptr)

{

if (ptr.left == null)

parent.right = ptr.right;

else

parent.right = ptr.left;

}

}

}

else if (Case == 3)

{

Node ptr1 = SSUCC(ptr);

int item1 = ptr1.info;

BST_DELTE(item1);

ptr.info = item1;

}

}

this function will use for the case 3 of the BST deletion which means a node have the both childs left and right then case 3 will occur because of which this function will call which will return the reference of the deletion node's right then left most child reference it is done just because of the rule of the deletion from the BST tree

Node SSUCC(Node ptr)

{

Node ptr1 = ptr.right;

if (ptr1 != null)

while (ptr1.left != null)

ptr1 = ptr1.left;

return (ptr1);

}

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Abbas Ali Butt
Other
Pakistan Pakistan
My name is Abbas Ali Butt. I am a student of Punjab University Information and Technology.

Comments and Discussions

 
-- There are no messages in this forum --
Article
Posted 24 Sep 2006

Stats

16.2K views
6 bookmarked