這個遞歸函數如何工作？

我無法弄清楚這是如何工作的，在我看來，一旦它得到答案，它不會對它做任何事情。這個遞歸函數如何工作？

Node* FindNode(Node *rootNode, int data) 
{ 
    if (!rootNode) 
    return NULL; 
    else 
    { 
    if (rootNode->data == data) 
    return rootNode; 
    else 
    { 
    FindNode(rootNode->left, data); 
    FindNode(rootNode->right, data); 
    } 
    } 
}

來源

2010-08-13 fauxCoder

它沒有。它應該是：

Node* FindNode(Node *rootNode, int data) { 
    if (!rootNode) { 
     return NULL; 
    }else if (rootNode->data == data) { 
     return rootNode; 
    }else if (data < rootNode->data) { 
     return FindNode(rootNode->left, data); 
    }else{ 
     return FindNode(rootNode->right, data); 
    } 
}

請注意額外的返回語句以及額外的else if子句。

編輯 —下面來總結註釋：您發佈的代碼可以工作的唯一理由是，如果編譯器的實現細節和測試數據的奇怪組合有利於你走到了一起。你應該明確解決問題，而不是讓代碼保持原樣。

來源

2010-08-13 04:43:16 David

那麼這就是我認爲...但它的工作原理，至少作爲一個更大的系統的一部分。 – fauxCoder 2010-08-13 04:44:16

由於編譯器對'return'語句的特定實現，返回值可能會在正確的位置結束;然而，你不能依賴它總是工作。另外，因爲你一直在搜索左右兩個子樹，所以在數組上使用BST沒有任何優勢。 – David 2010-08-13 04:46:09

@Shraptnel：不，它不。更準確地說，您在原始帖子中發佈的內容不起作用。很有可能你錯誤地複製了代碼。 – AnT 2010-08-13 04:46:41

這是假定FindNode返回第一個匹配。

Node* FindNode(Node *rootNode, int data) 
    { 
     Node *ptr; 
     if (!rootNode) 
      return NULL; 
     else 
     { 
      if (rootNode->data == data) 
      return rootNode; 
      else 
      { 
      ptr = NULL; 
      // if either left or right child is there 
      if(rootNode->left || rootNode->right) 
      { 
       // if not found in left subtree 
       if(NULL == (ptr = FindNode(rootNode->left, data))){ 
        // check in right subtree 
        ptr = FindNode(rootNode->right, data); 
       } 
      } 
      return ptr; 
      } 
     } 
    }

來源

2010-08-13 05:37:22 Chubsdad

這個遞歸函數如何工作？

回答

相關問題