-1

独自のバイナリツリーを作成しようとしていますが、挿入に問題があります。ツリーの値が複製されます。「Noderight、left and intvalue」フィールドを持つ内部静的クラスNodeと、1つのフィールド（ノードルート）を持つ外部クラスBinaryTreeがあります。

挿入コード：

public void insert(int number) {
    if (root.isEmpty())
        root.value = number;
    else {
        Node node = root;
        insert(number, node);
    }
}

private void insert(int number, Node node) {
    if (number < node.value && node.left != null) {
        node = node.left;
        insert(number, node);
    } else {
        if (node.left == null)
            node.left = new Node(null, null, number);
    }

    if (number > node.value && node.right != null) {
        node = node.right;
        insert(number, node);
    } else {
        if (node.right == null)
            node.right = new Node(null, null, number);
    }
}

私は何を間違っていますか？

4

1 に答える 1

1

ルートとしてXというノードがあるとします。いくつかの番号を挿入しています 

if (number < node.value && node.left != null) {
    node = node.left; // NODE IS NOW Y
    insert(number, node);
}

これで、次のifステートメントに進みます

if (number > node.value && node.right != null) {
    node = node.right;
    insert(number, node);
} else {
    if (node.right == null)
        node.right = new Node(null, null, number);
}

ノードは現在Yに等しく、子はありません。したがって、node.right==nullです。したがって、番号はYの右の子として再挿入されます。

したがって、番号のコピーが存在します。returnを使用して解決します。

private void insert(int number, Node node) {
    if (number < node.value && node.left != null) {
        node = node.left;
        insert(number, node);
        return;
    } 
    else {
        if (node.left == null)
            node.left = new Node(null, null, number);
        return;
    }

    if (number > node.value && node.right != null) {
        node = node.right;
        insert(number, node);
        return;
    }
    else {
        if (node.right == null)
            node.right = new Node(null, null, number);
        return;
    }
}
于 2012-12-09T01:23:46.260 に答える