这种递归是如何工作的？我如何让它打印出根？

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