Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 234

# Deleting Within A Tree

Need help with code that will enable the user to delete a node within a tree of words.
0
John500
• 2
1 Solution

Commented:
I assume this if for me.  right?  If you send me a final copy.  (If we are there yet.)  I'll paste it in here.
0

Commented:
The final code:
*********************
void Probe::hook(Node *ptr,BinTree *tree, Node *par, Node *cur)
{
if(_top == 0)
{
tree->_root = ptr;
}
else if(cur == par->_left)
{
par->_left = ptr;
}
else
{
par->_right = ptr;
}
_trail[_top] = ptr;
}

void Probe::deleteCurrent(BinTree *tree)
{ // delete current node: trail [top]
if(_top < 0)
return;  // empty tree

Node *par, *cur = _trail[_top];  // nicer name for current node

tree->_numWords -= cur->_count;

if(_top > 0)
par = _trail[_top - 1];  //parent if current node has one

if(!cur -> _left) // has no left child, might have right child
{
hook(cur->_right,tree,par,cur);
if(!_trail[_top]) _top--;  // node gone, back up
}

else if (!cur->_right)  // has no right child, does have left child
{
hook(cur->_left,tree,par,cur);
}

else  // cur has both children present
{
// find inorder successor to cur
Node * p = cur->_right;
if(!p->_left)  // already at inorder successor
{
p->_left = cur->_left;  // make p's left ptr same as cur's
hook(p,tree,par,cur);
}
else
{
while(p->_left && p->_left->_left)
{ p = p->_left;
// now p points to parent of inorder successor to cur
Node *succ = p->_left;
p->_left = succ->_right;  // hook up subtree

succ->_left = cur->_left;
succ->_right = cur->_right;
hook(succ,tree,par,cur);
}
}
}
cur->_left = NULL;
cur->_right = NULL;
delete cur;
}

0

Author Commented:
Much Thanks!
0

## Featured Post

• 2
Tackle projects and never again get stuck behind a technical roadblock.