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

``````#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##
``````

1 个回答
✓ 已被采纳

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

###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进