この再帰はどのように動作し、どのようにしてルートを出力するのですか？

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

の実装を行いました。問題は、それが私のルートである要素を表示しない、そうでなければうまくいくように見えることです（編集の開始）。 -12 -13 -1 0 12を：これは、以下の順序でそれらを返し、100値-12、-13、-1、0、12、10、123、122、124以下挿入 124明確に注文されていない商品です。 （編集の終了）

私は、再帰部分の仕組みが完全にわからないことがあり、これを説明して、適切な場所にルートを印刷する方法を得ることができるようにしたいと思います。

Answer 1

あなたはそれを開始ノードを通過した後、左と右のサブツリーを印刷するように見えます。がnullの後にprint文を移動：あなたはEDIT

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

ノードの左と右の子供のメソッドを呼び出して、メソッドへのparamとして渡されるノードに値をプリントアウトする必要があり、 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); 
}