Похожие двоичные деревья

Я написал следующую функцию, чтобы проверка двух 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;
}

0

c++

Решение

Другие решения

Вы должны убедиться, что если 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;
}

а также, б-дерево не коротка для бинарное дерево.

1

Источник

Accepted Answer

Во-первых, вы могли бы извлечь большую пользу из разрыва своего кода, в частности, из-за того, что if заявление на четвертой строке противный. Почему бы просто не обработать нулевой регистр в самом методе? например:

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

Насколько я могу судить, реальная проблема с вашим кодом заключается в том, что вы перезаписываете значение m в строке 9, не принимая во внимание предыдущее значение. Если левая часть дерева не похожа, но правая, возвращаемое значение будет равно 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);

2