was ist wohl mit dieser aufgabenstellung gemeint?

Dill

es soll ein binärer sortierbaum erstellt werden. soweit klar

aber dann:

- niveauweis ausgabe des baums (soll wohl heissen ebene für ebene)
- ausgabe in symmetrischer ordnung (kein plan)

danke schonmal

RTC

Weiß es zwar auch nicht genau, aber vom logischen Textverständnis her:

-niveauweise: denke auch, Ebene für Ebene. Also, gehe rekursiv bis in eine jeweilige Ebene, dann die nächste Ebene, bis alle Knoten ausgegeben sind.
-symmetrisch: meine Vermutung ist, dass du den Baum umgestalten musst. Es gibt ja immer einen Anfangsknoten, von dem alle Knoten ausgehen, dieser Knoten liegt aber kaum in der Mitte des Baumes. Symmetrisch heißt für mich, dass du von dem mittleren Baumelement ausgehst und von da aus dann die einzelnen Knoten ausgibst (vielleicht auch wieder ebenenweise, sonst würde das mit der Symmetrie vielleicht nicht hinhauen). Was musst du denn machen? Die Elemente ausgeben oder den Baum grafisch darstellen? Realisierungen hierfür könnte ich mir schon vorstellen, aber teil uns mal deine Ideen mit.

P.S.: Falls du es dann genau wissen solltest, bitte posten. Interessiert mich auch ein wenig

Dill

erstmal kurz was dazu wie der baum entsteht:

es werden nacheinander integers eingegeben, der erste ist die wurzel.
*Plinks zeigt etwa immer nur auf kleinere werte
*Prechts halt auf größere

versteh ich dich jetzt so richtig:

ich suche mir das element das gleich viele "kleinere" wie "größere" hat
nehme das als wurzel und baue den baum neu auf ...

würd sich ja mit der aufgabenstellung decken, nur erschliesst sich mir der sinn nicht so recht (und ich kann nicht behaupten, dass wir sinnfreie aufgaben gestellt kriegen. evtl. ist so eine reorganisation sinnvoll, da aus einem baum in grenzfällen ja eine liste werden kann ?!

ich mache das natürlich NICHT grafisch, steht nicht in der aufgabenstellung!

elise

habe ein wenig rumrecherchiert.. und denke, symmetrische ordnung ist einfach nur ein anderer begriff für inorder...

laufe den baum inorder durch.

Dill

aber der baum ist ja nicht geordnet ...
wie soll ich da einfach in order ausgeben ...?

elise

hi...

ich glaube, inorder ist dir kein begriff
http://www.informatik.uni-leipzig.de/ifi/lehre/Heyer2000/ADKapitel08/tsld002.htm

du kannst einen baum entweder preorder, postorder oder inorder ausgeben..

und inorder ist m.E. synonym für symmetrische ordnung

Dill

"Inorder : traversiere linken Teilbaum, besuche Wurzel, traversiere rechten Teilbaum
Inorder heißt auch symmetrische Ordnung."

super, danke!
dann ist das ja easy

Bashar

ebenenweise Traversierung heißt auch "level order", also viel spaß beim googlen

Dill

so, bin fertig.
hier der code, zum staunen und meckern

#include <stdio.h>
#include <stdlib.h>
#include <conio.h> //schon gewusst, dass das spanisch für F**** äh weibliches, primäres geschlechtsteil ist?

typedef struct TTN{              
   int Key;
   struct TTN *left, *right;
}TTN; // Type of TreeNode 

int Insert(int Key, struct TTN **Anchor);
void printInOrder(struct TTN *P);
void printLevelOrder(struct TTN *P, int niveau);

int main(void){

    int Key;
    short menu;
    struct TTN *Anchor = NULL; //Tree-Anchor, PHelpMe

    do {
        printf("\n  >>>");
        printf("\n   (1) insert");
        printf("\n   (2) print (inorder)");
        printf("\n   (3) print (levelorder)");
        printf("\n   (9) end");
        printf("\n  > ");

        fflush(stdout);
        menu = getch(); printf("%c\n", menu);

        switch (menu) {
            case '1':
                printf("\nKey: "); scanf("%d", &Key); rewind(stdin);
                Insert(Key, &Anchor);
                break;
            case '2':
                printf("\nprinting ... (in order)\n");
                printInOrder(Anchor);
                printf("\n\n");
                break;
            case '3':
                printf("\nprinting ... (level order)\n");
                printLevelOrder(Anchor, 0);
                printf("\n\n");
        } /*switch*/
    } while (menu != '9');
    return 0;
}

int Insert(int Key, struct TTN **Anchor){

    struct TTN **PP, *PH;

    if ((PH=(struct TTN *)malloc(sizeof(struct TTN))) == NULL) return 1;

    PH->Key=Key;
    PH->left=NULL;
    PH->right=NULL;
    PP=Anchor;

    while (*PP != NULL) {
        if (Key < (*PP)->Key) PP=&((*PP)->left);
        else PP=&((*PP)->right);
    }

    *PP=PH;
    return 0;
}

void printInOrder(struct TTN *P) { /* trav. recursive inorder (symm. order) */

    if (P != NULL) {
        printInOrder(P->left);         

            printf("[%5d] <-- ", P->left ? P->left->Key : 0);
            printf("[[%5d]]", P->Key);         
            printf(" --> [%5d] \n", P->right ? P->right->Key : 0);

        printInOrder(P->right);        
    } 
}

void printLevelOrder(struct TTN *P, int niveau){

    int I;

    if (P != NULL) {
        printLevelOrder(P->right, niveau + 1);
        for (I = 0; I < niveau; I++) printf("    ") 
            ;
        printf("[%d]\n", P->Key);
        printLevelOrder(P->left, niveau + 1);
    } 
}

RTC

[code]typedef struct TTN{...}TTN;[/code]

Macht man das nicht "typedef struct {...} TTN;"?

Bashar

Nö. Man könnte einwenden, dass der Typ TTN nirgends verwendet wird.

BTW find ich die Ausgabe reichlich seltsam. Wieso wird bei der Inorder immer noch der linke und rechte Kindknoten ausgegeben? Wieso machst du bei Levelorder so nen komischen Trick anstatt richtig?

Dill

Original erstellt von Bashar:
**Nö. Man könnte einwenden, dass der Typ TTN nirgends verwendet wird.
**

ja, gibt eine warnung
**
BTW find ich die Ausgabe reichlich seltsam. Wieso wird bei der Inorder immer noch der linke und rechte Kindknoten ausgegeben?
**
warum eigentlich nicht?
**
Wieso machst du bei Levelorder so nen komischen Trick anstatt richtig?
**

wieso trick?
was meinst du mit richtig?
hab sowas ja noch nie gemacht, weiss also nicht wie "richtig" geht, sach doch mal...

Bashar

angenommen, wir haben diesen Baum:

12
  2        15
1   3

Beim inorder-Durchlauf würde ich 1 2 3 12 15 ausgeben, beim levelorder-Durchlauf 12 2 15 1 3. Einfach inorder Rückwärts und dann um 90° gedreht sieht zwar irgendwie nach ebenenweise aus, ich glaub aber nicht dass das der Sinn der Sache sein soll

Dill

inorder Rückwärts und dann um 90° gedreht

wie meinen?
was soll 90° gedreht bedeuten? wie kann ich eine reihe von zahlen drehen?