|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
Stay one step ahead of the competition. Evaluate and give feedback
on some of the hottest web development tools on the market today.
Make your opinion heard! Click
Here
|
|
#1
May 4th, 2008, 06:39 AM
|
|||
|
|||
|
Binary tree
How to Delete a node from a binary tree (the node have data , right pointer and left pointer )
|
|
#2
May 4th, 2008, 09:32 PM
|
||||
|
||||
|
There are a few cases to consider here. Here're some of them.
1. Node to be deleted has no children Simply delete the node 2. The node has one child (either a left or a right child) Point the parent of this node to the child and then delete the node. Say we want to delete node 3 from the figure below. Code:
Before delete
===========
4
/ \
3 6
/ / \
2 5 7
/
1
In this case, we simply point 4 to 2 and then delete node 3 Code:
After delete
===========
4
/ \
2 6
/ / \
1 5 7
3. Node has two children. Replace the node by its inorder successor. Say we want to delete 3 in the figure below: Code:
Before Delete
==========
6
/ \
3 7
/ \ \
2 5 8
/ /
1 4
The in-order successor of node 3 is 4. Hence we grab that node and replace it as shown below: Code:
After Delete
==========
6
/ \
4 7
/ \ \
2 5 8
/
1
__________________
Up the Irons What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home. "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest Down with Sharon Osbourne Puzzle of the Month solved by sizeablegrin, etienne141 and L7Sqr, superior C/C++ programmers of the month
|
|
#3
May 5th, 2008, 05:24 AM
|
|||
|
|||
|
This is an example i did before :
Code:
struct BST* BST_Remove(struct BST *BST,int *removeptr)
{
// Parent of RemoveNode
struct Tree_Node *parent;
// Parent of traversal
struct Tree_Node *parent_traversal;
struct Tree_Node *tempTraversal;
struct Tree_Node *traversal;
struct Tree_Node *RemoveNode;
// To maintain children of RemoveNode
struct Tree_Node *tempRemoveNode;
char special = 'y';
parent = BST->root;
traversal = BST->root;
tempTraversal = BST->root;
parent_traversal = BST->root;
/*
if no child, just delete
if one child, point by grandparent
if two children,
swap with it with
inorder-successor(Left child of right sub Tree)
// Smallest in right sub tree
Traverse once to right , then continue
traverse to left
or
inorder-predecessor(Right child of Left sub Tree)
// Largest in left sub tree
*/
// Iteractve Remove Tree Node
while(traversal != NULL)
{
// To remove root node
if (*removeptr == tempTraversal->value)
{
RemoveNode = BST->root;
tempRemoveNode = BST->root;
// got 2 children
if (RemoveNode->leftNode != NULL
&& RemoveNode->rightNode != NULL)
{
// Traverse once to right tree
if (tempTraversal->rightNode != NULL)
{
tempTraversal = tempTraversal->rightNode;
}
// Continue traverse smallest unit left sub tree
while(tempTraversal->leftNode != NULL)
{
tempTraversal = tempTraversal->leftNode;
}
tempRemoveNode->leftNode = RemoveNode->leftNode;
tempRemoveNode->rightNode = RemoveNode->rightNode;
tempTraversal->leftNode = tempRemoveNode->leftNode;
tempTraversal->rightNode = tempRemoveNode->rightNode;
if (traversal != NULL)
{
traversal = traversal->rightNode;
}
traversal->leftNode = NULL;
Tree_Node_Deallocate(RemoveNode);
BST->root = tempTraversal;
while(traversal != NULL)
{
traversal = traversal->leftNode;
}
}
}
else if (traversal != NULL)
{
if (*removeptr < traversal->value)
{
traversal = traversal->leftNode;
parent_traversal = parent_traversal->leftNode;
if (traversal != NULL)
{
RemoveNode = traversal;
tempRemoveNode = traversal;
}
if (traversal != NULL)
{
if (traversal->value == *removeptr)
{
// got 2 children
if (RemoveNode->leftNode != NULL
&& RemoveNode->rightNode != NULL)
{
// Traverse once to right tree
if (traversal->rightNode != NULL)
{
traversal = traversal->rightNode;
parent_traversal = parent_traversal->rightNode;
}
// Continue traverse smallest unit left sub tree
while(traversal->leftNode != NULL)
{
traversal = traversal->leftNode;
}
// To identify parent of traversal
if (parent_traversal->leftNode != NULL)
{
while(parent_traversal->leftNode->leftNode != NULL)
{
parent_traversal = parent_traversal->leftNode;
}
special = 'n';
}
if (special == 'n')
{
tempRemoveNode->rightNode = RemoveNode->rightNode;
tempRemoveNode->leftNode = RemoveNode->leftNode;
}
if (traversal->value
<parent->value)
{
parent->leftNode = traversal;
}
else
{
parent->rightNode = traversal;
}
if (special == 'n')
{
traversal->leftNode = tempRemoveNode->leftNode;
traversal->rightNode = tempRemoveNode->rightNode;
if (RemoveNode->value
< parent_traversal->value)
{
parent_traversal->leftNode = RemoveNode;
}
else
{
parent_traversal->rightNode = RemoveNode;
}
}
else
{
traversal->leftNode = tempRemoveNode->leftNode;
}
Tree_Node_Deallocate(RemoveNode);
}
// Got 1 child
else if (RemoveNode->leftNode != NULL
|| RemoveNode->rightNode != NULL)
{
// Swap it with its Left child
if (RemoveNode->leftNode != NULL)
{
traversal = traversal->leftNode;
if (traversal->value < parent->value)
{
parent->leftNode = traversal;
}
else
{
parent->rightNode = traversal;
}
Tree_Node_Deallocate(RemoveNode);
}
// Swap it with its Right child
if (RemoveNode->rightNode != NULL)
{
traversal = traversal->rightNode;
if (traversal->value < parent->value)
{
parent->leftNode = traversal;
}
else
{
parent->rightNode = traversal;
}
Tree_Node_Deallocate(RemoveNode);
}
}
// No child
else
{
Tree_Node_Deallocate(RemoveNode);
parent->leftNode = NULL;
}
}
}
if (parent != NULL)
{
parent = parent->leftNode;
}
}
else
{
traversal = traversal->rightNode;
parent_traversal = parent_traversal->rightNode;
if (traversal != NULL)
{
RemoveNode = traversal;
tempRemoveNode = traversal;
}
if (traversal != NULL)
{
if (traversal->value == *removeptr)
{
// got 2 children
if (RemoveNode->leftNode != NULL
&& RemoveNode->rightNode != NULL)
{
// Traverse once to right tree
if (traversal->rightNode != NULL)
{
traversal = traversal->rightNode;
parent_traversal = parent_traversal->rightNode;
}
// Continue traverse smallest unit left sub tree
while(traversal->leftNode != NULL)
{
traversal = traversal->leftNode;
}
parent_traversal = parent_traversal;
// To identify parent of traversal
if (parent_traversal->leftNode != NULL)
{
while(parent_traversal->leftNode->leftNode != NULL)
{
parent_traversal = parent_traversal->leftNode;
}
special = 'n';
}
tempRemoveNode->leftNode = RemoveNode->leftNode;
tempRemoveNode->rightNode = RemoveNode->rightNode;
if (traversal->value
<parent->value)
{
parent->leftNode = traversal;
}
else
{
parent->rightNode = traversal;
}
if (special == 'n')
{
traversal->leftNode = tempRemoveNode->leftNode;
traversal->rightNode = tempRemoveNode->rightNode;
if (RemoveNode->value
< parent_traversal->value)
{
parent_traversal->leftNode = RemoveNode;
}
else
{
parent_traversal->rightNode = RemoveNode;
}
}
else
{
traversal->leftNode = tempRemoveNode->leftNode;
}
Tree_Node_Deallocate(RemoveNode);
}
// Got 1 child
else if (RemoveNode->leftNode != NULL
|| RemoveNode->rightNode != NULL)
{
// Swap it with its Left child
if (RemoveNode->leftNode != NULL)
{
traversal = traversal->leftNode;
if (traversal->value < parent->value)
{
parent->leftNode = traversal;
}
else
{
parent->rightNode = traversal;
}
Tree_Node_Deallocate(RemoveNode);
}
// Swap it with its Right child
if (RemoveNode->rightNode != NULL)
{
traversal = traversal->rightNode;
if (traversal->value < parent->value)
{
parent->leftNode = traversal;
}
else
{
parent->rightNode = traversal;
}
Tree_Node_Deallocate(RemoveNode);
}
}
// No child
else
{
Tree_Node_Deallocate(RemoveNode);
parent->rightNode = NULL;
}
}
}
if (parent != NULL)
{
parent = parent->rightNode;
}
}
}
}
return BST;
}
I hope this help.
|
|
#4
May 5th, 2008, 09:52 AM
|
|||
|
|||
|
Really thanks
Really Thanks................................
|
|
#5
May 5th, 2008, 09:53 AM
|
|||
|
|||
|
tHANKS ALOT
|
|
| Viewing: Dev Shed Forums > Programming Languages > C Programming > Binary tree |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
