這種遞歸是如何工作的？我如何讓它打印出根？

Question

所以我做了一個BST

private String toStringHelper(Node node) { 


      if (node == null) { 
       return ""; 
      } 
      if (node.left != null) { 
       System.out.println(node.left.value); 
       toStringHelper(node.left); 

      } 

      if (node.right != null) { 
       System.out.println(node.right.value); 
       toStringHelper(node.right); 

      } 


      return ""; 
     } 

我想用遞歸的實現。問題是它不會打印出我的根元素，否則它看起來很有效（編輯開始）。 當插入下列值100，-12，-13，-1,0，12，10，123，122，124，它返回它們以下列順序： -12 -13 -1 124這顯然不是有序的。 （編輯結束）

事情是，我不完全確定遞歸部分是如何工作的，我想解釋一下，這樣我也可以獲得打印出適當位置的根的方法。

Answer 1

它看起來像你通過它的開始節點，然後打印左，右子樹。你需要打印出來在節點的值作爲參數去的方法傳遞，然後調用該方法，該節點的左右孩子

private String toStringHelper(Node node) { 

     if (node == null) { 
      return ""; 
     } 
     //print the value of the current node 
     System.out.println(node.value); 
     if (node.left != null) { 
      //System.out.println(node.left.value); 
      toStringHelper(node.left); 

     } 

     if (node.right != null) { 
      //System.out.println(node.right.value); 
      toStringHelper(node.right); 

     } 


     return ""; 
    } 

編輯：移動打印語句空後根據OLE VV的更正檢查

Answer 2

儘管原始問題的答案非常簡單，並且已經被其他海報指出，但我想提供關於遞歸樹遍歷的更詳細的答案，也許這對未來的訪問者會有所幫助這篇文章。 樹遍歷有許多不同的方式，其中一些是「自然」遞歸，其中一些不是。 （有關更多詳細信息，請參閱wikipedia。）下面的代碼說明了基於OP中代碼的前/後/後順序深度優先搜索和廣度優先搜索。 由於遞歸（堆棧溢出）的實際限制，既深度優先和廣度優先應該與循環來實現，使用堆棧或隊列作爲底層數據結構，除非該實施是尾遞歸和平臺可以將其優化來一個循環，但Java編譯器不支持。 在下面的代碼中，我帶來了遞歸的例子，因爲關於遞歸的原始問題，而不是樹遍歷。

// depth first pre-order 
// root 
// left child 
// left child of left child 
// right child of left child 
// right child 
// left child of right child 
// right child of right child 
private String toStringHelperDepthFirst(Node node) { 
    if (node == null) { 
     return ""; 
    } 
    System.out.println(node.value); 
    toStringHelper(node.left); 
    toStringHelper(node.right); 
} 

// depth first in-order 
// left child of left child 
// left child 
// right child of left child 
// root 
// left child of right child 
// right child 
// right child of right child 
private String toStringHelperDepthFirst(Node node) { 
    if (node == null) { 
     return ""; 
    } 
    toStringHelper(node.left); 
    System.out.println(node.value); 
    toStringHelper(node.right); 
} 

// depth first post-order 
// left child of left child 
// right child of left child 
// left child 
// left child of right child 
// right child of right child 
// right child 
// root 
private String toStringHelperDepthFirst(Node node) { 
    if (node == null) { 
     return ""; 
    } 
    toStringHelper(node.left); 
    System.out.println(node.value); 
    toStringHelper(node.right); 
} 

// breadth-first 
// root 
// left child 
// right child 
// left child of left child 
// right child of left child 
// left child of right child 
// right child of right child 
private void toStringHelperBreadthFirst(Node node) { 
    if(node != null) { 
     Queue<Node> queue = new LinkedList<>(); 
     queue.add(node); 
     breadhFirst(queue); 
    } 
} 

private <E> void breadthFirst(Queue<E> queue) { 
    if(queue.isEmpty()) { 
     return; 
    } 
    Node node = queue.pop(); 
    System.err.println(node.value); 
    if(node.left != null) { 
     queue.add(node.left); 
    } 
    if(node.right != null) { 
     queue.add(node.right) 
    } 
    breadhFirst(queue); 
}