Zwei Kinder löschen auf einem Binärbaum

Question

Ich habe eine Zuordnung, die manuell implementiert einen binären Baum mit Zeigern erfordert. Mein Baum funktioniert bis zum Löschen mit zwei Kindern. Was ich an diesem Punkt habe, ist, dass das richtige Element entfernt wird und das richtige Element an die Stelle des entfernten Elements gesetzt wird, aber ich bin am Ende mit dem linken Kind, das ein falscher Zeiger auf sich selbst ist und ich kann nicht herausfinden, wo ich Ich vermassle das. Ich möchte nicht den gesamten Code veröffentlichen, da dies eine Aufgabe ist, aber hier ist der Code, der das Problem hat. Wenn jemand mir bitte zeigen könnte, wo ich meinen Fehler mache, ohne den Code für mich zu machen, würde ich es wirklich schätzen. Auch der Baum, mit dem ich teste, sieht ungefähr so ​​aus und ich versuche, Knoten 3 zu entfernen. Knoten 2 ist an seinem Platz, wie es sein sollte, aber Knoten 2 links ist Knoten 2. Ich könnte sehen, wie ich das in diesem Fall umgehen kann, aber dann wäre es durcheinander, wenn der Ersatzknoten nicht das direkte Kind wäre, also sehe ich nicht, was ich falsch mache.

 5 
    / \ 
    3  7 
/\ /\ 
2 4 6 8 
/ 
3.5 

temp = delItem->left; 
back = delItem; 
while(temp->right != NULL) 
{ 
    back = temp; 
    temp = temp->right; 
} 

returnItem->m_dValue = delItem->m_dValue; 
returnItem->m_dWeight = delItem->m_dWeight; 
returnItem->m_iType = returnItem->m_iType; 
strcpy(returnItem->m_sDesc,delItem->m_sDesc); 
strcpy(returnItem->m_sItemName,delItem->m_sItemName); 
returnItem->left = delItem->left; 
returnItem->right = delItem->right; 
delItem = temp; 
delItem->left = returnItem->left; 
delItem->right = returnItem->right; 
returnItem->left = NULL; 
returnItem->right = NULL; 
     /*delItem->left = left; 
     delItem->right = right;*/ 
if(back == delItem) 
{ 
    back->left = temp->left; 
} 
else 
{ 
    back->right = temp->left; 
} 
temp->left = NULL; 
temp->right = NULL; 
delete temp; 
return returnItem; 

Vielen Dank für jede Hilfe, weil alles, was ich entweder spricht über die Theorie zu sehen, die ich ganz gut verstehen oder nicht annähernd das Problem zu beheben.

Jimmy

Answer 1

ein Element aus einem binären Baum Entfernen wird an vielen Orten über das Internet (und Lehrbücher) abgedeckt.

Ich würde vorschlagen, einen Blick auf diese Links, wie sie auch Codebeispiele bieten. Es ist sehr wichtig, dass Sie den Algorithmus verstehen, da es sich um eine Aufgabe handelt, von der erwartet wird, dass Sie sie kennen und in Zukunft getestet werden könnten.

Binary search tree. Removing a node

Binary Tree – Deleting a Node