4. was ist wohl mit dieser aufgabenstellung gemeint?

was ist wohl mit dieser aufgabenstellung gemeint?

  • D

    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!

    0

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

    laufe den baum inorder durch.

    0
  • D

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

    0

  • 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

    0
  • D

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

    super, danke!
    dann ist das ja easy 🙂

    0
  • B

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

    0
  • D

    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);
    } 
}
    0
  • R

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

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

    0
  • B

    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?

    0
  • D

    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...

    0
  • B

    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 😉

    0
  • D

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

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

    0
Anmelden zum Antworten