二元树的递归遍历在返回语句不终止

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); 
} 

但是，你想，如果既要发生什么左侧和右侧的子树是空的？如果他们都是非空，你想要返回什么？

请注意，仅仅因为您的基本呼叫已经返回，只会返回单个呼叫 - 并非堆栈中的所有其他呼叫。递增不替换与新的通话的堆栈帧 - 它只是增加另一个堆栈帧。从新的堆栈框架返回只是让你回到你身边。

---

是的，我知道尾递归。尽管如此，我们不要混淆视听。