Как я могу получить метод добавления BST для добавления узлов за первые два дочерних узла?

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

Как правило, с бинарными деревьями вы будете писать рекурсивные функции. Вместо управления вставкой из одного вызова функции вы можете найти сторону, к которой принадлежит узел, и передать ее в рекурсивный вызов функции на стороне этого узла.

Предполагая, что эта функция относится к классу User, это должно работать.

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