最初の2つの子ノードを超えてノードを追加するには、どのようにしてBSTの追加メソッドを取得できますか？

Question

私はバイナリツリーの新機能で、シンプルなゲームのための追加メソッドを扱っています。現在、このメソッドは、新しいノードを追加するたびにルートノードの子ノードを置き換えます。ルートノードの最初の2つの子ノードを置き換えるのではなく、ツリー全体に新しいノードを追加するにはどうすればよいですか？これはこれまで私が持っているものです：

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