Binärer Baum in C?

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

Das ist ja ganz nett.

Aber wer kann mir einen genauen Anwendungsfall sagen wo soetwas verwendet wird???

MfG Jack

Alles hat einen Grund.

Ich kann ihn nur nicht bei Windows finden.

Sortierhash. Du kannst nämlich in den Tree recht einfach und mit ziemlich geringen Aufwand einsortieren, und beim Auslesen bekommst auf die Art ganz automatisch 'ne sortierte Liste 'raus. Ausserdem ist's Suchen unglaublich einfach und schnell (binary search geht da drin ME am schnellsten. Und BS is' der schnellste Suchalgo).

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

Das Problem ist, daß diese simplen Bäume, die du hier hernimmst, leider degenerieren können und dann wieder erst eine linerare Liste vorliegt, die man in O(n) durchsuchen kann. Bessere Ansätze sind da z.B. AVL-Bäume oder B-Bäume. Aber für's grundsätzliche Verstehen sind diese simplen Binärbäume natürlich ideal.

Is' so scho' schwer genug zu verstehen für jemanden, der mit Rekursion und Bäumen noch wenig am Hut hat. Ausserdem geht's ja eben um einen Binärbaum.

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

Bitte schreib ein Buch - ich kaufs dir ab!
mfg
mm

'Kann man Vertrauen zu einer Frau haben, die einen selber zum Mann nimmt?'
Curt Goetz (1888-1960)

Lach ned, ich bin am Grübeln ob ich ned ein Begleitbuch zu AlgoDat schreiben soll, weil das Scriptum wird von Jahr zu Jahr mieser (und fehlerhafter).

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

War ja auch nicht als Scherz gedacht -> da gibts nix zum lachen

mfg
mm

Danke erst mal für die ausführliche Beschreibung, aber mir war schon klar wie ein Binärer Baum funktioniert, mein einziges Problem liegt darin, das meine ganzen Funktionen die ich schreiben soll die root nicht als Zeiger übergeben bekommen, sondern als Zeiger auf Zeiger. Das Codestück das du mir oben hingeschrieben hast hatte ich auch schon, nur mit anderer Traversierung.

Ich hab mir die root in meiner main so deklariert:
RNODE **root=NULL;

Danach versuche ich einen Knoten einzufügen:
void RDInsert(**root, key);

Dann soll die Funktion für die Ausgabe aufgerufen werden:
RDPrint(**root);

Mein Problem liegt beim ausprogrammieren der Funktionen, und zwar wie kann ich z.B. bei der Ausgabe über root auf die einzelnen Knoten zugreifen, oder müßte ich root überhaupt anders deklarieren?

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.

Das mit der Rukursion war mir eh auch schon klar, trotzdem danke für deine Ausführung.
Das Problem ist, ich brauch es für die Uni und hab leider die Funktionsschnittstellen so vorgegeben, würde es sonst auch nie mit ** machen, ist total umsonst und nur verwirrend. Ich komm aber einfach nicht dahinter wie ich mit ** auf die Knoten zugreifen kann, das mit der Liste wäre auch kein Problem wenn ich nur mal auf den Knoten selbst Zugriff hätte, bekomm entweder immer Warnings, oder er kompiliert es, gibt mir aber beim Ausführen des Programm irgendwelche kryptischen Zeichen aus.

Wahrscheinlich weil Du ins Nirvana greifst.

Aus welchem Buch isses denn, vielleicht kommen wir so dahinter.

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

Also ich versuchs mal:

typedef struct {
char key;
char irgendwas;
} TEST;

TEST erstes;
TEST *eintrag;
TEST **root;

eintrag = &erstes;

eintrag->key = 'dundidum';

root = &eintrag;

*root->key = 'neues dumdidum;

Hab ich das nun richtig interpretiert???

MfG Jack

Alles hat einen Grund.

Ich kann ihn nur nicht bei Windows finden.

(*root)->key = .......

so müßte es heißen.

Das hab ich mir eh auch gedacht, dass ich da irgendwo hingreife wo ich eigentlich gar nicht sein sollte.
Keine Ahnung ob es die Assistenten aus einem Buch haben, oder ob es ihren eigenen Gedanken entsprungen ist.

Hier kannst du dir mal meine kläglichen Versuche ansehen:

#include
#include
#include

#include "Liste.h"
#include "BTree.h"

void RDInit(RDNODE **root)
{
RDNODEP elem;

if (elem = (RDNODEP) malloc(sizeof(RDNODE)))
{
strcpy(elem->key, "root");
elem->list=NULL;
elem->left=NULL;
elem->right=NULL;

root = &elem;

printf("KEY: %s",elem->key);
}
}

void RDPrint(RDNODE **root)
{
RDNODEP elem;

elem=*root; //elem=&root;

//if (elem = (RDNODEP) malloc(sizeof(RDNODE)))
{
printf("KEY: %s",elem->key);

if(elem->left!=NULL)
RDPrint(&elem->left);
else if(elem->right!=NULL)
      RDPrint(&elem->right);
}
}

int main(void)
{
RDNODE **root;
char *key="ler";

root=NULL;

RDInit(root);
RDPrint(root);
                //RDInsertKey(root, key);

return 0;
}

Da bekomm ich beim ausführen wenn er RDPrint aufruft irgendwo einen Speicherverletzungsfehler.

Was ist RDNODE und RDNODEP?

Und in der Zeile
if (elem = (RDNODEP) malloc(sizeof(RDNODE)))
sollte == statt = stehen, vermute ich mal.

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

RDNODE sollte das BTNODE sein und RDNODEP ist BTNODEP, das hab ich umbenannt.
Das mit dem = müßte schon passen, der Block nach dem if wird nur betreten falls das anfordern des Speichers funktioniert, ansonsten nicht.

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