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 和 right 方法：

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

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

}

Answer 1

大多数二叉树遵循不同的风格，并在递归方法内部设置parent的left/right child，而不是child向上并告诉有人这是他们的新人 parent

对于大多数二叉树的功能，此代码更加标准：

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);
}

该代码应该正确保存正在创建的 BSTreeNode 的值，并且具有减少 parent 如何获得它的混淆的附加效果 child

对于大多数人来说，parent 得到 child 而不是 child 到达一个节点并告诉它它是街区

上的新 child

Answer 2

你的逻辑可能有点问题。

从构造函数添加时，您直接调用 addLeftChild 或 addRightChild。这些函数检查 right/left 上的节点是否为 null，如果为空则添加值。但是，如果它不为空怎么办。然后它应该与 left/right 子节点进行比较并继续，否则节点不会被添加（即函数失败并且不会 return 任何东西，因为它的 void）。

Java 二叉树插入无法正常工作

Java Binary tree insert is not working properly

java

recursion

binary-tree

insert

nodes