java - Java中的BST递归实现

Question

我不知道为什么我需要再次分配node.left = insert(node.left, data)，因为我已经使用node = new BNode(data)分配了它.

private BNode insert(BNode node, int data) { 
    if (node == null) { 
       node = new BNode(data); 
    } 
   else if (node.data < data) { 
        node.left = insert(node.left, data); 
    } 
   else if (node.data > data) { 
        node.right = insert(node.right, data); 
    } 
    return node; 
}

Answer 1

在二叉搜索树中，您必须将任何新元素作为叶子放置。您的代码首先检查我们当前是否正在查看节点，如果是，则在此处插入我们的数据。否则，我们需要继续沿着 Twig 向下移动，直到到达叶子。因此，我们在左分支或右分支上调用此函数(取决于节点中的数量和数据)。我们的方法是调用node.left 或node.right 上的函数。如果子节点为空，那么我们想说现在我们的子节点就是我们刚刚插入的新节点。

如果子节点不是叶子，则通过返回原始子节点，此分配将不会执行任何操作。它只是通过说来做某事

node = new BNode(data);

因此，上一次调用此方法将是唯一将其左子或右子更改为当前新叶子的时间，而所有其他左子和右子都保持原样。