C++遞歸函數返回值

作爲一項家庭作業，我正在實現一個二叉搜索樹，並且正在做一些搜索某些數據的位置（以便能夠稍後修改/刪除它）的部分，這裏是我的一塊代碼：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

與根指向1.當我想尋找元素3，我期待得到的指針3，但每一次這個函數返回根本身。然後我想也許這與foo的第一個實例沒有返回值有關，所以我將search(x, pos->right)更改爲return search(x, pos->right)，對於左側則同樣如此，此時一切正常。這使我困惑，我試着做了幾運行具有以下虛擬函數只是爲了瞭解那會返回

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

我雖然沒有規定什麼情況下返回if語句是假的，它劇照工程和輸出1.我想也許foo(0)剛剛回到無論foo(1)在遞歸返回，檢查我嘗試這樣：

int boo() { 
    return 1; 
} 

int foo() { 
    boo(); 
}

，並呼籲foo()，這就造成了「富必須返回值」的錯誤，很明顯將boo()更改爲return boo()固定它。所以我的問題是爲什麼第一個案件輸出根？爲什麼第二個案例甚至有效？

來源

2016-12-29 user3002386

如果沒有'return'語句返回某個不同於'void'的函數的末尾，就會導致未定義的行爲。你幸運沒有[鼻子守護神]（http://www.urbandictionary.com/define.php?term=nasal%20demons）！ –

@DietmarKühl感謝參考鼻子deamons :) –

拿起並返回一個'node *'似乎很奇怪，但是你對於搜索的遞歸調用的結果並沒有做任何事情（因此沒有有效的'return'）。 – crashmstr

你有這裏的問題是，你不宣傳你的遞歸調用的返回值回原來的調用者。事實上，當這些調用返回時，該值將被丟棄。

更糟糕的是，在情況下，你不覺得你的對手，你作爲書面未能返回任何東西，這是不確定的行爲。獲得根節點的事實更多的是編譯器或當前內存佈局的怪癖，而不是定義的結果。

正如@Mike指出的那樣，對於二叉樹，根據搜索值是否大於或小於當前節點的值，您應該只在搜索中遍歷一個子樹。傳統上，左邊的樹保存的值小於當前節點，而右邊的樹保留的值更大。

來源

2016-12-29 20:34:06

另外他們不應該需要在bst中搜索這兩個子樹 – Mike

C++遞歸函數返回值

回答

相關問題