二叉树的同构

给定两棵二叉树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则称两棵二叉树是“同构”的
现给定两棵树，请判断是否同构

输入格式

输入给出两颗二叉树的信息

先在一行中给出该树的结点数
随后n行中，第i行对应编号第i个结点，给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的百脑汇
如果孩子结点为空，则在相应位置上给出’-’

输入样例

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -

8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

求解思路

二叉树表示
建二叉树
同构判别

二叉树表示

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1                     //注意区别于cstdlib中的NULL(0)，因为0也是下标，所以将“指针”为空的情况设置为-1
结构数组表示二叉树：静态链表             //物理上的存储是使用数组，但运用链表的思想
struct TreeNode                     //顺序存储实现
{
    ElementType Element;
    Tree Left;
    Tree Right;
}T1[MaxTree],T2[MaxTree];           //T1,T2为结构数组，保存整棵二叉树

程序框架搭建：伪代码描述

int main()
{
    建二叉树1
    建二叉树2
    判别是否同构并输出
    return 0;
}

需要设计的函数

读数据建立二叉树
二叉树同构判别

int main()
{
    Tree R1,R2;
    R1=BuildTree(T1);
    R2=BuildTree(T2);
    if(Isomorphic(R1,R2))printf("Yes\n");
    else printf("No\n");
    return 0;
}

建立二叉树

Tree BuildTree(struct TreeNode T[])
{
    int i,N,check[N];
    Tree cl,cr,Root;
    scanf("%d\n",&N);
    if(N)
    {
        for(i=0;i<N;i++)check[i]=0;         //check数组用来判别结点是否有其他结点指向
        for(i=0;i<N;i++)
        {
            scanf("%c %c %c\n",&T[i].Element,&cl,&cr);
            if(cl!='-')
            {
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            }
            else T[i].Left=Null;
            if(cr!='-')
            {
                T[i].Right=cr-'0';
                check[T[i].Right]=1;
            }
            else T[i].Right=Null;
        }
        for(i=0;i<N;i++)if(!check[i])break;
        Root=i;                             //T[i]没有任何一个结点的Left(cl)和Right(cr)指向，因此为根结点
    }
    return Root;
}

判别二叉树同构

int Isomorphic(Tree R1,Tree R2)
{
    if((R1==Null)&&(R2==Null))return 1;
    //两树(子树)均为空
    if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))return 0;
    //其中一棵树(子树)为空
    if(T1[R1].Element!=T2[R2].Element)return 0;
    //根不同
    if((T1[R1].Left==Null)&&(T2[R2].Left==Null))return Isomorphic(T1[R1].Right,T2[R2].Right);
    //都没有左子树
    if(((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&&((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)))
        return (Isomorphic(T1[R1].Left,T2[R2].Left)&&Isomorphic(T1[R1].Right,T2[R2].Right));
    //左右不需要交换的情况
    else return (Isomorphic(T1[R1].Left,T2[R2].Right)&&Isomorphic(T1[R1].Right,T2[R2].Left));
    //左右需要交换的情况
}

判断是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树，然而一棵给定的二叉搜索树却可以有多种不同的插入序列得到

如：按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树，都能得到同样的结果

对于输入的各种插入序列，需要判断它们是否能生成相同的二叉搜索树

输入样例

输出样例

YES 
NO          
NO

求解思路

两个序列是否对应相同二叉搜索树的三种判别方法

根据两个序列分别建两颗二叉搜索树的判别方法
- 根据两个序列分别建二叉搜索树，在判别二叉搜索树是否相同
不建树的判别方法
- 如：序列3 1 2 4和序列3 4 1 2的构造均为{1 2} 3 {4}
- 序列3 1 2 4和序列3 2 4 1的构造则为{2,1} 3 {4}
只建一棵二叉搜索树，再判断其他序列是否与该二叉搜索树一致

考虑使用第三种方法，求解思路为：

二叉搜索树表示
建二叉搜索树T
判别一序列是否与二叉搜索树T一致

二叉搜索树表示

typedef struct TreeNode *Tree;
struct TreeNode
{
    Tree Left,Right;
    int v,flag;
};

程序框架搭建

int main()
{
    读入数据N和L
    根据读入第一行输入序列建树T
    依据树T分别判断后面的L个序列是否能与T形成同一搜索树并输出结果
}

需要设计的主要函数

读数据并建搜索树
判别一序列时候与T构成一样的搜索树

int main()
{
    int N,L,i;
    Tree T;
    scanf("%d",&N);
    while(N)                                    //当基准序列长度不为0时
    {
        scanf("%d",&L);
        T=MakeTree(N);                          //建基准二叉树
        for(i=0;i<L;i++)                        //读L个序列，分别进行比较
        {
            if(Judge(T,N))printf("Yes\n");
            else printf("No\n");
            ResetT(T);                          //一个序列比较之后，将T中的标记重置
        }
        FreeTree(T);                            //L个序列均比较完成后，释放掉基准树
        scanf("%d",&N);                         //每次循环最后更新基准序列长度，当输入序列长度为0时跳出循环
    }
    return 0;
}

建立二叉搜索树

Tree MakeTree(int);
Tree Insert(Tree,int);
Tree NewNode(int);
Tree MakeTree(int N)
{
    Tree T;
    int i,V;
    scanf("%d",&V);
    T=NewNode(V);
    for(i=1;i<N;i++)
    {
        scanf("%d",&V);
        T=Insert(T,V);
    }
    return T;
}
Tree Insert(Tree T,int V)
{
    if(!T)T=NewNode(V);
    else if(V<T->v)T->Left=Insert(T->Left,V);
    else if(V>T->v)T->Right=Insert(T->Right,V);
    return T;
}
Tree NewNode(int V)
{
    Tree T=(Tree)malloc(sizeof(struct TreeNode));
    T->v=V;
    T->Left=T->Right=NULL;
    T->flag=0;
    return T;
}

判别序列与二叉搜索树是否一致
方法：在树T中依次搜索输入序列中所有的元素

如果每次搜索所经过的结点在前面均出现过，则一致
否则(存在某次搜索中遇到前面未出现的结点)，则不一致

int check(Tree T,int V)          //搜索序列的一个元素
{
    if(T->flag)                  //如果flag=1，继续递归搜索
    {
        if(V<T->v)return check(T->Left,V);
        else if(V>T->v)return check(T->Right,V);
        else return 0;          //这种情况说明数据重复了
    }
    else                        //如果flag=0，检查是否是当前输入元素，如果是则结束查找并将元素标记为查找过
    {                           //如果不是当前元素，则说明序列与基准树不是同一棵二叉搜索树
        if(V==T->v)
        {
            T->flag=1;
            return 1;
        }
        else return 0;
    }
    return 0;
}
int judge(Tree T,int N)         //这个版本有bug：当发现序列中某个数与T不一致，judge函数会直接返回，这轮输入序列的读取就停止了
{                                            //而这一轮输入序列剩下的数会被当作是下一轮的输入，导致程序会出错
    int i,V;
    scanf("%d",&V);             //先判断一下根
    if(V!=T->v)return 0;
    else T->flag=1;
    for(i=1;i<N;i++)
    {
        scanf("%d",&V);
        if(!check(T,V))return 0;//依次检查输入序列的元素，
    }
    return 1;
}
int judge(Tree T,int N)         //更正版本
{
    int i,V,flag=0;             //flag=0代表目前序列与基准树还一致，1代表已经不一致
    scanf("%d",&V);
    if(V!=T->v)flag=1;
    else T->flag=1;
    for(i=1;i<N;i++)
    {
        scanf("%d",&V);       
        if(!check(T,V)&&(!flag))flag=1;  //此时发现序列与基准情况不一致，程序唯一的工作就是将输入读完
    }
    if(flag)return 0;
    return 1;
}

清除T中各结点的flag标记，准备比较下一个输入序列

与遍历原理相同，需要注意的是要对结点进行操作，所以不能遍历到结点为空再停止

void ResetT(Tree T)
{
    if(T->Left)ResetT(T->Left);
    else if(T->Right)ResetT(T->Right);
    T->flag=0;
}

释放T的空间

void FreeTree(Tree T)
{
    if(T->Left)ResetT(T->Left);
    else if(T->Right)ResetT(T->Right);
    free(T);
}