如何实现判断两个二叉树是否相同？

Question

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

#define OK 1
#define OVERFLOW -1

typedef int Status;
typedef char TElemType;

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lChild, *rChild;
} BiTNode, *BiTree;

Status InitBiTree(BiTree *BT);

Status CreateBiTree(BiTree *BT);

bool IsSame(BiTree BT1, BiTree BT2);

Status main() {
    BiTree BT1, BT2;
    printf("To Creat Binary Tree 1,Please Input PreOrder with '#':\n");
    InitBiTree(&BT1);
    CreateBiTree(&BT1);
    printf("To Creat Binary Tree 2,Please Input PreOrder with '#':\n");
    InitBiTree(&BT2);
    CreateBiTree(&BT2);
    if (IsSame(BT1, BT2)) {
        printf("\n相同\n");
    } else {
        printf("\n不相同\n");
    }
    return OK;
}

Status InitBiTree(BiTree *BT) {
    *BT = NULL;
    return OK;
}

Status CreateBiTree(BiTree *BT) {
    TElemType ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *BT = NULL;
    } else {
        *BT = (BiTNode *) malloc(sizeof(BiTNode));
        if (!(*BT)) {
            exit(OVERFLOW);
        }
        (*BT)->data = ch;
        CreateBiTree(&(*BT)->lChild);
        CreateBiTree(&(*BT)->rChild);
    }
    return OK;
}

bool IsSame(BiTree BT1, BiTree BT2) {
    if (BT1 == NULL && BT2 == NULL) {
        return true;
    }
    if (BT1 == NULL || BT2 == NULL) {
        return false;
    }
    if (BT1->data != BT2->data) {
        return false;
    }
    return (IsSame(BT1->lChild, BT2->lChild) && IsSame(BT1->rChild, BT2->rChild));
}

在如下输入的情况下，这段代码运行输出不出预期的结果“相同”。

To Creat Binary Tree 1,Please Input PreOrder with '#':
ab#d##c##
To Creat Binary Tree 2,Please Input PreOrder with '#':
ab#d##c##

Answer 1

在你调用 CreateBiTree(&BT2) 里面的 scanf 会获得第一次输入行尾的回车，但你的程序没处理这种情况，就直接卡死等待了，把 scanf 那里改一下就好了

    do
    {
        scanf("%c", &ch);
    } while (ch == '\n');