Re(3): Binärer Baum in C?

Binärer Baum in C? (18 Beiträge, 17 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Ich komm einfach mit dem Binären Baum nicht zusammen.
Also die Struktur sieht wie folgt aus:

struct _BTREE
{
char key[100]; //Key
LIST *list; //einfach verkettete Liste
struct _BTREE *left; //linker Sohn
struct _BTREE *right;//rechter Sohn
};

typedef struct _BTREE BTNODE;
typedef BTNODE *BTNODEP;

Jetzt soll ich eine Funktion implementieren, die die einzelnen Knoten des Baums ausgibt:

void BTPrint(**root)

Ich hab nun keine Ahnung wie ich mit dem Zeiger auf Zeiger umgehen soll, vielleicht kann mir hier jemand etwas weiterhelfen.

Re: Binärer Baum in C? (Fly am 23.04.2002, 02:28:46)

Re(2): Binärer Baum in C? (Jack Sniper am 23.04.2002, 09:08:35)

Re(3): Binärer Baum in C? (Fly am 23.04.2002, 10:02:03)

Re(4): Binärer Baum in C? (le am 23.04.2002, 12:19:37)

Re(5): Binärer Baum in C? (Fly am 23.04.2002, 13:03:01)

Re(2): Binärer Baum in C? (MikeM am 23.04.2002, 09:54:45)

Re(3): Binärer Baum in C? (Fly am 23.04.2002, 10:02:42)

Re(4): Binärer Baum in C? (MikeM am 23.04.2002, 10:07:26)

Re(2): Binärer Baum in C? (Edi am 23.04.2002, 10:24:19)

Du greifst auf die Knoten gar nicht direkt zu. Du nutzt die Ähnlichkeit aus.

Der Trick dabei ist, dass Du die Funktion aus sich selbst heraus nochmal aufrufst, mit den Nachfolgern. So Marke "divide and conquer". Die Wurzel hat keinen Schimmer, wie weit sie nach unten gehen wird, sie gibt einfach die "Kontrolle" mal an den linken und mal an den rechten Nachfolger weiter (dazwischen wird ihr Inhalt ausgegeben). Diese Nachfolger machen nun genau das gleiche. Jeder Knoten "sieht" dabei nur sich selbst und (so vorhanden) seine Nachfolger.

Aufgerufen wird die Rekursion, indem Du als Parameter für den neuen Aufruf entweder den linken (also root->left) oder den rechten (root->right) übergibst. Dass der Parameter root heissen soll is' dabei vielleicht ein klein wenig verwirrend, weil es wird ein einziges Mal (nämlich beim Aktivieren von "aussen") mit dem Wurzelknoten aufgerufen. Alle anderen Aufrufe passieren von innerhalb der RDPrint Funktion! Der Wurzelknoten ruft's also mit seinem linken Nachfolger auf, der macht das gleiche, und der wieder, und der wieder... bis es keinen linken Nachfolger mehr gibt. Wieviele Aufrufe da passieren und wie lang's dauert, wieviele Nachfolger es da gibt und wo die hängen, das "weiss" der Wurzelknoten nicht. Er wartet einfach darauf, dass die Ausführung wieder zu ihm zurückkommt.

Nehmen wir an, wir haben folgenden Tree:

     4
  2     6
1  3  5 7

Wir rufen's mit der Wurzel (4) auf. Diese sieht, sie hat einen linken Nachfolger (2) und ruft die Funktion mit diesem auf. 2 merkt, er hat einen linken Nachfolger (1) und ruft die Funktion mit diesem auf. 1 hat keinen Linken nachfolger (1. Zeile fertig).

1 wird ausgegeben. (2. Zeile fertig)

1 merkt er hat keinen rechten Nachfolger (3. Zeile fertig). Damit ist die Funktion in 1 fertig und die Ausführung kehrt zurück zu 2. 2 ist jetzt mit der 1. Zeile des Codes fertig.

2 wird ausgegeben

2 merkt, es hat einen rechten Nachfolger (3) und führt die Funktion mit diesem als parameter aus. 3 geht's jetzt so wie 1 (d.h. kein linker Nachfolger, Ausgabe, kein rechter Nachfolger, Funktion fertig).

Danach geht die Ausführung zurück an 2. 2 ist mit der 3. Zeile jetzt auch fertig (das war die Übergabe an 3) und beendet seine Funktion. Damit geht die Ausführung zurück an 4. 4 ist jetzt mit seiner 1. Zeile fertig.

4 wird ausgegeben

Danach wiederholt sich das ganze Spiel mit dem rechten Ast des Baumes (ich erspar mir jetzt die Tipperei).

Warum Du's als ** definieren willst versteh' ich nun nicht ganz, 'n Zeiger würde reichen. Ich komm' auch noch nicht dahinter, wozu die verkette Liste da drin nutzen soll.

Shadows can be made real
if you kill in their name.

Re(4): Binärer Baum in C? (Edi am 23.04.2002, 11:42:56)

Re(5): Binärer Baum in C? (Fly am 23.04.2002, 11:55:35)

Re(6): Binärer Baum in C? (Jack Sniper am 23.04.2002, 12:23:28)

Re(7): Binärer Baum in C? (le am 23.04.2002, 12:32:18)

Re(6): Binärer Baum in C? (Edi am 23.04.2002, 12:29:12)

Re(7): Binärer Baum in C? (Fly am 23.04.2002, 13:14:05)

Re(8): Binärer Baum in C? (Edi am 23.04.2002, 15:21:44)

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung