Übungsaufgabe

Hallo wir sollen in einer Übungsaufgabe ein Programm um einige Stellen ergänzen.
Es handelt sich um einen Binären Suchbaum.

Von mir ergänzt wurden bisher ein Teil im Einfügen und im Ausgeben.

Es sollen 1000 Zufallswerte eingefügt und diese ausgegeben werden, wobei größere Werte zuerst ausgegeben werden sollen.

Nur muss irgendwo ein gr0ßer Fehler drin sein, denn das Programm hängt sich auf:
Wie gesagt der Fehler ist am wahrscheinlichsten in den Funktionen insert oder print

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct knoten
{
    knoten *links;
    knoten *rechts;
    int wert;
};

knoten *new_knoten(int wert)
{
    knoten *hilf;
    hilf = new knoten;

    if (hilf == NULL)
    {
        return hilf;
    }
    else
    {
        hilf -> links = NULL;
        hilf -> rechts = NULL;
        hilf -> wert = wert;
        return hilf;
    }
}

int insert_baum(knoten **wurzel, int wert)
{
// Der Baum ist noch leer
    if (*wurzel == NULL)
    {
        *wurzel = new_knoten(wert);
        if (*wurzel == NULL)
        {
            return 1;
        }
        return 0;
    }
    else if((wert > (*wurzel)->wert) && (*wurzel)->rechts == NULL)
    {
        (*wurzel)->rechts = new_knoten(wert);
    }
    else if((wert < (*wurzel)->wert) && (*wurzel)->links == NULL)
    {
        (*wurzel)->links = new_knoten(wert);
    }
    else
    {
        knoten** tmp = wurzel;
        if(wert > (*tmp)->wert)
        {
            insert_baum( &((*tmp)->rechts),wert);
        }
        else if(wert < (*tmp)->wert)
        {
            insert_baum( &((*tmp)->links), wert);
        }
    }
    return 0;
}

void print_baum(knoten *wurzel)
{
    if(wurzel == NULL)
    {
        cout << "Leerer Baum !" << endl;
    }
    else
    {
        while(wurzel->rechts != NULL)
        {
            print_baum(wurzel->rechts);
        }
        cout << wurzel->wert << endl;
        while(wurzel->links != NULL)
        {
            print_baum(wurzel->links);
        }
    }
}

int main()
{
    knoten *wurzel = NULL;
    srand(time(0));
    /* Funktion rand() gibt einen Zufallswert zurueck */
    for(int i= 0; i <10; i++)
    {
        insert_baum(&wurzel, rand()%100000);
    }
    print_baum(wurzel);
    return 1;
}

Es tut mir leid dass ich keine näheren Angeben machen kann bezüglich des Fehlers.

Nexus

seltsamer mensch schrieb:

Es tut mir leid dass ich keine näheren Angeben machen kann bezüglich des Fehlers.

Das tut uns auch leid. Kannst du denn nicht wenigstens sagen, wo sich das Programm aufhängt? Und vielleicht auch, wie (also Segmentation Fault, Heap Corruption, nichts passiert, Programm beendet sich sofort)?

Geh ansonsten mal mit dem Debugger durch und prüfe die Variablen.

Edit: Was mir gleich aufgefallen ist: Du prüfst nach deinen Anforderung mit new , ob der Zeiger Null ist. Sofern du nicht die nothrow -Version aufrufst (und das tust du hier nicht), wirft new bei Fehlschlag eine Exception vom Typ std::bad_alloc . Aber diese Fehlerabfrage kannst du momentan getrost vernachlässigen...

SWW13

while(wurzel->rechts != NULL)
        {
            print_baum(wurzel->rechts);
        }
        cout << wurzel->wert << endl;
        while(wurzel->links != NULL)
        {
            print_baum(wurzel->links);
        }

Solltes es bei unterem nicht wurzel->rechts statt links sein?

edit: Hmm... scheint doch richtig zu sein, ich war blind.

nocheinmitglied

void print_baum(knoten *wurzel)
{
    if(wurzel == NULL)
    {
        cout << "Leerer Baum !" << endl;
    }
    else
    {
        if(wurzel->rechts != NULL)
        {
            print_baum(wurzel->rechts);
        }
        cout << wurzel->wert << endl;
        if(wurzel->links != NULL)
        {
            print_baum(wurzel->links);
        }
    }
}

statt dem while ein if hin