0

2 つの b ツリーが類似しているかどうかをチェックする次の関数を作成しました。しかし、目的の出力が得られません。

int bt_similar(btree *b1, btree *b2)
{
    int m=1;
    if ((b1->data==b2->data&&(((b1->lchild==NULL&&b2->lchild==NULL)||(b1->lchild!=NULL&&b2->lchild!=NULL))&&((b1->rchild==NULL&&b2->rchild==NULL)||(b1->rchild!=NULL&&b2->rchild!=NULL))))&&(m))
    {
        if (b1->lchild!=NULL)
        m=bt_similar(b1->lchild,b2->lchild);
        if (b1->rchild!=NULL)
        m=bt_similar(b1->rchild,b2->rchild);
        if (m)
        return 1;
    }
    return 0;
}
4

2 に答える 2

2

まず、コードを分割することで多くのメリットが得られます。特にif、4 行目のステートメントの大きな条件はnastyです。メソッド自体で null ケースを処理しないのはなぜですか? 例えば：

if (b1 == null && b2 != null)
    return 0;
if (b2 == null && b1 != null)
    return 0;
if (b1 == null && b2 == null)
    return 1;

私が知る限り、コードの実際の問題は、前の値を考慮せずに 9 行目の m の値を上書きするところにあります。ツリーの左側が似ておらず、右側が似ている場合、戻り値は 1 になります。代わりに:

    if (b1->lchild!=NULL)
    m=bt_similar(b1->lchild,b2->lchild);
    if (b1->rchild!=NULL)
    m=bt_similar(b1->rchild,b2->rchild);

あなたが持っている必要があります：

    if (b1->lchild!=NULL)
        m = bt_similar(b1->lchild,b2->lchild);
    if (b1->rchild!=NULL)
        m = m && bt_similar(b1->rchild,b2->rchild);
于 2013-08-27T13:04:25.817 に答える
1

b1 == NULL または b2 == NULL の場合...

bool compare(struct node* b1, struct node* b2) {

    // 1. both empty -> true
    if (b1==NULL && b2==NULL) return(true);   

    // 2. both non-empty -> compare them
    else if (b1!=NULL && b2!=NULL) {
        return(
            b1->data == b2->data &&
            compare(b1->lchild, b2->lchild) &&
            compare(b1->rchild, b2->rchild));
    }

    // 3. one empty, one not -> false
    else return false;
}

また、b-treeはbinary tree の略ではありません。

于 2013-08-27T13:03:50.490 に答える