方法递归 (Java)

Question

我运行在试图理解二叉搜索树时陷入了一个困惑的境地。当一个方法被调用时，我对方法递归在这里发生的方式感到困惑，比如 inOrder()。下面是代码：

public class Node {
  int data;
  Node left;
  Node right;

public Node (int data) {
    this.data = data;
    left = null;
    right = null;
}
public Node() {
    left = null;
    right = null;
}
public int getData() {
    return data;
 }
}
====================
public class BinarySearch {
  Node root;

public BinarySearch() {
    root = null;
}
public void insert(int data) {
    Node newNode = new Node();
    newNode.data = data;
    if(root == null) {
        root = newNode;
        System.out.println("root =" + root.getData());
    } else {
        Node current = root;
        Node parent;
        while(true) {
            parent = current;
            if(data < current.data) {
                current = current.left;
                if(current == null){
                    parent.left = newNode;
                    break;
                }
        } else {
                current = current.right;
                if(current == null) {
                    parent.right = newNode;
                    break;
                }
            }
        }
    }
}
public void inOrder() {
    inOrder(root);
}
private void inOrder(Node n) {
    if(n != null) {
        inOrder(n.left);
        System.out.print(n.getData() + " ");
        inOrder(n.right);
    }
  }
}
===================
 public class BTree {
    public static void main(String[] args) {
      BinarySearch bst = new BinarySearch();
      bst.insert(10);
      bst.insert(4);
      bst.insert(11);
      bst.inOrder();
   }
}
o/p:
root = 10
4 10 11

请原谅我的冗长代码，但我希望您需要它。

当inOrder()方法被调用时，编译器会向left走极端，直到Node n变成null，然后退出基于[=17=的方法]，但是，编译器在 if for false 之后寻找的直接步骤是 System.out.print(n.getData() + " ");，它又在 'if' 语句中 - 这个功能让我很开心。我是说，

1) 当 if 布尔值仍为 false（因为 Node n 为空）时，编译器如何转到行 System.out.print？

2) 即使打印出来了，当 Node n 实际上减少到 null 时，n.getData() 怎么会有值（o/p: 4）？

提前致谢！

Answer 1

因此，当 inOrder() 命中节点“4”时，它会在节点“4”的左节点上调用另一个 inOrder()，这次它是一个空值，因此它退出，并继续执行 inOrder () 在节点 4 上，打印节点 4 的值，然后在该节点的右侧再次调用 inOrder() 再次为 null，到达函数末尾并 returns 返回到前一个节点. 也正如 Elliott Frisch 所说：尝试使用调试器来了解方法的堆栈。

Answer 2

如果要进入一个空的左节点，程序不会进入第 System.out.print 行。你的程序组装的BST有10为根，4为根的左分支，11为根的右分支。调用 inOrder() 时，在转到 node.data=4 的左分支后，程序会尝试查看 node.data=4 的左分支。左边的分支为空，因此打印了 4 的值。

您可以通过放置

来验证这一点

System.out.print(n.getData() + " ");

以上

if(n != null) {

你会遇到异常。

Answer 3

同意王老师的回答。 java 程序暂停 4 的执行（因为您正在递归调用方法 inOrder(4->left) 即 inOrder(null)。现在，它不会进入条件，因为它失败了）。现在，执行of 4 恢复并打印出值 4，然后继续。希望对您有所帮助。

方法递归 (Java)

Method recursion (Java)

java

recursion

binary-search-tree