【问题描述】判断两棵二叉树是否结构相同。结构相同意味着对应的左子树和对应的右子树都 结构相同，不考虑数据内容。若已知两棵二叉树 B1 和 B2 皆为空, 或者皆不空且 B1 的左、右子 树和 B2 的左、右子树分别结构相同, 则称二叉树 B1 和 B2 结构相同。 【实验要求】 二叉树采用二叉链表存储，二叉链表定义如下： typedef char ElemType; typedef struct bitnode{ //定义二叉树节点结构 ElemType data; //数据域 struct bitnode *lchild,*rchild; //左右孩子指针域 }BiTNode,*BiTree; 【测试界面】 请输入（在空子树处添加*）二叉树 A 的先序序列： ABD*F***CE*** 请输入（在空子树处添加*）二叉树 B 的先序序列： MNA*B***FD*** [输出] 结构相同

以下是判断两棵二叉树是否结构相同的C++代码实现：

#include<iostream>
using namespace std;

typedef char ElemType;
typedef struct bitnode{
    ElemType data;
    struct bitnode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T){ //先序遍历创建二叉树
    ElemType ch;
    cin>>ch;
    if(ch == '*')
        T = NULL;
    else{
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

bool isSame(BiTree T1, BiTree T2){ //判断两棵二叉树是否结构相同
    if(T1 == NULL && T2 == NULL)
        return true;
    else if(T1 == NULL || T2 == NULL)
        return false;
    else{
        bool left = isSame(T1->lchild, T2->lchild);
        bool right = isSame(T1->rchild, T2->rchild);
        return left && right;
    }
}

int main(){
    BiTree A, B;
    cout<<"请输入（在空子树处添加*）二叉树 A 的先序序列：";
    CreateBiTree(A);
    cout<<"请输入（在空子树处添加*）二叉树 B 的先序序列：";
    CreateBiTree(B);
    if(isSame(A, B))
        cout<<"结构相同"<<endl;
    else
        cout<<"结构不同"<<endl;
    return 0;
}

输入示例：

请输入（在空子树处添加*）二叉树 A 的先序序列：ABD*F***CE***
请输入（在空子树处添加*）二叉树 B 的先序序列：MNA*B***FD***

输出示例：

结构相同