Solved

Deleting Within A Tree

Posted on 1998-06-25
3
217 Views
Last Modified: 2010-04-01
Need help with code that will enable the user to delete a node within a tree of words.
0
Comment
Question by:John500
  • 2
3 Comments
 
LVL 22

Accepted Solution

by:
nietod earned 40 total points
ID: 1166653
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
 
LVL 22

Expert Comment

by:nietod
ID: 1166654
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
 

Author Comment

by:John500
ID: 1166655
Much Thanks!
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now