バイナリ検索ツリーソート

Question

私は既に作成したバイナリ検索ツリーの助けを借りていくつかのデータを並べ替えたいです。 私は、次の例のコードが動作します..しかし、これがどのように動作するのか理解できません。 データベースにレコードが存在しない場合はb = 0と戻ります。これは明らかです。 bが存在する場合は、左ノードに戻り、b-> left == NULLになるまで関数を何度も呼び出します。正しく取得できますか？ しかし、とき、それはそれは、印刷をdoesntの機能を実行しますが、関数の先頭から再び開始したとき、私は何を得るのため、..

void display_ordered_email(struct BST_node *b) 
{ 
    if (b==0)   
     return;    
    display_ordered_email(b->left); 
    printf("Name : %s\n", b->data->name); 
    printf("Address : %s\n", b->data->address); 
    printf("Email : %s\n", b->data->email); 
    printf("\n"); 
    display_ordered_email(b->right); 
} 

このINORDERトラバーサルまたはその他の方法か、データを印刷しませんか

Answer 1

この単純なツリーを考えてみましょう。 display_ordered_emailを再帰的に順にノードを印刷することになっているbを印刷しなければならないとき、あなた自身に尋ねることができることを考えると

b 
/\ 
a c 

。答えはa（左側）を訪問して印刷した後で、c（右側）を訪問して印刷する前に、bを印刷する必要があります。

void display_ordered_email(struct BST_node *b) 
{ 
    if (b==0)   
     return;    
    display_ordered_email(b->left); 
    /* ... print the node */ 
    display_ordered_email(b->right); 
} 

これはあなたのルーチンがどのように構成されているかを正確に示しています。

Answer 2

これは、再帰を使用した予約注文トラバーサルです。左のサブツリーで作業が完了すると、そのサブツリーのルートとそれに続く右のサブツリーが出力されます。約8ノードのツリーで試してみてください。

Answer 3

左下まで移動して0を押すと、1つのノードに戻り、return文の後にそのノードのコードが続行されます。これは、そのコードを出力し、正しいノードで試すことを意味します。正しいノードがない場合はそれだけを返し、そうでない場合は正しいノードを出力します。両方の作業が完了したら、1つのレベルをバックアップし、そこにあるすべてのものを印刷して、それが持つ可能性のあるブランチの正しいブランチをチェックします。

最初はかなり混乱していますが、それを描くと分かりやすくなります。