向树中添加元素

Question

我有一个二叉树，我正在尝试添加元素

问题是如果我有并且在树中输入像 5 5 6 6 9 0 0 2 -1 只添加 5 6 9 0 2（我使用 -1 停止添加元素）

我尝试更改 if(nodeToAdd.data <= node.data) 中的条件 if(nodeToAdd.data < node.data) 但这没有帮助，我尝试了不同的条件，但每次我遇到堆栈溢出时都没有。

我需要更改什么才能将相同的数字相加两倍、三倍或 n 倍？有什么想法吗？

问题已解决，现在一切正常）

private Node traverseAndAddNode (Node node, int data){

    if(node==null)return new Node(data);

    if(data <= node.data){

       node.leftChild=traverseAndAddNode(node.leftChild, data);

    }else if(data > node.data){
        node.rightChild=traverseAndAddNode(node.rightChild, data);
    }

    return node;

}

Answer 1

目前如果 nodeToAdd.data == node.data 您的方法不执行任何操作，因为两个 if 条件都失败了。您可能想要：

if (nodeToAdd.data < node.data) {
    ...
else {
    ...
}

在这种情况下，相等的节点将被插入到右侧。如果你想让它们插入到左边，那么 if 条件 <=.

None 其中解释了您提到的堆栈溢出，但这可能是一个不相关的错误。我注意到您的代码依赖于添加的具有空子节点的节点。我建议您明确断言这一点，以确保在此方法中不会向您的树中添加任何循环。它们很可能被添加到其他地方。

assert nodeToAdd.leftChild == null;
assert nodeToAdd.rightChild == null;

Answer 2

我刚在我的树上试过你的代码。看起来它有效。

private Node put(Node i, Key key, Value value) {
    if (i == null) return new Node(key, value, 1);

//      int compare = key.compareTo(i.key);
//      if (compare < 0) i.left = put(i.left, key, value);
//      else if(compare > 0) i.right = put(i.right, key, value);
//      else i.value = value;
//      
//      //update N while unwinding stack
//      i.N = size(i.left) + size(i.right) + 1;
    int compare = key.compareTo(i.key);
    if (compare < 0) {
        if (i.left == null) i.left = new Node(key, value, 1);
        else put(i.left, key, value);
    }
    if (compare >= 0) {
        if (i.right == null) i.right = new Node(key, value, 1);
        else put(i.right, key, value);
    }       
    return i;
}



    //main
    BST<String, Integer> bst = new BST<>();
    String[] s = {"S", "S", "E", "E", "X", "A", "R", "C", "H", "M"};
    for (int i = 0; i < s.length; i++) {
        bst.put(s[i], i);   
    }   
    for(String key: bst.keys()) System.out.print(key + " "); // levelordered

输出：S E S A E X C R H M

向树中添加元素

Adding elements to tree

java

algorithm

binary-tree

nodes