バイナリツリーの順序通りのトラバース

Question

バイナリツリーを順番にトラバースし、そのアイテムを順番に整数の配列に入れる関数を作成しようとしました。このコードには悪い習慣がいくつか含まれていますしかし、私は実際に私の関数が目的の整数配列を作成しない理由は実際にはなぜですか。私の関数は、bstのすべての項目を保持するために必要なサイズを見つけることができる場合でも、これらの項目を適切に置くことはできません。ルートのみ。

ここで主要な機能を置く理由はありません。なぜなら、私はその配列の要素を印刷するためだけに使うからです。

TreeNodeのMy関数、グローバルバリアブル、およびtypedefブロック。

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. のmalloc（）サイズサイズ*のはsizeof（int型）の配列を（それはです

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

   をそして、それはそれだ：あなたが必要 のみ割り当てが）、そして、あなたは、単純な再帰を行うことができます0

にインデックスを初期化します！