4. Ebenen im binären Baum

Ebenen im binären Baum

  • C

    Hallo alle miteinander.

    Ich hab da folgendes Problem:
    Ich habe ein kleines Programm aus dem Buch "Programmieren in C" von Kernighan / Ritchie verwendet um einen binären Baum zu erzeugen. Dieser Baum erstellt eine Sortierung eines eingegebenen Textes in Baumform.
    Nun möchte ich aber die Wörter sortiert nach Ebenen ausgeben, das Bedeutet das "Startwort" (Root) zuerst auf Ebene 1.
    Dann die beiden (wenn vorhanden) Söhne auf Ebene 2.
    Die (wenn vorhanden) nun folgenden Söhne auf Ebene 3 usw.
    In einer kleinen graphischen Struktur sähe das wie folgt aus:
    ---
    --- ---
    --- --- --- --- etc.
    Ich habe aber momentan keine Ahnung, wie ich das Programm ändern soll, dass es die Knoten nach Ebenen sortiert. Alle von mir im Kopf durchgespielten Versuche über eine Auswertung der Nullzeiger oder einer mitlaufenden Variable (dann hätte ich ja nur die Knotenanzahl) etc. führen mich nicht zur Lösung :o(

    Wäre schön, wenn mir einer von euch weiterhelfen könnte !

    0
  • B

    Das Verfahren nennt sich level-order Traversierung, füttere mal google damit. Ich hab auf die Schnelle nur ne Java-Lösung gefunden ...

    0
  • C

    Thx soweit, hat mir aber leider immer noch net weitergeholfen...

    Okay, ich weiss nun, dass ich meinen binären Suchbaum (so wie das Programm jetzt aussieht) zuerst in InOrder Traversierung erstellen muss und dann in LevelOrder Traversierung nochmal duchlesen muss um die Worte dann in Ebenen zu printen, leider wird auf sämtlichen Dokus die ich finde nur erklärt, was eine LevelOrder Traversierung ist und wie man einen Baum auf diese Art liest, nicht wie man den Baum so ausgibt.

    Ich komme halt nicht auf die Bedingung die das Prog braucht um zu erkennen, dass eine bestimmte Anzahl der Knoten auf einer Ebene liegt.

    Meine Idee momentan ist, den Knoten eine weitere Bedingung hinzuzufügen (strucht tnode *level;) und dann brauch bei Erstellung eines neuen Knotens dieser einen Eintrag in level (würde also so aussehen: p->level = ...), aber ich weiss nicht, wie die benötigte Bedingung für "..." aussehen muss.
    Wenn ich dafür eine Variable nehme (i) und sie jedesmal inkrementiere, erhalte ich auch nur die Anzahl der Knoten. Setze ich sie auf einen festen Wert, wird sie jedesmal mit diesem Wert zugewiesen, ist also auch unbrauchbar.
    Meine Idee wäre dann, zu prüfen, ob der jeweilige Knoten einen Vater hat (also muss es eine Ebene drüber geben) und ob er Söhne hat. Hat er Söhne, muss also noch eine Ebene folgen; sind die beiden Zeiger Nullzeiger (p->left = p->right = NULL;), hat der Knoten keine Söhne mehr und ist damit ein Blatt. Damit hätte ich die unterste Ebene und muss dann nur noch solange nach oben laufen, bis der letzte Knoten keinen Vater mehr hat, also root ist.
    Aber ich krieg das dort oben in Worten beschriebene nicht in Sourcecode umgesetzt! 😞
    Hach, jeder Anfang ist schwer...

    0
  • C

    Ich habs jetzt gelöst. Wenn's interessiert, poste ich gerne mal den Quelltext.

    0
  • V

    poste mal pseudocode oder die kommentare oder so, daß ich deinen algo verstehe.

    0
  • C

    Pseudocode?!
    Algo?!

    #include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <dialogs.h>
#include <events.h>
#include <ctype.h>

#include "Baum.h"

#define MAXWORD 10000
#define BUFSIZE 10000

struct tnode {              /* der Knoten eines Baumes */
    char *word;             /* zeigt auf den Text */
    int count;              /* Haeufigkeit */
    int level;              /* Ebene */
    struct tnode *left;     /* linker Nachkomme */
    struct tnode *right;    /* rechter Nachkomme */
};
struct tnode *addtree(struct tnode *, char *, int level);
struct tnode *talloc(void);
void treeprint(struct tnode *);
void *malloc(size_t size);
int Baum_zeichnen(void);
int getword(char *, int);
int getch(void);
int comment(void);
int bufp = 0;               /* naechste freie Position in buf */
void ungetch(int);
char buf[BUFSIZE];
char *strdup(char *);
short   itemHit;

DialogPtr   myDlg;

/* Hauptteil */
main()
{
    WindowPtr   myWindowPtr = 0;
    Boolean     tracks = 0;

    MaxApplZone();
    InitGraf(&qd.thePort);
    InitFonts();
    InitWindows();
    InitMenus();
    TEInit();
    InitDialogs(nil);

myDlg = GetNewDialog(PaletteID, nil, myWindowPtr -1);
SetDialogTracksCursor(myDlg, tracks);
SetDialogCancelItem(myDlg, Cancel);
if (myDlg != 0)
        do {
            ModalDialog(0, &itemHit);
            switch (itemHit) {
            case Baum: Baum_zeichnen();
                break;
            }
        }
    while (itemHit != cancel);
    DisposeDialog(myDlg);
return 0;
}

/* Haeufigkeit von Worten zaehlen */
int Baum_zeichnen(void)
{
    struct tnode *root;
    int level = 0;
    char word[MAXWORD];

    root = NULL;
    while (getword(word, MAXWORD) != '$')
        if (isalpha(word[0]))
            root = addtree(root, word, level);
    treeprint(root);
    return 0;
}

/* addtree: einen Knoten mit w bei oder nach p einfuegen */
struct tnode *addtree(struct tnode *p, char *w, int level)     /* Vaterebene uebernehmen */
{
    int cond;

    if (p == NULL) {                /* ein neues Wort */
        p = talloc();               /* neuen Knoten erzeugen */
        p->word = strdup(w);
        p->count = 1;
        p->level = level+1;     /* Ebene inkrementieren */
        p->left = p->right = NULL;
    } else if ((cond = strcmp(w, p->word)) == 0)
        p->count++;              /* Wort ist schon vorgekommen */    
    else if (cond < 0)               /* kleiner: links darunter */
        p->left = addtree(p->left, w, p->level);
    else                            /* groesser: rechts darunter */
        p->right = addtree(p->right, w, p->level);
    return p;
}

/* treeprint: Baum p sortiert ausgeben (Inorder) */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d \t%4d \t%s\n", p->count, p->level, p->word);
        treeprint(p->right);
    }
}

/* talloc: tnode erzeugen */
struct tnode *talloc(void)
{
    return (struct tnode *) malloc(sizeof(struct tnode));
}

/* strdup: Duplikat von String erzeugen */
char *strdup(char *s)           /* Duplikat von s erzeugen */
{
    char *p;

    p = (char *) malloc(strlen(s)+1);       /* +1 fuer '\0' */
    if (p != NULL)
        strcpy(p, s);
    return p;
}

/* getword: naechstes Wort oder Zeichen aus der Eingabe holen */
int getword(char *word, int lim)
{
    int c, d, comment(void), getch(void), tolower(int c);
    void ungetch(int);
    char *w = word; 

    while (isspace(c = getch()))
        ;
    if (c != '$') {
        c = tolower(c);
        *w++ = c;
    }
    if (isalpha(c) || c == '_' || c == '#') {
        for ( ; --lim > 0; w++)
            if (!isalnum(*w = getch()) && *w != '_') {
                ungetch(*w);
                break;
            }
    } else if (c == '\'' || c == '"') {
        for ( ; --lim > 0; w++)
            if ((*w = getch()) == '\\')
                *++w = getch();
            else if (*w == c) {
                w++;
                break;
            } else if (*w == '$')
                break;
    } else if (c == '/')
        if ((d = getch()) == '*')
            c = comment();
        else
            ungetch(d);
    *w = '\0';
    return c;
}

/* comment: Kommentar übergehen und / oder EOF liefern */
int comment(void)
{
    int c;

    while ((c = getch()) != '$')
        if (c == '*')
            if ((c = getch()) == '/')
                break;
            else
                ungetch(c);
    return c;
}

 int getch(void)                        /* naechstes (eventuell zurueckgestelltes) Zeichen holen */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c)                 /* Zeichen zurueckstellen */
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}
    0
  • V

    sorry, aber irgendwie überseh ich da, wie du den baum ebenenweise anzeigst.

    0
Anmelden zum Antworten