4

BSTs指定された 2 つ(二分探索木) が Java で等しいかどうかをテストしたいと思います。ノードには、親ノードへのBSTポインターがありません。

最も簡単な解決策は、両方をトラバースしBSTs、2 つのトラバーサル リストを作成して、リストが等しいかどうかをテストすることです。ただし、O(N) メモリが必要です。

別の方法を試してみたいと思います:Iteratorをトラバースする を作成し、BSTs... 残りは明らかです。

それは理にかなっていますか？BSTs2つが等しいかどうかをテストするための「より良い」(よりシンプルで効率的な)ソリューションはありますか?

4

3 に答える 3

7

  1. 二分探索木は木ですよね？

  2. 2 つのツリーは、同じルートと同じ子を持つ場合、同等です。

  3. どの子も木です。

  4. ポイント2を参照してください。

ヒント:. メモリ消費量はO(logn)（自分で証明してください）です。

于 2012-07-16T07:03:46.433 に答える
1

最も簡単な方法は、両方のツリーのハッシュを作成し、それらが等しいかどうかを確認することです。これは、両方のツリーの内容が同じ場合にのみ適用されます。

チェックサムを作成し、それらのチェックサムを比較する方法。

http://www.mkyong.com/java/how-to-generate-a-file-checksum-value-in-Java/

于 2012-07-16T07:04:11.597 に答える
1

再帰equals()メソッドを実装します。メモリを必要とせず、コーディングも簡単です。

このようなものが動作するはずです:

public class Node {

    Object value;
    private Node left;
    private Node right;

    public boolean equals(Object o) {
        if (o instanceof Node) {
            Node node = (Node)o;
            if (value.equals(node.value)) {
                return true;
            }
            return ((left == null && node.left == null) || left.equals( node.left)) && 
                    ((right == null && node.right == null) || right.equals( node.right));
        }
        return false;
    }
}

hashCode()この実装を反映するにはオーバーライドする必要があることに注意してください。そのため、equalsDeep()代わりに上記の impl に名前を付け、impl をスキップすることを検討してhashCode()ください。

于 2012-07-16T07:04:34.920 に答える