7-2 树的同构 (25 分)
本文最后更新于1783天前,其中的信息可能已经有所发展或是发生改变。

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

图1

图2现给定两棵树,请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N−1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的,输出“Yes”,否则输出“No”。

输入样例1(对应图1):

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 -

输出样例1:

Yes

输入样例2(对应图2):

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

输出样例2:

No

代码:(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
#define Max_Node 11
#define END -1
 
typedef struct node
{
    char value;
    int left;
    int right;
}Node;
 
void CreateTree(vector<Node>& Tree,int N)//获取树的输入,并将输入的字符合理转化成整型数字
{
    
    char value,left,right;
    for (int i=0; i<N; ++i)
    {
        cin>>value>>left>>right;
        Tree[i].value=value;
        
        if (left=='-')
        {
            Tree[i].left=END;
        }else
        {
            Tree[i].left=left-'0';
        }
        
        if (right=='-')
        {
            Tree[i].right=END;
        }else
        {
            Tree[i].right=right-'0';
        }
    }
}
 
int FindTreeRoot(vector<Node>& Tree,int N)//寻找树的树根(树根没有其它的结点指向它)
{
    int Flag[Max_Node];
    for (int i=0; i<N; ++i)
    {
        Flag[i]=0;
    }
    
    for (int i=0; i<N; ++i)
    {
        if (Tree[i].left!=END)
        {
            Flag[Tree[i].left]=1;
        }
        if (Tree[i].right!=END)
        {
            Flag[Tree[i].right]=1;
        }
    }
    
    int k;
    for (k=0; k<N; ++k)
    {
        if (Flag[k]==0)
        {
            break;
        }
    }
    return k;
}
 
bool IsOmorphic(int Root1,int Root2,vector<Node>& Tree1,vector<Node>& Tree2)//递归判断两树是否同构
{
    if (Tree1[Root1].value==Tree2[Root2].value)
    {
        //两结点相等,并都是叶子结点
        if (Tree1[Root1].left==END && Tree1[Root1].right==END && Tree2[Root2].left==END && Tree2[Root2].right==END)
        {
            return true;
        }
        
        //以下四种情况都是,两个结点都是有一个孩子为空,另一个子树不空且这两个孩子相等的情形
        if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].right==END && Tree2[Root2].right==END)
        {
            return IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2);
        }
        if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].right==END && Tree2[Root2].left==END)
        {
            return IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2);
        }
        if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].left==END && Tree2[Root2].right==END)
        {
            return IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2);
        }
        if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].left==END && Tree2[Root2].left==END)
        {
            return IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2);
        }
        
        //以下两种情形,两个结点的孩子都相等
        if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value)
        {
            return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2));
        }
        if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value)
        {
            return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2));
        }
    }
    //不符合以上7种情况的其它情况都说明这两棵树不同构
    return false;
}
 
int main(int argc, const char * argv[])
{
    //Input
    int N1=0;
    cin>>N1;
    vector<Node> Tree1(Max_Node);
    CreateTree(Tree1,N1);
    int N2=0;
    cin>>N2;
    vector<Node> Tree2(Max_Node);
    CreateTree(Tree2,N2);
    
    
    if (N1!=N2)
    {
        cout<<"No";
    }else
    {
        if (N1==0)
        {
            cout<<"Yes";
        }else
        {
           
    
            //Build Tree
            int root1=FindTreeRoot(Tree1,N1);
            int root2=FindTreeRoot(Tree2,N2);
    
            //Judge
            if (IsOmorphic(root1, root2, Tree1, Tree2))
            {
                cout<<"Yes";
            }else
            {
                cout<<"No";
            }
        }
    
    }
    return 0;
}

 

点击数:105

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇