0

二分木が完全な二分木であるかどうか、つまり、最後のレベルを除いて各ノードに 2 つのノードがあるかどうかを確認する必要があります。これらは私がこれまでに行った方法ですが、機能していないようで、見つけるのにかなり苦労しています。何か案は？

private boolean isPerfect(BinaryNode<AnyType> t){

    int sizeTree = size(t);

    double num =  Math.log(sizeTree+1)/Math.log(2);  

    int checkNum = (int) (Math.floor(num));

    if(num - checkNum == 0)
        return true;
    else{
        return false;
    }
}
4

1 に答える 1

5

これは「学習演習」のように聞こえるので、ヒントを次に示します。

  • ツリー ノードの深さの最小値と最大値を比較します。

注: これは 1 つのアプローチにすぎませんが、考えさせるには十分なはずです。

@phcoding のコメントは、ここでの問題は、実際には「完全な検索ツリー」の代替定義間の不一致である可能性があることを指摘しています。2^Nあなたのコードは、葉ノード が正確にある場合 (正しく配置されている場合) に機能するはずです。

参照: http://en.wikipedia.org/wiki/Binary_tree ... 「完全な」、「完全な」、「完全な」二分木の定義を探してください。

于 2013-03-31T00:02:00.567 に答える