3

整数を読み取り、昇順で出力するメイン関数を定義する必要があります。

    For example, if the input contains

       12
       4
       19
       6

   the program should output

       4
       6
       12
       19

ただし、これを行うにはツリーを使用する必要があります。私は 2 つの機能insertavlを使用することができdeleteavl、自由に使用できます。それらの定義は次のようになります... http://ideone.com/8dwlU 基本的に、deleteavl が呼び出されると、ノードが削除され、それに応じてツリーのバランスが取り直されます ... 興味のある構造があれば、 http: //ideone.com/にあります。キュールゲ。

私はこれまでにこれを得ました：

int main (void) {
   int number;
   struct node *t = NULL;
   while (1 == scanf("%d",&number)) {     
          t = insertavl(t, number);              
   }
   while (t != NULL){
      printf("%d\n",t->data);
      t = deleteavl(t, t->data);    
   }    
}

しかし、これはそれらを昇順で印刷しません。何か提案は役に立ちますか？前もって感謝します！

4

1 に答える 1

4

ヒント: BSTでの順序通りのトラバーサルは、要素を昇順で繰り返します。

AVL ツリーは BST の特定の実装であるため、ここでも適用されます。

編集:説明 - BST での順序通りのトラバーサルのこのプロパティが正しいのはなぜですか?

in-order trvaersal では、左側のサブツリーのすべてのノードにアクセスした後、各ノードに [print] アクセスします。BST ではルートが左側のサブツリーのすべてのノードよりも大きいため、これが必要でした。

また、順序通りのトラバーサルでは、右側のサブツリー内のすべての要素にアクセスする前に各ノードにアクセスします。これも BST であるため、これはまさに私たちが望んでいることです。

(*)注: これは正式な証明ではなく、なぜそうなのかを直感的に説明したものです。

于 2012-03-04T18:45:34.063 に答える