Solved

binary tree

Posted on 1998-11-29
13
305 Views
Last Modified: 2013-11-15
i need a code for removing a node from the tree, considerating all cases. function suld be recursive.
very basic c++ - no templates , very close to c language , but with treenode class that holds the tree, and node class
that holds only the data. i hope it's not too much to ask. thank you very much for your help!
0
Comment
Question by:liorliat
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 4
13 Comments
 

Author Comment

by:liorliat
ID: 1178784
Edited text of question
0
 

Author Comment

by:liorliat
ID: 1178785
node class has 3 node pointers - left , right , parent.
0
 

Author Comment

by:liorliat
ID: 1178786
node class has 3 node pointers - left , right , parent.
0
[Live Webinar] The Cloud Skills Gap

As Cloud technologies come of age, business leaders grapple with the impact it has on their team's skills and the gap associated with the use of a cloud platform.

Join experts from 451 Research and Concerto Cloud Services on July 27th where we will examine fact and fiction.

 

Author Comment

by:liorliat
ID: 1178787
node class has 3 node pointers - left , right , parent.
0
 
LVL 1

Accepted Solution

by:
Booth882 earned 100 total points
ID: 1178788
do you want to remove a node from anywhere or one from the outermost branches (ie one with no Right or Left pointer)?  to remove one from the outermost branches you could say

node * CurrentNode = trunk // trunk is the base node in the tree

while(CurrentNode->Left || CurrentNode->Right)
{
    if(CurrentNode->Left)
        CurrentNode = CurrentNode->Left;
    else
        CurrentNode = CurrentNode->Right;
}

if(CurrentNode->ParentNode->Left == CurrentNode)
    CurrentNode->ParentNode->Left = 0;
else
    CurrentNode->ParentNode->Right = 0;

EraseNode(CurrentNode);

I think this is what you want to do, because to remove a node from an arbitrary location would take the removal of all the nodes it is a parent and grandparent etc to.  you could do that though too.  all it would take would be to take the above algorithm and repeat until the node you want to remove has no branches coming from it, ie

if(RemovalNode->Right == 0 && RemovalNode->Left == 0)

and instead of using the trunk of the whole tree to initialize CurrentNode use the node you want to remove, like this

void RemoveNode(node * RemovalNode)
{
    while(RemovalNode->Right != 0 && RemovalNode->Left != 0)
    {
        node * CurrentNode = RemovalNode;

        while(CurrentNode->Left || CurrentNode->Right)
        {
            if(CurrentNode->Left)
                CurrentNode = CurrentNode->Left;
            else
                CurrentNode = CurrentNode->Right;
        }

        if(CurrentNode->ParentNode->Left == CurrentNode)
            CurrentNode->ParentNode->Left = 0;
        else
            CurrentNode->ParentNode->Right = 0;

        EraseNode(CurrentNode); // however you are doing this,
                                // possibly delete CurrentNode;?
    }
}

that should do it.  let me know if you have any questions.
0
 
LVL 1

Expert Comment

by:Booth882
ID: 1178789
hey liorliat?  you still there?...
0
 

Author Comment

by:liorliat
ID: 1178790
thank you very much for you'r answer.
i'm afraid that it was'nt exactly what i ment. i want to delete an arbitrary node from the tree, and keep the property of a binary tree.
by now, i wrote the  functions to do the next:
1) find the predecessor of a node,by sending the pointer of the node.
2) find the successor.
3) find a node in the tree by getting its data (an integer in my qestion case)
4) find min and max from a node (functions gets the pointer to the node)
all functions returns a pointer to the node found , or NULL .
now,using all this function,and having right left and parent pointer in each node,how do i delete an arbitrary node,keeping the property of a binary tree still?
0
 

Author Comment

by:liorliat
ID: 1178791
thank you very much for you'r answer.
i'm afraid that it was'nt exactly what i ment. i want to delete an arbitrary node from the tree, and keep the property of a binary tree.
by now, i wrote the  functions to do the next:
1) find the predecessor of a node,by sending the pointer of the node.
2) find the successor.
3) find a node in the tree by getting its data (an integer in my qestion case)
4) find min and max from a node (functions gets the pointer to the node)
all functions returns a pointer to the node found , or NULL .
now,using all this function,and having right left and parent pointer in each node,how do i delete an arbitrary node,keeping the property of a binary tree still?
0
 

Author Comment

by:liorliat
ID: 1178792
thank you very much for you'r answer.
i'm afraid that it was'nt exactly what i ment. i want to delete an arbitrary node from the tree, and keep the property of a binary tree.
by now, i wrote the  functions to do the next:
1) find the predecessor of a node,by sending the pointer of the node.
2) find the successor.
3) find a node in the tree by getting its data (an integer in my qestion case)
4) find min and max from a node (functions gets the pointer to the node)
all functions returns a pointer to the node found , or NULL .
now,using all this function,and having right left and parent pointer in each node,how do i delete an arbitrary node,keeping the property of a binary tree still?(sorry th bother you again...)    :-)              
0
 
LVL 1

Expert Comment

by:Booth882
ID: 1178793
what do you mean by keep the property of a binary tree?  

could you clarify what you mean by 'property'?
0
 

Author Comment

by:liorliat
ID: 1178794
by saying "keep the property of binary tree" i mean that the tree would still be sorted as a binary tree after the removal of an arbitrary node.
please give me an answer as soon as possible,  i need it  7 hours from now !!!
thanks again.

0
 
LVL 1

Expert Comment

by:Booth882
ID: 1178795
the second algorithm I showed you would still keep it sorted as a binary tree.  it is necessary to delete all the nodes that spring from the removed node because otherwise you would have no connection to them and their memory would be lost, but after you are done it will still be a binary tree.  give it a try, it works! :)
0
 

Author Comment

by:liorliat
ID: 1178796
thanks a lot fo your quick response.
soory about the misunderstanding.
you SAVED me!
i'll be talking to you when i'll have another  ?  
it probebly wont take long...  :)
0

Featured Post

How Blockchain Is Impacting Every Industry

Blockchain expert Alex Tapscott talks to Acronis VP Frank Jablonski about this revolutionary technology and how it's making inroads into other industries and facets of everyday life.

Question has a verified solution.

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

Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
All of the resources available today make learning a new digital media easier than ever-- if you know where to begin. This is a clear, simple guide to a few of the basic digital art mediums and how to begin learning them on your own.
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…

623 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