2016-12-29 21 views
1

宿題として、私はバイナリ検索ツリーを実装しており、後で変更/削除できるように、データの位置を検索する部分を行っていました。コード:C++再帰関数戻り値

node*& bst::search(data& x, node*& pos) { 
    if (pos->get().num == x.num) { 
     return pos; 
    } 
    if (pos->right != NULL) search(x, pos->right); 
    if (pos->left != NULL) search(x, pos->left); 
} 

私はsearch(data_to_find, root)を呼び出します。私の例では、私は、このフォームの整数のツリーを持っていた:

1 
2 
    3 

私は要素3を検索したい1.ルートポインティングで、私は3へのポインタを取得することを期待しますが、毎回ましたこの関数はルート自体を返します。それから、値が返されないfooの最初のインスタンスと関係があったかもしれないと思ったので、search(x, pos->right)return search(x, pos->right)に変更しました。これは、私はちょうど私が文がfalseの場合、それは静止画の場合に返すために何を指定していないが、それは

int foo(int x = 0) { 
    if (x == 1) { 
     return x; 
    } 
    x++; 
    foo(x); 
} 

を返すかを理解するために、次のダミー関数をいくつかの実行を実行しようとしました、私は混乱して作られました作品や出力1.私は多分foo(0)はちょうど私はこの試みたことを確認するために、foo(1)は再帰で返さどんな返されたと思った:

int boo() { 
    return 1; 
} 

int foo() { 
    boo(); 
} 

をし、明らかに、「fooが値を返さなければなりません」エラーをもたらした、foo()と呼ばれますboo()return boo()を修正しました。 Sooo私の質問はなぜ最初のケースがrootを出力しているのですか?そして、なぜ2番目のケースも機能していますか?

+4

'return'ステートメントなしで' void'とは異なる何かを返す関数の終わりから流出することは、未定義の動作です。あなたは幸運にも[鼻のデーモン](http://www.urbandictionary.com/define.php?term=nasal%20demons)はありませんでした! –

+0

@DietmarKühlは鼻のdeamonsへの参照のためにありがとう:) –

+0

'node *&'を返すのは奇妙に思えますが、 'search'への再帰呼び出しの結果で何もしません有効な 'return'を持っていません)。 – crashmstr

答えて

3

問題は、再帰呼び出しの戻り値を元の呼び出し元に伝播しないことです。そのままでは、これらの呼び出しが戻ったときに値は破棄されます。

さらに悪いことに、一致するものが見つからない場合は、書かれたものが何も返されず、未定義の動作です。ルートノードを取得するという事実は、定義された結果ではなく、コンパイラや現在のメモリレイアウトのクルークです。

@Mikeによって指摘されているように、バイナリツリーの場合、検索値が現在のノードが保持する値より大きいか小さいかに基づいて、検索で1つのサブツリーを走査するだけでよい。従来、左のツリーは現在のノードよりも小さい値を保持し、右のツリーはより大きな値を保持します。

+1

また、BSTの両方のサブツリーを検索する必要はありません – Mike