我怎样才能让我的 BST add 方法在前两个子节点之后添加节点？

Question

我对二叉树有点陌生，正在研究一个简单游戏的添加方法。目前，每次我添加新节点时，该方法都会替换根节点的子节点。我怎样才能让它在整个树中添加新节点，而不是仅仅替换根节点的前两个子节点？这是我目前所拥有的：

public boolean add(User friend) {
    User node = friend;
    if (root == null) {
        root = node;
        return true;
    }
    if (node.key() < root.key()) {
        if(root.left == null) {
            root.setLeft(node);
        }
    } else if (node.key() > root.key()) {
        if(root.getRight() == null) {
            root.setRight(node);
        }
    }
    return true;
}

Answer 1

通常，对于二叉树，您将编写递归函数。您可以找到节点所属的一侧，然后将插入移交给该节点一侧的递归函数调用，而不是管理来自一个函数调用的插入。

假设这个函数属于classUser，这应该可以工作。

public boolean beFriend(User friend) {
    User node = friend;
    if (root == null) {
        root = node;
        return true;
    }
    if (node.getKey() < root.getKey()) {
        if(root.getLeft() == null) {
            root.setLeft(node);
        } else {
            // recursively call beFriend handing insertion to the child
            root.getLeft().beFriend(node);
        }
    } else if (node.getKey() > root.getKey()) {
        if(root.getRight() == null) {
            root.setRight(node);
        } else {
            // recursively call beFriend handing insertion to the child
            root.getRight().beFriend(node); 
        }
    } else { // node.getKey() == root.getKey() so we replace the previous root
        node.setLeft(root.getLeft());
        node.setRight(root.getRight());
        root = node;
    }
    return true;
}

我怎样才能让我的 BST add 方法在前两个子节点之后添加节点？

How can I get my BST add method to add nodes past the first two child nodes?

java

binary-tree

binary-search-tree