判断二叉树是否相等

1、算法思想

先序遍历二叉树
判断如果其中一棵树为空，那么一定不相等！
如果两棵都为空，那么一定相等！
在结点值相等的情况下执行先序遍历，递归判断！
否则都是不相等的情况，包括值不相等的情况！

2、算法实现

——————————————————————————————————————————————————
#include
#include
#define MaxSize 20
#include
#include<stdlib.h>
#include “queue”
#define endl ‘\n’
using namespace std;
typedef struct BiTNode{ //结点
char data; //数据域
struct BiTNode *lchild,*rchild; //指针域
}BiTNode,*BiTree;
——————————————————————————————————————————————————
//先序遍历的顺序建立二叉链表
void CreateTree(BiTree &T){
char ch;
cin>>ch;
if (ch == ‘#’) T = NULL; //递归结束，建立空树
else{
T = new BiTNode; //申请一个结点
T->data = ch; //将输入值赋值给T
CreateTree(T->lchild); //递归创建左子树
CreateTree(T->rchild); //递归创建右子树
}
}
——————————————————————————————————————————————————
//先遍历输出
void PreOrder(BiTree T){
if(T != NULL){
cout PreOrder(T->lchild); //递归输出左子树
PreOrder(T->rchild); //递归输出右子树
}
}
——————————————————————————————————————————————————
int IsSame(BiTree T,BiTree T1){
if (T != NULL && T1 == NULL || T == NULL && T1 != NULL ) return 0; //如果其中一个为空，则不同
else if (T == NULL && T1 == NULL ) return 1; //若两个都为空，则相同
else if (T->data == T1->data) //如果值不同也不同
return IsSame(T->lchild,T1->lchild) && IsSame(T->rchild,T1->rchild); //左右子树都相同才相同
else return 0;
}
——————————————————————————————————————————————————
int main(){
BiTree T;
cout<<”\n请输入字符！（若输入的是#代表建立的是一棵空树T1）：“;
CreateTree(T);
cout<<”\n先序遍历输出二叉链表："; //A B C # # D E # # G # # F # # #
//ABC##DE##G##F###
PreOrder(T);

fflush(stdin);
BiTree T1;
cout<<“\n\n请输入字符！（若输入的是#代表建立的是一棵空树T2）：”;
CreateTree(T1);
cout<<“\n先序遍历输出二叉链表：”; //A B C # # D E # # G # # F # # #
//ABC##DE##G##F###
PreOrder(T1);
if (IsSame(T,T1)) cout<<“\n\n两个二叉树相同！”;
else cout<<“\n\nT 和 T1不相同！”<<" "< }
——————————————————————————————————————————————————