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

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;}}为什么 current 语句被打印两次并且总是只在 current 有时被重新分配时才返回根元素？

Answer 1

由于以下原因，它没有正确打印：

首先，您的添加方法总是打印“值是”+ 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);

}

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

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

    }

}

在你的 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);

}

我希望这对您有所帮助，并且我已经解释清楚了。

Answer 2

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

浏览上面的文章应该有所帮助。快乐学习！！