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
  • Last Modified:

Deleting Within A Tree

Need help with code that will enable the user to delete a node within a tree of words.
0
John500
Asked:
John500
  • 2
1 Solution
 
nietodCommented:
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
 
nietodCommented:
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->_numNodes--;  // adjust tree statistics
 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
 
John500Author Commented:
Much Thanks!
0

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

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