Traversée en ordre dans un arbre binaire

Question

J'ai essayé d'écrire une fonction pour traverser un arbre binaire dans l'ordre et de mettre ses éléments à un tableau d'entiers, dans l'ordre. Je sais que ce morceau de code contient de mauvaises pratiques mais ce que je me demande c'est en fait pourquoi ma fonction ne crée pas de tableau entier cible. Par exemple, même si ma fonction peut trouver la taille nécessaire pour conserver tous les éléments de bst, elle ne peut pas mettre ces éléments correctement. seulement la racine.

Je ne vois aucune raison de mettre une fonction principale ici car je ne l'utiliserais que pour l'impression d'éléments de ce tableau.

Ma fonction, bloc global variabless et typedef pour un TreeNode;

typedef struct TreeNode{ 
    int val; 
    struct TreeNode *left; 
    struct TreeNode *right; 
} TreeNode; 

    int ctr = 0; 
    int size = 0; 

    int* inorder(TreeNode *root, int* arr){ 

     if(ctr==0) /*if first call to this function*/ 
      arr = malloc(size*sizeof(int)) ; 

     ctr++ ; 

     if(root){ 

      if(!root->left && !root->right){   
       arr = realloc(arr, ++size*sizeof(int)) ; 
       arr[size-1] = root->val ; 
      } 

      else if(!root->left&&root->right){ 
       arr = realloc(arr, ++size*sizeof(int)) ; 
       arr[size-1] = root->val ; 
       arr=inorder(root->right,arr) ; 
      } 
      else if(!root->right&&root->left){ 
       arr=inorder(root->left,arr) ; 
       arr = realloc(arr, ++size*sizeof(int)) ; 
       arr[size-1] = root->val ; 
      } 
      else{ 
       arr=inorder(root->left,arr) ; 
       arr = realloc(arr, ++size*sizeof(int)) ; 
       arr[size-1] = root->val ; 
       arr=inorder(root->right,arr) ; 

      } 

      return arr ; 
     } 
     else 
      return arr ; 
    } 

Answer 1

Ouch, vous faites un realloc() à chaque appel de fonction. Un realloc() est coûteux et devrait être utilisé le moins possible. Vous devriez garder la taille de l'arbre quelque part. Si vous ne le pouvez pas, vous pouvez le parcourir une première fois pour compter le nombre d'éléments. Autre chose: votre if/elseif/elseif/else est inutile: vous pouvez toujours appliquer le même traitement. Pseudocode, en supposant que pour tout nœud left->val < node->val < right->val:

1. obtenir la taille de l'arbre (si vous ne l'avez pas déjà)
2. malloc() un tableau de taille de taille * sizeof (int) (c'est la aLLOCATION vous aurez besoin), initialiser un indice à 0

Ensuite, vous pouvez faire un simple récursion:

void inorder(Treenode *root, int *array, int *index) { 
    if (!root) 
     return; 

    inorder(root->left, array, index); 
    array[*index] = root->val; 
    (*index)++; 
    inorder(root->right, array, index); 
} 

Et voilà!