为什么这个递归函数只设置一次？

Question

我知道递归一直在执行，直到它符合基本情况。

但是，为什么这个递归函数只设置头部的孩子一次？

当head变为null时，它返回节点并将head的左子节点或右子节点设置为节点。

我得到了这个概念，但为什么这个递归函数不会将所有左子节点或右子节点设置为节点，即使它是递归函数？

还有一个问题，当头为空时，这个递归会停止，但为什么这个递归不会将null的子设置为节点？此递归将null的head的子项的前一个设置为节点。为什么？

public Node<Integer> insert(Node<Integer> head, Node<Integer> node){
    if(head == null){
        return node;
    }

    if(head.getData() >= node.getData()){
        head.setLeftChild(insert(head.getLeftChild(), node));
    } else {
        head.setRightChild(insert(head.getRightChild(), node));
    }

    return head;
}

Answer 1

我们这里有一个binary search tree插入功能。

该函数将两个节点作为参数：head是二叉树的根，node是您插入其中的新节点。

新的node将以这样一种方式插入，即树的depth-first in-order traversal将产生一个递增的整数序列。

为什么这个递归函数只设置head的孩子一次？

它在递归的路上设置沿着从根节点到插入节点位置的路径上的所有树节点。但是，只有第一个赋值是有意义的，因为所有其他赋值只是设置相同的节点而没有更改

为什么这个递归函数不会将所有左子节点或右子节点设置为节点，即使它是递归函数？

此递归中函数的每次调用都设置左，右或无子。如果仔细执行，您将看到树中哪个位置设置了哪个位置。

为什么这个递归不将null的子节点设置为节点？

recursion exit condition阻止对head的任何操作，如果它的值是null - 它返回你要插入的node而不是前一个实际插入发生的递归调用。

Answer 2

insert在大多数情况下返回head。每当它返回head时，head.setLeftChild(insert(head.getLeftChild(), node))导致head.setLeftChild(head.getLeftChild())和head.setRightChild(insert(head.getRightChild(), node))导致head.setRightChild(head.getRightChild())。即在大多数情况下，对setLeftChild和setRightChild的调用不会改变当前head Node的左/右孩子。

只有当insert(head.getLeftChild(), node)或insert(head.getRightChild(), node))传递null值时（即当head.getLeftChild()或head.getRightChild()是null时），递归调用返回新的Node，node，这导致head.setLeftChild(insert(head.getLeftChild(), node))导致head.setLeftChild(node)和head.setRightChild(insert(head.getRightChild(), node))导致head.setRightChild(node)。