2

まず、これは宿題なので、そこに出してください。

特定の方法で二分探索木を実装することになっています。

void 挿入 (文字列)、ブール型の削除 (文字列)、およびブール型の検索 (文字列)。

insert メソッドと find メソッドのプログラミングとテストは成功しましたが、remove に問題があります。

私のプログラムで何が起こっているかというと、削除は実際にはツリーから何も削除していないということです。これは、現在のノードのローカル作成のみを参照しているためだと思いますが、間違っている可能性があります。テストする必要があるさまざまなケースのロジックを実装できると思います (2 つの子ケースを持つノードを削除するのに助けが必要かもしれませんが、概念的に理解していると思います)適切にツリー

current = null; // case

これが私がこれまでに得たものです：

public boolean remove(String title)
{
    return remove(root, title);
}
private boolean remove(BSTNode current, String title)
{
    if (current == null)
    {
        return false;
    }
    if (current.data == title)
    {
    if (current.left_child !=null && current.right_child != null)
    {
        return true;  // returning true since I haven't finished writing this case
    }
    else if (current.left_child == null && current.right_child == null)
        {
        current = null;  // this should remove the node from tree but it doesn't
        return true; 
    }

    else if (current.left_child != null && current.right_child == null)
    {
        current = current.left_child;    // don't think this is right
        return true;
    }
    else if (current.right_child != null && current.left_child == null)
    {
        current = current.right_child;   // not sure about this
        return true;
    }

    }
root = current;
if (title.compareToIgnoreCase(current.data) == -1)
{
    return remove(current.left_child, title);
}
    else 
{
    return remove(current.right_child, title);
}
}

どんな知識でも大歓迎です。

4

1 に答える 1

2

ノードはその親によって参照されます (ルートを除き、そのノードは BST 自体によって参照されます)。ツリーからノードを削除するには、親ノードの参照を に設定する必要がありますnull。

あなたが今やろうとしていることは次のようなものです：

Before:
parent.left ---> node <--- current

After setting current = null:
parent.left ---> node      current ---> null

つまり、現在の参照ですnullが、親は変更されません (そのローカル変数のみ)。

remove メソッドでは、親も渡す必要があります (または、親の呼び出しで両方の子を好きなように処理します)。

ところで、文字列を と比較することは決してありません==。たとえば、この質問を参照してください。

各ノードに親を明示的に格納せずに、ノードとその親を見つける方法:

再帰を使用するよりもループでこれを行う方が簡単だと思いますが、どちらも機能します。ループ内:

BSTNode parent = null;
BSTNode current = root;
boolean found = false;
while (!found && current != null) {
    int compare = title.compareToIgnoreCase(current.data);
    if (compare == 0) {
        found = true;
    } else {
        parent = current;
        if (compare < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
}
if (!found) {
    // title was not found
} else if (parent == null) {
    // found the root
} else {
    // found another node
}

ノードとその親の両方を返すメソッドが必要なため、再帰は面倒です。これを解決するには、いくつかの単純な内部クラスが必要になります。

private class NodeAndParent {
    public BSTNode node;
    public BSTNode parent;
    public NodeAndParent(BSTNode node, BSTNode parent) {
        this.node = node;
        this.parent = parent;
    }
}

private boolean find(String title, NodeAndParent current) {
    if (current.node == null) {
        return false; // not found
    } else {
        int compare = title.compareToIgnoreCase(current.node.data);
        if (compare == 0) {
            return true; // found
        } else {
            current.parent = current.node;
            if (compare < 0) {
                current.node = current.node.left;
            } else {
                current.node = current.node.right;
            }
        }
    }
}

private boolean remove(String title) {
    NodeAndParent nodeAndParent = new NodeAndParent(root, null);
    boolean found = find(title, nodeAndParent);
    if (!found) {
        // title was not found
    } else if (nodeAndParent.parent == null) {
        // found the root
    } else {
        // found another node
    }
}
于 2013-11-03T00:09:41.120 に答える