0

私は自分の二分木をコード化しようとしています。二分探索木の例はたくさんありましたが、自分で書くことにしました。

これまでのところ、私はこれに行き着きました：

public class bTree {
bnode root=null;

void add(int val){
    bnode newnode= new bnode(val);
    bnode curr = this.root;
    bnode parent = null;

    if(this.root == null){
        this.root = newnode;
        System.out.println("Inserted at root \t"+newnode.value);
    }
    else{
            while( curr != null){
            System.out.println("Current Left and Right\t"+curr.left+"\t"+curr.right);

            if(curr.left == null){
                curr =  curr.left;
                curr = newnode;
                System.out.println("Inserted Left\t" +newnode.value);
                return;
            }
            if(curr.right ==  null){
                curr =  curr.right;
                curr = newnode;
                System.out.println("Inserted Right\t" +newnode.value);
                return;
            }
        }
    }
}

二分木に値を追加しようとすると、ルートだけが値を追加できます。私はゆっくりと残りのコードを書き込もうとしています。ここでは、左の子がいっぱいであることがわかり、バックトラックとすべてのケースがあります。私の質問は、左端の子に次の値を追加することさえできないのはなぜですか(2回目の呼び出しで)。コードを教えていただければ幸いです。私は学びたいのです。

4

3 に答える 3

3

ここでのあなたの声明では：

        if(curr.left == null){
            curr =  curr.left;
            curr = newnode;
            ...
        }

「curr = curr.left」を割り当てると、「curr」に null が割り当てられ、ツリー内の何も参照されなくなります。ツリーがそれを参照するように、「curr」の左側のリンクを新しいノードに割り当てる必要があります 

        if(curr.left == null){
            curr.left = newnode;
            ...
        }

この 2 つの違いを示す図を次に示します。 ここに画像の説明を入力

于 2013-09-19T04:11:11.840 に答える
2

2 番目の呼び出しで、左端の子に次の値を追加しないのはなぜですか?

curr.leftこれはに割り当てられないためnewnode：

curr = curr.left;
curr = newnode;

修理：

curr = curr.left = newnode;

コードにはまだ他のバグがあることに注意してください。より多くの呼び出しでそれらを見つけることができます。

于 2013-09-19T03:37:24.747 に答える
1

入力すると、else {} curr は常に != null (curr=root および root!=null であるため) であるため、ループは実行されません。

于 2013-09-19T03:32:13.233 に答える