Трассировка в порядке в двоичном дереве

Question

Я попытался написать функцию для перемещения по двоичному дереву в порядке и поместить его элементы в массив целых чисел in-order.I знаю, что этот фрагмент кода содержит некоторые плохие методы но на самом деле я задаюсь вопросом, почему моя функция не создает цельный массив целых чисел. Например, даже если моя функция может найти размер, необходимый для хранения всех элементов bst, он не может правильно помещать эти элементы. Иногда он помещает только два узла, а иногда только корень.

Я не вижу причин, чтобы какая-либо главная функция здесь, так как я использовал бы ее только для печати элементов этого массива.

Моя функция, глобальный блок variabless и typedef для 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

Ой, вы делаете realloc() при каждом вызове функции. Realloc() является дорогостоящим и должен использоваться как можно меньше. Вы должны хранить размер дерева где-нибудь. Если вы не можете, вы можете перенести его в первый раз, чтобы подсчитать количество элементов.

Другое: ваш if/elseif/elseif/else бесполезен: вы всегда можете применить одно и то же обращение. Псевдокод, при условии, что для любого узла left->val < node->val < right->val:

1. получать размер дерева (если у вас его еще нет)
2. таНоса() массив размера размера * SizeOf (INT) (это только распределение вам нужно), инициализировать индекс 0

Затем вы можете сделать простую рекурсию:

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); 
} 

И это все!