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

Question

我是理解和学习数据结构的新手。在搜索了一些教程后，我尝试实现树数据结构。看起来不错，但我不理解这里有点奇怪的递归行为。有人可以帮助我理解代码。

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

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.value”，这在尝试弄清楚程序如何添加值时会令人困惑。

其次，您的 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);
}

现在每个 block 都是它自己的插入，程序流程更容易跟踪。

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

这张图片可能有助于可视化树(抱歉我的手写难看)

如果你想改变顺序，可以这样做(将 current 的 print 放在 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);
    }
}

并在你的 main 中这样调用它:

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

}

我希望这对您有所帮助，并且我已经解释清楚了。如果我的言论有误，请评论，我会相应地编辑帖子。