代码之家 › 专栏 › 技术社区 › Bishal Kumar Shrestha

相似二叉树

c++

Bishal Kumar Shrestha · 技术社区 · 12 年前

我已经编写了以下函数来检查两个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;
}

2 回复 | 直到 12 年前

davmac 12 年前

首先,您可以从分解代码中受益匪浅,特别是在 if 第四行的语句是 肮脏的 。为什么不在方法本身中处理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);

vvy 12 年前

您应该确保如果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 .

推荐文章

AstralHex · 矩阵乘法代码工作不正常

7 月前

Baba Dan Constantin · SSE4.1在矩阵4x4乘法上比SSE3慢?

7 月前

Giogre · 为包含许多数值字段的简单“struct”重载比较运算符

7 月前

einpoklum · 定义一个并不真正提供now()函数的std::chrono Clock是“合法的”吗?

7 月前

Fishie · 作为类成员的智能指针是否仍然自动释放?[关闭]

7 月前

Die4Toast · 递归调用成员箭头运算符->

7 月前

Angle.Bracket · 如何用C++将UTF-8文件名写入MS Windows控制台?

7 月前

Anka HanÄ±m · 关于结构和动态数组地址的问题

7 月前

Adam Barnes · 我如何定义一个基于constexpr函数返回值进行限制的概念?

7 月前

user2138149 · 为什么我不能获取包含多个元素的结构体中某些元素的地址?[副本]

7 月前