Java 二叉树插入方法无效

Question

我正在为二叉树制作递归插入方法。此方法无法将节点添加到树中。我似乎找不到这种方法有什么问题。构造函数为子节点和父节点取一个字符串标签。

 public void insert(String aLabel) {

    //if compare is positive add to right else add to left
    //basis case:
    BSTreeNode aNode = new BSTreeNode(aLabel,null);
    if (aNode.parent == null) {
        aNode.parent = this;
    }
    inserts(this,aNode);
}
private void inserts(BSTreeNode aParent, BSTreeNode aNode){
    //initially the root node is the parent however a proper parent is found thorough recursion
    //left recursion:
    if(aParent.getLabel().compareTo(aNode.getLabel()) <= 0) {
        if (this.childrenLeft == null) {
            this.childrenLeft = aNode;
            aNode.parent = this;
            return;
        } else {
            childrenLeft.inserts(childrenLeft, aNode);
        }
    }
    //right recursion
    else {
        if (this.childrenRight==null) {
            this.childrenRight = aNode;
            return;
        }
        else{
            childrenRight.inserts(childrenRight,aNode);
        }

    }

}

Answer 1

编辑：这个答案指的是问题的原始版本。

当你调用inserts(this.childrenLeft, aNode);时你仍然在同一个节点；即 this 仍然指的是旧的 parent.

相反，您应该这样做：

childrenLeft.insert(childrenLeft, aNode);

其实insert的第一个参数是多余的，应该重构去掉。

Answer 2

我想你可能需要这样的东西。

对代码进行了注释，以便您了解发生了什么...

// insert method takes The Node as a param and a value to store in BT
public void insert(Node node, int value) {

//Check that the value param is less than the Node (root) value,
// If so insert the data to the left of the root node. Else insert        
// the right node as it is a larger number than root
if (value < node.value) {
  if (node.left != null) {
    insert(node.left, value);
  } else {
    System.out.println("  Inserted " + value + " to left of "
        + node.value);
    node.left = new Node(value);
  }
} else if (value > node.value) {
  if (node.right != null) {
    insert(node.right, value);
  } else {
    System.out.println("  Inserted " + value + " to right of "
        + node.value);
    node.right = new Node(value);
  }
 }
}

Java 二叉树插入方法无效

Java Binary Tree insert method not working

java

recursion

binary-tree

nodes

binary-search-tree