Je veux faire une traversée InOrder d'un BST et imprimer les nœuds. Je peux très bien imprimer l'arbre mais je n'arrive pas à obtenir la bonne numérotation.

Voici tout le code si quelqu'un veut compiler et essayer. Je vous remercie!

#include <time.h>
#include <stdlib.h>
#include <stdio.h>



struct Node_h {
    int start_addr;
    int size;

    struct Node_h* left;
    struct Node_h* right;
};

struct Node_h* newHoleNode(int st, int size) {
    struct Node_h* tmp = (struct Node_h*)malloc(sizeof(struct Node_h));
    tmp->start_addr = st;
    tmp->size = size;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}

int compare(struct Node_h* lhs, struct Node_h* rhs) {
    if(lhs->size != rhs->size) 
        return (lhs->size < rhs->size) ? -1 : 1;
    else if(lhs->start_addr == rhs->start_addr)
        return 0;
    else
        return (lhs->start_addr < rhs->start_addr) ? -1 : 1;
}

struct Node_h* insertHole(struct Node_h* cur, struct Node_h* add) {
    /* If the tree is empty, return a new node */
    if (cur == NULL) 
        return add;

    /* Otherwise, recur down the tree */
    if (compare(add, cur) == -1) {
        cur->left  = insertHole(cur->left, add);
    }
    else if(compare(add, cur) == 1) {
        cur->right = insertHole(cur->right, add);
    }

    /* return the (unchanged) node pointer */
    return cur;
}

int printHoles(struct Node_h* cur, int num) {
    if(cur == NULL) {
        return 0;
    }
    int t = 1 + num;
    t += printHoles(cur->left, num);
    printf("Hole %d: start location = %d, size = %d\n", t, cur->start_addr, cur->size);
    t += printHoles(cur->right, t);
    return t;
}

int main(int argc, char const *argv[]) {
    srand(time(NULL));   // should only be called once
    int pid = 0;
    struct Node_h* root = NULL;
    for (int i = 0; i < 1000; ++i) {
        int size = rand() % 10000;
        root = insertHole(root, newHoleNode(pid++, size));
    }
    printHoles(root, 0);
    return 0;
}

La numérotation est toujours soit des nombres +/- aléatoires massifs ou quelque chose comme ça. Aidez-moi!

Trou 1: emplacement de départ = 168, taille = 12

Trou 2: emplacement de départ = 665, taille = 12

Trou 4: emplacement de départ = 506, taille = 14

Trou 5: emplacement de départ = 908, taille = 30

Trou 11: emplacement de départ = 498, taille = 31

Trou 13: emplacement de départ = 340, taille = 38

Trou 14: emplacement de départ = 378, taille = 44

Trou 29: emplacement de départ = 303, taille = 54

Trou 30: emplacement de départ = 948, taille = 58

Trou 60: emplacement de départ = 503, taille = 70

2
D. Lamkin 30 nov. 2017 à 00:16

3 réponses

Meilleure réponse
// num is the number of nodes printed so far
// return the number of nodes printed so far
int printHoles(struct Node_h* cur, int num) {
    if(NULL == cur) {
        // last printed not changed
        return num;
    }
    num = printHoles(cur->left, num);
    printf("%d. size = %d\n", num + 1, cur->size);
    num = printHoles(cur->right, num + 1);
    return num;
}

Nous pouvons utiliser num pour suivre le nombre de nœuds imprimés jusqu'à présent. Sans utiliser t, cela devrait être plus clair et correct.

0
Daniel Kats 29 nov. 2017 à 21:49

Si vous réécrivez votre fonction comme

int printHoles(struct Node_h* cur, int num) {
    if(cur == NULL) {
        return num;
    }
    num = printHoles(cur->left, num) + 1;
    printf("Hole %d: start location = %d, size = %d\n", num, cur->start_addr, cur->size);
    num = printHoles(cur->right, num);
    return num;
}

Il doit suivre correctement le nombre de valeurs produites. Avant chaque appel printf(), le nombre est maintenant incrémenté de un et chaque appel récursif renvoie le nombre de valeurs produites jusqu'alors. Cela devrait faire ce que vous attendez.

0
Ctx 29 nov. 2017 à 22:01

Faites de num un pointeur et incrémentez directement après la visite du nœud. Avec la modification suivante, printHoles n'a plus besoin de renvoyer int:

void printHoles(struct Node_h* cur, int* num) {
  if (cur == NULL) {
    return;
  }
  printHoles(cur->left, num);
  printf("Hole %d: start location = %d, size = %d\n", *num, cur->start_addr, cur->size);
  (*num)++;
  printHoles(cur->right, num);
}
2
0x499602D2 29 nov. 2017 à 21:52
47561965