Ausdruck in Binärbaum abbilden

[Schlaubi_Schlumpf]

Hi,

ich hab ein großes (jedenfalls für mich) Problem.

Ich will eine Formel z.B.: ((3*5)+4) in einen Binärbaum abbilden, in etwa so:

xxxxxx +

xxxxxx / \

xxxxx * x 4

xxxx / \

xxx 3 x 5

Programmiert in C.

Leider krieg ichs auch nach mehreren Versuch nicht hin, wohl zu wenig Ahnung? Muss ich das mit Rückzeigern machen?

Bitte helft!

:confused: xxxxxx

[Diablo999]

Willst du eine eingegebene Formel zerlegen?

Wenn ja würde diese Antwort wohl etwas länger werden...

Wenn nein:

Hier wie ein Baum in etwa aufgebaut ist

struct STree  

{

  STree* lpLeft;     // Verweis auf den linken Teilzweig

  STree* lpRight;   // Verweis auf den rechten Teilzweig

  char*   szData;   // Die Daten in diesem Zweig

}

Gruß

Diablo999

[nic_power]

Hallo,

Das wird so nicht funktionieren, probiers mal mit der folgenden Variante:

struct STree

{

  struct STree* lpLeft;     /* Verweis auf den linken Teilzweig */

  struct STree* lpRight;   /* Verweis auf den rechten Teilzweig */

  char*   szData;             /* Die Daten in diesem Zweig */

};

Falls Du einen Analyser/Parser bauen möchtest, solltest Du Dir mal die Tool-Kombination flex/bison anschauen. Die ist genau für diese Aufgaben gedacht, verhältnismäßig einfach zu Nutzen und arbeit praktisch perfekt mit C zusammen.

Nic

[Schlaubi_Schlumpf]

danke erstmal,

aber die Struktur ist klar, was ich nicht auf die Reihe kriege ist die vor- und rückspringerei zwischen den Ebenen, runter denke ich geht immer irgendwie vom anfang an bis der Zeiger NULL ist. Aber wie komm ich wieder hoch?

[nic_power]

Guter Punkt! In dem Du noch einen Zeiger auf den vorherigen Knoten einfügst:

struct STree* previous;

Nic

[Guybrush Threepwood]

@nic_power

ich weiß nicht ob`s am Compiler liegt, aber Diablo999 hat bei mir

bisher immer Funktioniert.

[Schlaubi_Schlumpf]

an nen Rückzeiger hatte ich auch schon mal gedacht, aber wie krieg ich den da rein?

Hat den niemand sowas schon mal gemacht? Wenn ich ja mal ein Beispielcode hätte würde mir sicher so einiges klarwerden, aber im Moment steht ich echt neben mir, ich begreife die Funktionsweise als Ganzes nicht.

[Diablo999]

Aus welchem Grund willst du überhaupt im Baum "zurück" laufen?

Im Normalfall wird doch immer der ganze Baum durchlaufen (mit Hilfe einer Rekursiven Funktion).

die Funktion könnte dann in etwa so aussehen:

void PrintTree(CTree* lpTree)

{

  // linken Ast schreiben

  if (lpTree->lpLeft) 

    PrintTree(lpTree->lpLeft);


  // den Knoten selbst

  cout << lpTree->szData;


  // rechten Teilzweig

  if (lpTree->lpRight) 

    PrintTree(lpTree->lpRight);

}

[nic_power]

Guten morgen,

@Guybrush:

Ein C++ Compiler kommt damit klar, allerdings war als Sprache C angegeben (und es sich um keinen gültigen C Code handelt).

Um den Baum nur von oben (Wurzel) nach unten zu durchlaufen, wird kein Zeiger auf das vorhergehende Element benötigt. Allerdings hast Du dann auch keine Möglichkeit, schrittweise zurückzugehen.

Nic

[Shadax]

Original geschrieben von Schlaubi_Schlumpf

Wenn ich ja mal ein Beispielcode hätte würde mir sicher so einiges klarwerden, aber im Moment steht ich echt neben mir, ich begreife die Funktionsweise als Ganzes nicht.

Was willst du eigentlich -genau- machen? Einen Baum -aufbauen- durch einen Parser oder den fertigen Baum -evaluieren-?

[gugelhupf]

Original geschrieben von Schlaubi_Schlumpf

Hi,

ich hab ein großes (jedenfalls für mich) Problem.

Ich will eine Formel z.B.: ((3*5)+4) in einen Binärbaum abbilden, in etwa so:

xxxxxx +

xxxxxx / \

xxxxx * x 4

xxxx / \

xxx 3 x 5

Programmiert in C.

Leider krieg ichs auch nach mehreren Versuch nicht hin, wohl zu wenig Ahnung? Muss ich das mit Rückzeigern machen?

Bitte helft!

:confused: xxxxxx

Hallo !

Deine Bitte ist etwas unpräzise. Du musst für Dich selber festlegen in welcher Durchlaufreihenfolge Du Daten ablegen möchtest.

Pre-, in-, oder Postorder. Erst wenn Du dadruch Deine Datenstruktur festgelegt hast ist an eine Implementierung zu denken.

PS: Einen Parser für solche Klammerausdrücke macht man i.d.R mit Stacks.