C语言判断两字符串同构,c语言实现判断两颗树是否同构
在本題中認(rèn)為如果兩個(gè)樹左右子樹交換可以相同，也被認(rèn)為是同構(gòu)樹。
對(duì)應(yīng)輸入格式為：4(總結(jié)點(diǎn)數(shù))
A - 1
B 2 3
C - -
D - -
#include
#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;//為了標(biāo)記根節(jié)點(diǎn) ，因?yàn)闆]有節(jié)點(diǎn)指向根節(jié)點(diǎn)
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++)//遍歷找到根節(jié)點(diǎn)
if(Check[i] == 0)
break;
Root = i;
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;
//兩樹的根節(jié)點(diǎn)不一樣
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);
//若兩樹的左子樹不空，并且左子樹的結(jié)點(diǎn)元素都一樣，判斷左右子樹是否一樣
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
//否則 判斷兩樹是否同構(gòu)
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;
}
總結(jié)
以上是生活随笔為你收集整理的C语言判断两字符串同构,c语言实现判断两颗树是否同构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
