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

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/浏览上面的文章应该有所帮助。快乐学习！！