java - 二分探索木の追加と生成

Question

二分探索木にノードを追加または挿入する方法を理解するのに少し苦労しています。現時点では、次のコードがあります。

public void add(int v) { 
        Node n = new Node(v); 
        if(root==null)
            root = n;   
        else {  
            Node m = root;  
            while(...) { //not sure what to check
                if(v < m.value)
                    m = m.left;
                else
                    m = m.right;
            }
            if(...) //not sure what to check
                m.left = n;
            else
                m.right = n; 

        }   
    }

次に、特定の範囲内で n 個のノードを生成したいと思います。配列に対してこれを行う方法は知っていますが、BST のノードに対して行う方法がわかりません。

public void generate(int n, int range) {

  }

Answer 1

現在のアプローチを使用すると、親を追跡するために追加の変数が必要になりますNode

public void add(int v) { 
        Node n = new Node(v); 
        if(root==null)
            root = n;   
        else {  
            Node m = root,k;  
            while(m!=null) {
                if(v < m.value){
                    k=m;
                    m = m.left;
                 }
                else if(v > m.value){
                    k=m;
                    m = m.right;
                 }else{
                    return; //v already exists
                 }
            }
            if(v < k.value)
                k.left=n;
            else
                k.right=n;
        }   
    }

---

範囲に関する 2 番目の質問については、DrYap が指摘したように、範囲内で数値を生成し、数値ごとに add() を呼び出します。