Re: Binärer Baum in C?

Binärer Baum in C? (18 Beiträge, 18 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.

Primär glaub ich mal, dass Du uns irgendwas vorenthältst, weil root ned definiert ist.

Im Endeffekt geht's darum, dass Du die Selbstähnlichkeit so eines Baumes ausnutzen kannst. Zeichne Dir so 'nen Baum mal auf. Ich mein's ernst, Papier, Bleistift, zeichnen! So 3-4 Ebenen dürften reichen.

So. Als nächstes, vergiss für 'nen Moment C. Nix mehr an programmieren denken, jetzt wird's künstlerisch!

Jetzt schau Dir mal die Wurzel an (den Knoten ohne Vorgänger), und seine Nachfolger. Sprich, den ganzen Baum. So. Jetzt schau Dir den linken Nachfolger an, und seine Nachfolger. Du wirst feststellen, er ist dem ganzen Baum sehr ähnlich, nur "kleiner".

Weiters ist es von Vorteil, wenn Du Dir die Knoten von "innen" betrachtest. Also wennst so tust, als ob Du "im" Knoten die Ausgabe machst. Versuch's Dir vorzustellen. Nicht an Code denken! Vorstellen! Schau auf den 1. Knoten. Was müssen wir tun?

Nun, im Endeffekt nur 3 Schritte:

1. Wenn es einen linken Nachfolger gibt, sag diesem, er soll sich ausgeben.
2. Gib mich aus.
3. Wenn's einen rechten Nachfolger gibt, sag diesem, er soll sich ausgeben.

Die komische Formulierung "sag diesem..." hat folgenden Sinn: Dieser Nachfolger, bekommt ebenfalls wieder diesen 3-Punkte-Plan. Das heisst, er schaut nach ob er einen linken nachfolger hat... dieser wieder ... dieser wieder... usw.

Da wir zu Schritt 2 im 1. Knoten erst kommen, wenn wir mit Schritt 3 im linken Nachfolger fertig sind, wird dieser vor dem 1. Knoten ausgegeben. Das heisst, wir machen bei Schritt 2 in jeder Rekursion erst weiter, wenn der Nachfolger komplett fertig ist, dieser Knoten wird erst ausgegeben, wenn wir aus dem Nachfolger "zurückkommen".

Der Code selbst ist recht einfach (umschreiben für Deine Zwecke darfst ihn allerdings doch selbst

).

void printnode (node* current)
{
  if (current->left) printnode (current->left);
  OutputCurrentnode();
  if (current->right) printnode (current->right);
}

Was der Code macht sind im Wesentlichen die 3 Schritte, die ich oben besprochen hab.

Zuerst wird geprüft, ob's einen linken Nachfolger gibt (schau bitte auf Deiner Zeichnung von vorhin mit!). Falls ja, wird in diesen "gesprungen", und die Ausgaberoutine für diesen aufgerufen. Dieser macht das gleiche und prüft, ob er einen linken Nachfolger hat, dieser wieder, und wieder... Es ist WESENTLICH anzumerken, dass im Ur-Knoten, und in jedem seiner linken Nachfolger, die wir anspringen, inzwischen GAR NIX passiert, da wird derzeit nix ausgegeben und gar nix gemacht bis wir wieder "zurück" sind!

Wenn wir dann irgendwann einen Knoten finden, der keinen linken Nachfolger hat passiert in der 1. Zeile nix und wir kommen zur 2. IN DIESEM KNOTEN. Da wird dann der Inhalt ausgegeben. Dann kommen wir zur 3. Zeile, und wenn's einen rechten Nachfolger gibt, wird das Spiel mit diesem wiederholt. Gibt's keinen sind wir mit diesem Knoten fertig. Dann geht's zurück zum Vorgänger, dort kommen wir damit in die 2. Zeile (remember, wir haben vorher gesagt es passiert in diesem Knoten nix bis wir aus dem Nachfolger zurück sind, der "steht" immer noch, wie alle seine Vorgänger, auf der 1. Zeile und wartet darauf, dass die Nachfolger fertig werden).

Dort passiert nun das gleiche, Output, rechter Nachfolger, usw.

Das Spiel setzt sich nun durch den ganzen Baum durch fort, bis alle Knoten ausgegeben sind.

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

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)

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

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