Löschen im binären Suchbaum



  • Guten Morgen,
    ich habe folgendes Problem und hoffe, dass ihr mir dabei helfen könnt 😃

    Ich muss einen binären Suchbaum erstellen, indem man diverse Funktionen nutzen kann. Abgesehen vom Löschen des kompletten Baumes oder einzlener Knoten ist mir dies auch gelungen. Ich habe viele verschiedene Funktionen zum Löschen ausprobiert und im Wesentlichen trat immer eins von 2 Problem auf: 1. Das Programm stürzt ab oder 2. es wird nicht gelöscht.

    Für das Löschen des kompletten Baumes hatte ich folgenden relativ intuitiven Ansatz:

    void DeleteTree(Node *root){
    	if(root==0){
    		return;
    	}
    	DeleteTree(root->left);
    	DeleteTree(root->right);
    	delete root;
    }
    

    und auch einen etwas komplizierteren:

    void DeleteTree(Node *root){
    		if((root->left == 0) && (root->right==0)){ //hat der knoten keine Kinder, lösche ihn
    			delete root;
    
    		}
    		else if((root->right!=0) && (root-> left ==0)){ // hat er nur rechts ein Kind
    			Node* cache=root;
    			root=root->left;
    			delete cache;  //lösche ihn und setze dieses Kind an seine Stelle
    			DeleteTree(root);
    		}
    		else if(root->right!=0 && root->left ==0){ //hat er nur links ein Kind
    					Node* cache=root;
    					root=root->left;
    					delete cache; //lösche ihn und setze Kind an seine Stelle
    					DeleteTree(root);
    				}
    		else if(root-> right !=0 && root->left !=0){
    			Node* cache;
    			if (root-> left -> right != 0){
    			cache=root->left->right;
    				while (cache->right !=0){
    					cache=cache->right;
    				}
    				cache->right=root->right;
    			}else{
    				root->left->right= root->right;
    			}
    
    			cache=root;
    			root=root->left;
    			delete cache;
    			DeleteTree(root);
    		}
    
    }
    

    Vor allem bei dem intuiviem Ansatz hätte ich erwartet, dass er funktioniert. Könnt ihr mir vielleicht sagen, wo mein Fehler liegt?

    Gruß Stephan



  • Woher weißt du, dass nichts gelöscht wurde?



  • Hallo,

    ich musste unter anderem eine Funktion schreiben, die den Baum sortiert ausgibt. Und wenn das Programm nicht abgestürzt ist, war die Ausgabe vor und nach dem Löschen identisch.

    Gruß Stephan



  • Die Bits sind nach dem Löschen ja auch noch alle vorhanden. Wenn du sie illegalerweise betrachtest, kann sich das Programm verhalten, als wäre noch alles da. Es kann aber auch abstürzen.



  • Das heißt also, dass die Funktion so richtig ist und der Fehler nur durch den Versuch auftritt, das ganze nochmal auszugeben obwohl eigentlich nichts mehr da ist?



  • Schreib doch einfach mal einen Destruktor für Node und gib da irgendwas aus. Wenn da alle Items/Daten beim Löschen was ausgeben machst du bei der Ausgabe deines Bauems was (gehörig) falsch.



  • Ich habe das mit der Ausgabe getestet. Es wurden alle im Baum befindlichen Elemente ausgegeben. Also hat mein erster Code zumindest mal alle Elemente durchlaufen.

    Anschließend habe ich dem nun "leeren" Baum neue Werte hinzugefügt und diesen dann ausgeben lassen. Die neue Ausgabe bestand nur aus den neuen Werten, also scheint delete zu funktionieren und der Fehler kam tatsächlich durch den Versuch einen quasi nicht existierenden Baum ausgeben zu wollen.

    Nun gilt es nurnoch die Funktion RemoveNode zum Laufen zu bringen. Ich werde dies nun nochmal selbst versuchen und mich dann ggf. nochmals melden, falls ich es nicht hinbekomme.

    Ich danke euch beiden vielmals! 😃

    Gruß Stephan


Log in to reply