在树数据结构中添加节点时的java递归

Question

我对理解和学习数据结构是新手。在搜索了一些教程之后，我尝试实现树数据结构。这似乎很好，但我不理解这里有点奇怪的递归行为。有人能帮我理解代码吗

我已经包含了一些print语句来理解递归流，但无法理解为什么当前引用没有被返回

public class TreeCheck {
Node root;
private Node addRecursive(Node current, int value) {
if (current == null) {
    return new Node(value);
}

if (value < current.value) {
    current.left = addRecursive(current.left, value);
} else if (value > current.value) {
    current.right = addRecursive(current.right, value);
} else {
    // value already exists
    return current;
}
System.out.println("current is "+current.value); //Please compare in the 
 image why the 
return current;
}


public void add(int value) {
root = addRecursive(root, value);
System.out.println("value is "+root.value);
}

  public static void main(String h[]){
 TreeCheck bt = new TreeCheck();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);


    }

  class Node {
  int value;
  Node left;
  Node right;

   Node(int value) {
    this.value = value;
    right = null;
    left = null;
}
}

为什么当前语句被打印两次，并且总是仅在当前语句有时被重新分配时才返回根元素

Answer 1

由于以下原因，它无法正确打印：

首先，add方法总是打印“value is”+root。“值”，这在试图弄清楚程序如何添加值时令人困惑

其次，您的add方法在插入值后打印，我将对其进行重新构造，使其先打印要插入的值，然后打印检查节点的路径：

    public void add(int value) {
    // you always printed out the value of the root node with every call to this method
    // I updated it to reflect the input argument
    System.out.println("\nvalue is " + value);
    root = addRecursive(root, value);
}

现在，每个块都有自己的插入，程序流更容易跟踪

下一步：current实际上是按相反的顺序正确打印的。假设插入5，当前要打印的节点是：5的父节点是4，然后是4的父节点是6

这张图片可能有助于形象化这棵树（对不起，我的手写得很难看）

如果要更改顺序，请这样做（将current的打印置于If语句之前）：

    private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    System.out.println("current is " + current.value);

    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
}

此外，如果您想查看插入二进制搜索树是否有效，可以使用此方法按升序打印树：

    public void inOrderPrint(Node node){

    if (node.left != null) {
        inOrderPrint(node.left);
    }

    System.out.println(node.value);

    if (node.right != null) {
        inOrderPrint(node.right);
    }
}

你可以这样称呼它：

    public static void main(String h[]) {
    TreeCheck bt = new TreeCheck();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    System.out.println("   -");
    bt.inOrderPrint(bt.root);

}

我希望这是有帮助的，我解释得很清楚。请评论，如果我做了一个错误的声明，我会相应地编辑文章