was ist wohl mit dieser aufgabenstellung gemeint?

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?