Site Overlay

C 语言 判断二叉树相似

这是作业。

代码如下:


#include <stdio.h>
#include <stdbool.h>
#include <string.h>

// 题目给的定义
typedef struct node
{
    int data ; 
    struct node *lchild, *rchild; 
}btnode, *bitptr ; 

// 判断两颗棵以二叉链表表示的二叉树p和q是否相似
// 若相似函数返回TRUE,否则为FALSE
// printf 是我用来调试的代码,正式提交的时候删掉。
bool similar(bitptr p, bitptr q){
    printf("call\n");
    if(p == NULL){
        printf("p is null\n");
    }
    if(q == NULL){
        printf("q is null\n");
    }
    // p, q 结点都是 null,则结构相同
    if(p == NULL && q == NULL){
        return true;
    }
    // 如果 p, q 不都为 NULL,说明结构不同
    if(p == NULL || q == NULL){
        return false;
    }
    if(p->lchild == NULL){
        printf("p lchild is null\n");
    }
    if(p->rchild == NULL){
        printf("p rchild is null\n");
    }
    if(q->lchild == NULL){
        printf("q lchild is null\n");
    }
    if(q->rchild == NULL){
        printf("q rchild is null\n");
    }
    // 递归判断左右结构是否相同
    return similar(p->lchild,q->lchild) &&
    similar(p->rchild,q->rchild);
}

int main(){
    // 生成测试数据
    btnode r1;
        btnode a1;
        btnode b1;
        memset(&r1, 0, sizeof(r1));
        memset(&r1, 0, sizeof(a1));
        memset(&r1, 0, sizeof(b1));
        r1.lchild = &a1;
        r1.rchild = &b1;
            btnode c1;
            btnode d1;
            memset(&r1, 0, sizeof(c1));
            memset(&r1, 0, sizeof(d1));
            b1.lchild = &c1;
            b1.rchild = &d1;

    btnode r2;
        btnode a2;
        btnode b2;
        memset(&r2, 0, sizeof(r2));
        memset(&r2, 0, sizeof(a2));
        memset(&r2, 0, sizeof(b2));
        r2.lchild = &a2;
        r2.rchild = &b2;
            btnode c2;
            btnode d2;            
            memset(&r2, 0, sizeof(c2));
            memset(&r2, 0, sizeof(d2));
            b1.lchild = &c2;
            b1.rchild = &d2;

    printf("sim: %d\n", similar(&r1, &r2));

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注