二叉树的同构判断

小鱼儿 2023-07-02 11:30 136阅读 0赞

一 题意理解  
给定两颗树，T1，T2，若T1可以通过若干次的左右子互换变成T2，则称为这两棵树同构。

二 输入数据  
先输入一个N，代表接下来的个数，然后輸入N组元素，分别为节点名称，其左子的序号，右子的序号，若其不存在左子或右子，则输入"-"。  
例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]  
解题思路  
1 二叉树表示  
2 建二叉树  
3 同构判断

1二叉树表示：  
用结构数组表示二叉树（静态链表）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]  
设置数据结构：

struct treenode
    {
        
        char element;
        int left;
        int right;
    }T1[10],T2[10];

二 程序框架搭建  
int main()  
\{建二叉树一  
建二叉树二  
判断是否同构并输出  
\}

建二叉树函数写法：  
将所有有节点指向的数字排除，没有被指过的节点则为根节点，因为其它的节点都被指过。

tree buildtree(struct treenode T[])
    {
        
        int N,i,check[100],root;
        char cl,cr;
        scanf("%d\n",&N);
        if(N)
        {
        
            for(i=0;i<N;i++)check[i]=0;         //check数组的作用是找到根节点，先把基础值全改为0
            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;            //若不为空则转化为int类型，并标记该值出现过。
                }
                else T[i].left=-1;
                if(cr!='-'){
        
                    T[i].right=cr-'0';
                    check[T[i].right]=1;
                }
                else T[i].right=-1;
            }
            for(i=0;i<N;i++)
                if(!check[i]) break;
            root=i;
        }
        return root;    
    }

判断二叉树同构函数：  
需要分类讨论可能出现的多种情况

int isomorphic(tree R1,tree R2)
    {
        
        if((R1==-1)&&(R2==-1))
            return 1;              //都为空则返回真值
        if((R1==-1)&&(R2!=-1)||(R1!=-1)&&(R2==-1))
            return 0;          //一个为空，另一个不为空，则返回0
        if(T1[R1].element!=T2[R2].element)
            return 0;         //若根节点元素不一样则返回0，
        if((T1[R1].left==-1)&&(T2[R2].left==-1))
            return isomorphic(T1[R1].right,T2[R2].right);  //若左边都为空，则递归判断其右子树
        if(((T1[R1].left!=-1)&&(T2[R2].left!=-1))&&((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));   //左子元素不相等。可能是左与右相等，比较左与右，右与左的情况。
    }

完整代码：

#include <stdio.h>
    #define Tree int
    #define Null -1
    #define MAXSIZE 10
     
     
    struct Node{
        
        char Element;
        Tree Left;
        Tree Right;
    }T1[MAXSIZE], T2[MAXSIZE];
     
    Tree BuildTree(struct Node T[])
    {
        
        int N, i, Root;
        char ch, cl, cr;
        
        scanf("%d", &N);
        ch = getchar();
        
        int Check[N];
     
        for(i = 0; i < N; i++) Check[i] = 0;    //为了标记根节点 ，因为没有节点指向根节点 
        for(i = 0; i < N; i++){
        
            scanf("%c %c %c", &T[i].Element, &cl, &cr);
            ch = getchar();
            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] == 0)
                break;
            Root = i;       if(N==0)Root=-1;    
        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);              
    }
     
    int main()
    {
        
        Tree R1, R2;
        
        R1 = BuildTree(T1);
        R2 = BuildTree(T2);
        if(Isomorphic(R1, R2)) printf("Yes");   
        else
            printf("No");
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200129211041127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200129211155564.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70