DVL zahlenwerte in Binärbaum übergeben



  • Hallo Leute,

    ich benötige eure Hilfe.
    Die Unterlagen die ich von der Uni erhalten habe sind keine Hilfe.

    Ich habe eine doppelt verkettete Liste erstellt und diese mit zufallszahlen befüllt.
    Nun soll ich diese Zahlenwerte in einen binären Baum geben. Also den binären Baum mit den Zahlen aus der DVL befüllen.

    Wie geht das?

    Ich habe im Netz nach einem gut erklärten Beispiel gesucht aber nichts brauchbares gefunden. Ich mache das zu ersten mal.

    SG



  • Zeig doch erstmal deinen Quellcode mit der doppelt verketteten Liste.
    Zudem wäre das Wissen vonnöten nach welchen Kriterien die Liste ( ein nächstes Element ), in einen binären Baum ( zwei nächste Elemente ) umgewandelt werden soll. Das sollte ja aus deinen Unterlagen hervorgehen.



  • Hallo,

    deine Frage ergibt keinen rechten Sinn. Wenn man einen binären Baum hat, ist es sehr einfach, ihn mit dem Inhalt einer doppelt-verketteten Liste zu füllen: Man durchläuft die Liste und fügt die Elemente dem Baum hinzu. Das ist um Größenordnungen einfacher als eine doppelt-verkettete Liste oder einen binären Baum zu implementieren. Deshalb denke ich, deine Frage ist eigentlich: Wie entwirft man einen binären Baum? (Und: geht es nicht eigentlich um einen binären Suchbaum?) Daher: Was weißt du denn über binäre Bäume?



  • Ich soll zuerst eine DVL erzeugen und mit Werten befüllen. Danach soll ein binär Baum erstellt werden und mit den Werten aus der DVL befüllt werden.

    Das habe ich mittlerweile hinbekommen.

    Nun habe ich aber beim einfügen der Elemente in die DVL folgenden Fehler, den ich nicht verstehe:

    Fehlermeldung:

    Ausgelöste Ausnahme: Lesezugriffsverletzung
    "head" war "nullptr".

    Hier der Code:

    void insertElement() { 
    
    	node* help = 0;
    	node* head = 0;
    
    	for (int i = 0; i < MAX; i++){
    
    		int number = (int)(rand() % (250 - 1 + 1) + 1); 
    
    		help = new node;
    		help->key = number;
    		help->next = head->next; // hier markiert er den Fehler;
    		help->prev = head;
    		head->next->prev = help;
    		head->next = help;
    	}
    }


  • @C91
    Head ist zu dem Zeitpunkt nullptr, daher darfst du nicht per -> auf irgendwelche Member von head zugreifen.



  • @C91: Du benötigst dafür eine Membervariable (sofern du eine Klasse benutzen willst/sollst) oder aber eine (wenn auch nicht empfohlen) globale Variable head, da sie ja der Kopf für alle einzufügenden Elemente ist.
    Und für die Funktion insertElement solltest du noch einen Parameter übergeben, an der das neue Element eingefügt werden soll (oder soll es immer am Anfang oder Ende der Liste)?

    PS: Warum hast du hier im Subforum C++/CLI mit .NET gepostet?



  • @Th69 darf ich dich bitten, das du mir das mal in meinem Beispiel zeigst?
    Ich blicke da gerade nicht ganz durch.

    PS: Das hier ist ja der C++ bereich, oder nicht?



  • Schau dir mal (besonders die Bilder in) Doppelt verkettete Listen in C an.

    Jetzt erst sehe ich, daß du ja in insertElement() mehrere Elemente (in der Schleife) hinzufügen willst - besser ist es das ersteinmal auf das Einfügen von einem Element (so wie die Funktion ja auch heißt) zu beschränken.
    Und eine weitere Funktion ruft dann diese Funktion in einer Schleife passend auf (mit entsprechenden Parametern).

    PS: Gestern war dieses Thema noch im falschen Subforum, aber das hat wohl ein Moderator inzwischen korrekt verschoben.



  • Also die Liste funktioniert schon mal.

    Nun habe ich beim ausgeben des Baumes ein Problem:

    Ausgelöste Ausnahme: Lesezugriffsverletzung
    "head" war "0xCDCDCDCD".
    

    Der Fehler entsteht in folgender Zeile:

    void display(node* head){   
      		
                if (head != z){
    		display(head->l); // Hier markiert er den Fehler.
    		cout << "Wert: " << head->key << "Wert: " << head->info << endl;
    		display(head->r);
    		}
    }


  • Vermutlich das gleiche Problem wie gestern: head ist nicht initialisiert. Du solltest dir angewöhnen, Zeiger auf Gültigkeit zu überprüfen, bevor du sie benutzt.
    Falls es einen Anwendungsfall gibt, in dem ein Zeiger nullptr sein darf:

    void f( SomeType* some_pointer )
    {
       if( some_pointer )
       {
          some_pointer->something();
       }
    }
    

    falls nicht:

    void f( SomeType* some_pointer )
    {
        std::assert( some_pointer, "some_pointer in f() must not be null" );
        some_pointer->something();
    }
    


  • Head und z habe ich ganz oben:

    node* z, *head;


  • @C91
    Und welchen Wert haben sie?



  • Ändert nichts am Fehler.



  • @C91
    Wer seine Zeiger nicht initialisiert darf sich auch nicht wundern, dass sie einem um die Ohren fliegen. Der MSVC Compiler ist sogar noch so nett und initialisiert sie mit 0xCDCDCDCD, damit man sieht, dass man selbst die Initialisierung vergessen hat.



  • Ich habe beide initialisiert:

    node* head = NULL;
    node* z = NULL;
    

    ??



  • Und wie sieht dein Quelltext jetzt aus?



  • head und z ist global:

    node* head = NULL;
    node* z = NULL;
    

    In der Main habe rufe ich die Funktion auf und übergebe head:

    displayTree(head);
    

    Hier nochmal die Funktion:

    void display(node* head){   
    	
            if (head != z){
    	display(head->l); // Fehler ist noch immer hier.
    	cout << "Wert: " << head->key << "Wert: " << head->info << endl;
    	display(head->r);
            }
    }


  • Welchen Wert haben head und z an der Stelle?
    Btw:
    Der Ausschnitt, den du zeigst, hilft nicht weiter. Erst schreibst du, dass du displayTree aufrufst und sagst dann, dass der Fehler in display auftritt. Wie ist da der Zusammenhang?



  • @DocShoe Ich habe es geändert, dait es lesbarer ist. Ist aber noch immer die gleiche Funktion.



  • @C91
    Du musst dir auch helfen lassen. Ich habe dir zwei konkrete Fragen gestellt, von denen du keine beantwortet hast. Stattdessen Quelltextauszüge, die doch irgendwie doch nicht das sind, was du tatsächlich versuchst.


Anmelden zum Antworten