liorliat
asked on
binary tree
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!
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!
ASKER
node class has 3 node pointers - left , right , parent.
ASKER
node class has 3 node pointers - left , right , parent.
ASKER
node class has 3 node pointers - left , right , parent.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
hey liorliat? you still there?...
ASKER
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?
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?
ASKER
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?
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?
ASKER
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...) :-)
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...) :-)
what do you mean by keep the property of a binary tree?
could you clarify what you mean by 'property'?
could you clarify what you mean by 'property'?
ASKER
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.
please give me an answer as soon as possible, i need it 7 hours from now !!!
thanks again.
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! :)
ASKER
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... :)
soory about the misunderstanding.
you SAVED me!
i'll be talking to you when i'll have another ?
it probebly wont take long... :)
ASKER