Java二叉树插入不正常工作

Question

当我在插入方法中添加一个名为“Bob”的节点时：

public void insert(String aLabel){
    //left recursion:
    if(this.getLabel().compareTo(aLabel) <= 0) {
        if (childrenLeft == null) {
            BSTreeNode aNode = new  BSTreeNode(aLabel,this);
            return;
        }
    else {
            childrenLeft.insert(aLabel);
        }
    }
    //right recursion
    else {
        if (childrenRight==null) {
            BSTreeNode aNode = new BSTreeNode(aLabel,this);
            return;
        }
    else{
            childrenRight.insert(aLabel);
        }

    }

}

我的树只在左侧添加一个没有标签的空节点。 (BSTreeNode aNode = new BSTreeNode;)是否有问题？因为当我像这样硬编码节点时：

BSTreeNode Louis = new BSTreeNode("Louis", treeRoot);
BSTreeNode bonny = new BSTreeNode( "bonny", treeRoot);
BSTreeNode Sue = new BSTreeNode("Anne", bonny);
BSTreeNode Sam = new BSTreeNode("Sam",Louis);
BSTreeNode Anne2 = new BSTreeNode( "delta", bonny);
BSTreeNode Frank = new BSTreeNode("Kalle", Louis);

这个树展示了标签并且被插入到所需位置。其他的代码-构造函数：

public BSTreeNode( String aLabel,BSTreeNode aParent){
    label = aLabel;
    parent = aParent;
 //add this node as a child of this node's parent either left or right

    if(parent != null){
        if(parent.getLabel().compareTo(label)<= 0) {
            parent.addLeftChild(this);
        }
        if(parent.getLabel().compareTo(label)> 0) {
            parent.addRightChild(this);
        }

    }

}

这是在节点创建时将节点添加到父节点的构造函数。添加childleft和childright方法：

private void addLeftChild(BSTreeNode aNode){
    if(childrenLeft == null) this.childrenLeft = aNode;

}
private void addRightChild(BSTreeNode aNode) {
    if(childrenRight == null) this.childrenRight = aNode;

}

- Ben Joshua S

---

我没有在另外两个代码块中看到insert()被调用。 - ergonaut

你能否添加类BSTreeNode的代码？ - Rahul Shardha

这些代码的添加表明，只要节点在主应用程序中硬编码，构造函数仍然能够工作，即使没有插入。它基本上展示了构造函数的工作原理，该构造函数也用于在插入方法中创建新节点。 - Ben Joshua S

添加整个类（大量代码）是不切实际的，但插入方法独立于BSTreeNode类中创建的其他方法工作。除了构造函数本身。 - Ben Joshua S

你尝试过在IDE中逐步调试并在执行期间检查变量值吗？这可能是更快定位问题的方法。 - Rahul Shardha

看一下你的逻辑。创建新的BSTreeNodes时，函数进入构造函数 -> 然后进入addLeftChild/addRightChild。检查它是否为空，如果是，则添加它。如果不为空会发生什么？您的插入函数会处理此事，但您的构造函数没有处理。从您的代码中可以看出，您正在调用构造函数。尝试加入这些检查并运行程序，看看会发生什么。 - Rahul Shardha

Answer 1

大多数二叉树都遵循不同的风格，而是在递归方法中设置父节点的左/右子节点，而不是子节点上升并告诉某人它们的新父节点

这段代码更符合大多数二叉树的功能标准：

public void insert(String aLabel)
{
    if(getLabel().compareTo(aLabel) <= 0)
        if(childrenLeft == null)
            childrenLeft = new BSTreeNode(aLabel, this);
        else
            childrenLeft.insert(aLabel);
    else
        if(childrenRight == null)
            childrenRight = new BSTreeNode(aLabel, this);
        else
            childrenRight.insert(aLabel);
}

这段代码应该正确地保存被创建的BSTreeNodes的值，并且具有使父节点如何获取其子节点变得不那么混乱的附加效果

对于大多数人来说，父节点获取子节点比子节点到达节点并告诉它自己是新的孩子更有意义

- phflack

Answer 2

你的逻辑可能有点错误。

当从你的构造函数中添加时，你直接调用了addLeftChild或addRightChild。这些函数会检查左/右侧的节点是否为null，如果是，则添加该值。但如果它不是null呢？那么它应该与左/右子节点进行比较并继续，否则节点将不会被添加（即函数会跳过并且不返回任何东西，因为它是void）。

- Rahul Shardha