用C++遞歸返回一個值

我有一個採訪，我無法回答這個問題。你有一個二叉樹，你使用in_order把所有的節點放到一個數組中，並且返回數組大小的值。我被告知我不能使用輔助函數，併爲數組計數器添加int i = 0。我不得不使用的遞歸函數標題是。用C++遞歸返回一個值

 In_order(Struct_Node * node, int *array){ 

     }

因爲這是我寫的In_order。

 if(node){ 
     In_order(node->left, array);

//這條線就是我應該添加元素和返回值，但我不知道如何做到這一點。這是我的一週，我需要了解這個代碼如何工作的原因比代碼更多。

 in_order(node->right,array); 
     }

我沒有真正寫出我在兩個In_order語句之間寫的內容，但是我寫的是錯誤的。

來源

2011-10-20 Aaron

如果你要返回數組長度，那麼你的函數定義應該是'unsigned int in_order（Struct_Node * node，int * array）{'。 – 2011-10-20 22:25:17

看看[維基百科]（http://en.wikipedia.org/wiki/Tree_traversal#Sample_implementations）中的樹的順序遍歷。將存儲數據替換爲數組。說'* array = node-> data; array ++;' – 2011-10-20 22:26:59

猜測所有丟失的細節，我認爲像你會做什麼：

int In_order(Struct_Node * node, int *array){ 

    int count = 0; 
    if (node->left) { 
    count += In_order(node->left, array); 
    } 
    array[count++] = node->data; // whatever it is you're storing 
    if (node->right) { 
    count += In_order(node->right, array+count); 
    } 
    return count; 
}

關鍵的一點是你通過一個更新指針RHS遞歸調用以及返回值是1 + LHS return + RHS return

如果您不能使用int作爲一個計數器（這是愚蠢的，因爲確實這是迄今爲止表達它的最清晰的方式），你可以這樣做：

int In_order(Struct_Node * node, const int *array){ 
    int *tptr = array; 

    if (node->left) { 
    tptr += In_order(node->left, array); 
    } 
    *tptr++ = node->data; // whatever it is you're storing 
    if (node->right) { 
    tptr += In_order(node->right, tptr); 
    } 

    return tptr-array; 
}

如果你婉假設有點瘋狂並避免除了函數參數之外的任何本地函數，您可以將返回類型更改爲數組當前工作結束的指針（實際上也是數組的大小），並執行以下操作：

int *In_order(const Struct_Node * const node, int * const result) { 
    return !node ? result : 
      In_order(node->right, &(*In_order(node->left, result) = node->value)+1); 
}

雖然相當誠實太可怕了代碼（我敢肯定，這是明確的甚至沒有100％！），我真的希望他們不是在尋找這樣的一個解決方案！

來源

2011-10-20 22:27:38 Flexo

我不確定'count'變量是否允許，剩下的就是我會回答的。 – Patrick

有序是樹遍歷的一種方法;您按順序（因此名稱）從左到右移動節點。

所以對於插入部分，你會插入所有當前節點的左節點，插入當前節點，然後將所有的權利的節點。

在撥打in_order(node->right,array)之後，您將返回您的值（您的問題描述不清楚您應該返回的內容）。

來源

2011-10-20 22:27:55

對於序遍歷：

做左子樹的序遍歷（如果有的話）。
訪問當前節點。
對右子樹（如果有的話）進行序列遍歷。

在你的情況下，「visit」意味着將當前節點添加到列表中，並撞上計數器。個人來說，我會使用一個向量（然後在最後如果需要，轉換/複製到數組）。你可以在一個「start」函數中創建它，然後調用遞歸函數，或者在調用者中創建它。無論哪種方式，您都會在每次調用中傳遞一個引用。最後，你有一個節點值數組和計數。否則，你最終不得不經過一次樹來計算元素，並第二次收集它們。（或者你可以傳遞一個引用或指針指向一個指針，所以你可以根據需要重新分配，但這會變得很難看。無論哪種方式，我都不會相信調用者知道數組的大小給你 - 這是你的工作知道/計算你的樹的大小：P）

來源

2011-10-20 22:29:48 cHao

用C++遞歸返回一個值

回答

相關問題