二元樹的遞歸遍歷在返回語句不終止

Question

我創建了一個用莫爾斯碼填充二叉樹的類。向左移動表示DOT，向右移動表示DASH。直到我正在編寫一個將字母轉換爲莫爾斯碼字符串的編碼方法之前，一切都很順利。該方法應遞歸地執行樹的前序遍歷（沿途創建莫爾斯碼的字符串），直到找到目標字符，然後返回該字符串。

但是，由於某種原因，我的遞歸不會終止在我的基本情況下。它只是繼續運行整個遍歷。我附上我的代碼，以下面的方法。爲什麼if語句中的return語句不觸發並結束方法？

對不起，如果這是不明確的，但我不想爲我的整個項目發佈300行代碼，當有人比我更容易發現問題時。

感謝所有幫助

//wrapper class 
    //@parameter character is the character to be encoded 
    //@return return the morse code as a string corresponding to the character 

    public String encode(char character){ 

     return encode(morseTree, character, ""); 


    } 


    //@Parameters tree is the binary tree is the tree to be searched, 
    //element is the target character trying to be foudn, s is the string being used to build the morse code 
    //@return returns the morse code that corresponds to the element being checked 

    public String encode(BinaryTree<Character> tree, char target, String s){ 


     if(tree.getData() == target){ //if the data at the current tree is equal to the target element 
      //return the string that is holding the morse code pattern for this current traversal 
      return s; 
     }else{ 
      if(tree.getLeftSubtree() != null){ 
        //Traverse the left side, add a DOT to the end of a string to change the morse code 
        encode(tree.getLeftSubtree(), target, s + DOT); 
      } 

      if(tree.getRightSubtree() != null){ 
        //Traverse the left side, add a DOT to the end of a string to change the morse code 
        encode(tree.getRightSubtree(), target, s + DASH); 
      } 
     } 

     //The code should never get this far! 
     return s; 
    } 

Answer 1

你在else塊調用不返回 - 他們也許應該像這樣：

if (tree.getLeftSubtree() != null) { 
    // Traverse the left side, add a DOT to the end of a string to 
    // change the morse code 
    return encode(tree.getLeftSubtree(), target, s + DOT); 
} 

if (tree.getRightSubtree() != null) { 
    // Traverse the left side, add a DOT to the end of a string to 
    // change the morse code 
    return encode(tree.getRightSubtree(), target, s + DASH); 
} 

但是，你想，如果既要發生什麼左側和右側的子樹是空的？如果他們都是非空，你想要返回什麼？

請注意，僅僅因爲您的基本呼叫已經返回，只會返回單個呼叫 - 並非堆棧中的所有其他呼叫。遞增不替換與新的通話的堆棧幀 - 它只是增加另一個堆棧幀。從新的堆棧框架返回只是讓你回到你身邊。

---

是的，我知道尾遞歸。儘管如此，我們不要混淆視聽。