Hi everyone,
I am working with a binary tree, and I am having a bit of trouble
visuallizing what needs to happen when I am trying to
delete a node that has two children. (no child node and one child node were
trivial).
Does anyone know the solution to this problem?
void CTree::Delete(C Person *&pPerson)
{
if (pPerson->pLeft == NULL && pPerson->pRight == NULL)
{
delete pPerson;
pPerson = NULL;
}
else if (pPerson->pLeft == NULL)
{
CPerson *pTemp = pPerson;
pPerson = pPerson->pRight;
delete pTemp;
}
else if (pPerson->pRight == NULL)
{
CPerson *pTemp = pPerson;
pPerson = pPerson->pLeft;
delete pTemp;
}
else //if the right and left are not null!?!?
{
}
} 8 3124
One thing I forgot to mention is: The solution that I have in my head is to
replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.
"Jimmy" <adfj;fd@dafj;d lf.sds> wrote... I am working with a binary tree, and I am having a bit of trouble visuallizing what needs to happen when I am trying to delete a node that has two children. (no child node and one child node
were trivial).
Does anyone know the solution to this problem?
I think you need to find a leaf that is between the left and the right
nodes and move it into the "deleted" node. void CTree::Delete(C Person *&pPerson) { if (pPerson->pLeft == NULL && pPerson->pRight == NULL) { delete pPerson; pPerson = NULL; } else if (pPerson->pLeft == NULL) { CPerson *pTemp = pPerson; pPerson = pPerson->pRight; delete pTemp; } else if (pPerson->pRight == NULL) { CPerson *pTemp = pPerson; pPerson = pPerson->pLeft; delete pTemp; } else //if the right and left are not null!?!? {
// this is a bit more complicated.
// you need to search the left and right for a leaf node
// that is smaller than right and greater than left
// then prune that leaf and stick the value in *this.
} }
I may be mistaken, of course. That's all off the top of my head.
Victor
"Jimmy" <adfj;fd@dafj;d lf.sds> wrote... One thing I forgot to mention is: The solution that I have in my head is
to replace the the node that is begin deleted with the left most node of it's right child. But not sure if that will work in all cases.
It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place :-)
Victor
"Victor Bazarov" <v.********@com Acast.net> wrote in message
news:kDJzb.4190 70$HS4.3341389@ attbi_s01... "Jimmy" <adfj;fd@dafj;d lf.sds> wrote... One thing I forgot to mention is: The solution that I have in my head is to replace the the node that is begin deleted with the left most node of
it's right child. But not sure if that will work in all cases.
It probably will. The leftmost [leaf] node of the right child is (a) greater than the current node (otherwise it would be in the left child) and (b) the smallest in the right subtree (otherwise it would not be the leftmost). So, with the current node gone, it's the primary candidate for its place :-)
Victor
What about a case like this
10
/ \
2 19
/ \ / \
1 4 14 20
\
15
if you try to delete 10, and replace it with the left most node of it's
right node (which is 14). what will happen to 15?
Ali R.
"Ali R." wrote: "Victor Bazarov" <v.********@com Acast.net> wrote in message news:kDJzb.4190 70$HS4.3341389@ attbi_s01... "Jimmy" <adfj;fd@dafj;d lf.sds> wrote... One thing I forgot to mention is: The solution that I have in my head is to replace the the node that is begin deleted with the left most node of it's right child. But not sure if that will work in all cases.
It probably will. The leftmost [leaf] node of the right child is (a) greater than the current node (otherwise it would be in the left child) and (b) the smallest in the right subtree (otherwise it would not be the leftmost). So, with the current node gone, it's the primary candidate for its place :-)
Victor
What about a case like this
10 / \ 2 19 / \ / \ 1 4 14 20 \ 15 if you try to delete 10, and replace it with the left most node of it's right node (which is 14). what will happen to 15?
Is this question addressed to the OP (you want to make him think
about some cases), or are you asking for yourself?
If first, I apologize for interfering.
else scroll down a little bit
15 has to be reconnected to 20 (if the leftmost child of
the right subtree has a right child on its own, then this
child will replace that leftmost child).
--
Karl Heinz Buchegger kb******@gascad .at
"Karl Heinz Buchegger" <kb******@gasca d.at> wrote in message
news:3F******** *******@gascad. at... "Ali R." wrote: "Victor Bazarov" <v.********@com Acast.net> wrote in message news:kDJzb.4190 70$HS4.3341389@ attbi_s01... "Jimmy" <adfj;fd@dafj;d lf.sds> wrote... > One thing I forgot to mention is: The solution that I have in my
head is to > replace the the node that is begin deleted with the left most node
of it's > right child. But not sure if that will work in all cases.
It probably will. The leftmost [leaf] node of the right child is (a) greater than the current node (otherwise it would be in the left child) and (b) the smallest in the right subtree (otherwise it would not be the leftmost). So, with the current node gone, it's the primary candidate for its place :-)
Victor
What about a case like this
10 / \ 2 19 / \ / \ 1 4 14 20 \ 15 if you try to delete 10, and replace it with the left most node of it's right node (which is 14). what will happen to 15?
Is this question addressed to the OP (you want to make him think about some cases), or are you asking for yourself?
If first, I apologize for interfering. else scroll down a little bit
No Apology need! :)
I was the one butting in to begin with.
I was thinking about a solutions but couldn't seem to find a good one. It's
been 15 years since I have looked at a binary tree. The cumulative solution
from this thread seem to involve alot of IF statements. I was just picking
Victor's brain there.
Ali R.
"Ali R." <no****@nospam. com> wrote... "Victor Bazarov" <v.********@com Acast.net> wrote in message news:kDJzb.4190 70$HS4.3341389@ attbi_s01... "Jimmy" <adfj;fd@dafj;d lf.sds> wrote... One thing I forgot to mention is: The solution that I have in my head
is to replace the the node that is begin deleted with the left most node of it's right child. But not sure if that will work in all cases.
It probably will. The leftmost [leaf] node of the right child is (a) greater than the current node (otherwise it would be in the left child) and (b) the smallest in the right subtree (otherwise it would not be the leftmost). So, with the current node gone, it's the primary candidate for its place :-)
Victor
What about a case like this
10 / \ 2 19 / \ / \ 1 4 14 20 \ 15 if you try to delete 10, and replace it with the left most node of it's right node (which is 14). what will happen to 15?
Deletion of a node is not a one shot operation. Since '15' is hanging
off the '14', and '14' is the one being deleted, then '15' should take
its place, I believe.
Victor
Victor Bazarov wrote: "Jimmy" <adfj;fd@dafj;d lf.sds> wrote...
One thing I forgot to mention is: The solution that I have in my head is
to
replace the the node that is begin deleted with the left most node of it's right child. But not sure if that will work in all cases.
It probably will. The leftmost [leaf] node of the right child is (a) greater than the current node (otherwise it would be in the left child) and (b) the smallest in the right subtree (otherwise it would not be the leftmost). So, with the current node gone, it's the primary candidate for its place :-)
Victor
Ahh, the binary tree; balance and symmetry.
One could also seek out the rightmost leaf node of the left subtree
of the victim node. I'm talking about the victim's predecessor when
traversing in LNR order.
I guess whether to replace the victim node with its predecessor or
successor is a design choice.
--
Thomas Matthews
C++ newsgroup welcome message: http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq: http://www.raos.demon.uk/acllc-c++/faq.html
Other sites: http://www.josuttis.com -- C++ STL Library book This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: JoeAley2003 |
last post by:
Hi all...
I need an example of a
RemoveNodeFromBTree(Data or Pointer);
function or even an alghoritm will help.
Will i need to rearrange the tree after this procedure?
|
by: A |
last post by:
Hi,
I'm trying to solve the 3rd and final case in deleting a node from a binary
tree. That is, deleting a node that has two subtrees. If someone out there
who knows about this problem as they have done it before or is currently
doing something similar then please give me some links with code.
Regards,
dfgf
|
by: Saradhi |
last post by:
Hi All,
Here I am facing a performance problem with the TreeView Node renaming.
I am displaying a hierarchy Data in a treeview in my Windows C# Application.
My tree view represents an hierarchical view of Parent Nodes and projects where in a projectnode can be added to any ParentNode and hence we may have a project node added to 100 Parent nodes.
In this one, I have an operation of Renaming a Project Node. So whenever I am doing the...
|
by: mathon |
last post by:
Hello,
im currently implementing a binary search tree means, that a greater
number than root will be added as right child and a less number as left
child. My insert function looks currently like this:
template <class Item>
void bag<Item>::insert(const Item& entry)
// Header file used: bintree.h
|
by: raylopez99 |
last post by:
What's the best way of implementing a multi-node tree in C++? What I'm
trying to do is traverse a tree of possible chess moves given an intial
position (at the root of the tree). Since every chess position has
around 30 moves, it would mean every node of the tree would have 30
branches (on average), which in turn themselves would average about 30
branches each.
I can think of a variety of ways of implementing this, including a
series...
| |
by: tina chatterjee |
last post by:
i have implemented binary tree insertion and deletion using my on coding.
but it was not a tough job till i got confused while deleting a node having both left and right child.I am unable to understand what should be done if such a node is deleted.
Anyone who could help me out.
|
by: yogi_bear_79 |
last post by:
I am enrolled in distance learning class, this amounts to self taught.
I have a book and that is about it. below is my assingment. The book
doesn't prove useful for examples, and I haven't had much look on the
web. I am not asking someone to do it for me, but a nudge in the
correct direction, a website anything!
Write a function to generate an N-node random binary search tree with
distinct keys L through N. What is the running...
|
by: sophia |
last post by:
Dear all,
How efficient is the binary tree node deletion method given here:-
http://s297.photobucket.com/albums/mm220/sophiaagnes/
is there any better method for deleting nodes in a binary tree ?
|
by: slizorn |
last post by:
hi guys,
i need to make a tree traversal algorithm that would help me search the tree..
creating a method to search a tree to find the position of node and to return its pointer value
basically i need to read in a text file... shown below
H
H,E,L
E,B,F
B,A,C
A,null,null
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |