网站做的一样侵权吗,学院网站建设的目的,广州海珠区赤岗 新港网站建设公司,高质量的合肥网站建设给定两棵树 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2#xff0c;则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的#xff0c;因为我们把其中一棵树的结点A、B、G的左右孩子互换后#xff0c;就得到另外一棵树。而图2就不是同构的。 图一…给定两棵树 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的因为我们把其中一棵树的结点A、B、G的左右孩子互换后就得到另外一棵树。而图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 对于每棵树其节点的数量、层次结构和连接关系必须完全一致。如果树上的节点带有特定的标签或值则这些标签也必须一一对应相等。 既然判断树的同构那我们就应该先构建一个树形结构 typedef struct tree
{char data; // 节点数据int left; // 左子节点索引int right; // 右子节点索引
} tree; 声明了两个全局数组T1和T2以及一个检查数组check用于存储两棵树的节点信息和标记哪些节点已经被访问过。 // 全局数组用于存放两个树的节点信息
tree T1[MAXTREE], T2[MAXTREE];
// 检查数组用于标记已访问过的节点
int check[MAXTREE]; 构建树的函数 (buildTree()): 接受一个指向tree结构体数组的指针参数t用于接收用户输入并构建树。用户需要输入节点总数然后依次输入每个节点的数据及其左右孩子的索引。函数通过遍历输入的节点信息填充tree结构体数组并找到根节点的索引后返回。 判断两棵树是否同构的函数 (Isomorphism()): 这是一个递归函数接受两个参数分别为两棵树的根节点索引。通过对比两棵树的各个节点数据和子节点结构确定它们是否同构。 // 构建树的函数
int buildTree(tree* t);
// 判断两棵树是否同构的递归函数
int Isomorphism(int root1, int root2); 主函数调用buildTree函数构建树形结构 int main()
{int r1, r2;// 分别构建两棵树r1 buildTree(T1);r2 buildTree(T2);// 如果两棵树同构打印Yesif (Isomorphism(r1, r2)) {printf(Yes\n);}// 否则打印Noelse{printf(No\n);}return 0;
} 构建树的函数 int buildTree(tree* t)
{int root null, i;int n;char cleft, cright;// 输入节点数量scanf(%d, n);// 如果节点数量大于零if (n 0){// 初始化检查数组memset(check, 0, sizeof(check));// 遍历所有节点输入节点数据及左右子节点索引for (i 0; i n; i){// 忽略换行符getchar();// 输入当前节点的数据及左右子节点索引scanf(%c %c %c, t[i].data, cleft, cright);// 处理左子节点if (cleft! -) {t[i].left cleft - 0; // 将字符形式的索引转为整数check[t[i].left] 1; // 标记此子节点已被访问} else t[i].left null; // 空节点// 处理右子节点if (cright! -) {t[i].right cright - 0; // 将字符形式的索引转为整数check[t[i].right] 1; // 标记此子节点已被访问} else {t[i].right null; // 空节点}}// 找到根节点for (i 0; i n; i){//没有被访问过if (!check[i]) {break;}}// 返回根节点索引root i;}// 返回根节点索引return root;
} memset(check, 0, sizeof(check)); 这里使用memset函数清空check数组准备记录哪些节点已经被访问过。 下面是判断两棵树是否同构的算法 int Isomorphism(int root1, int root2)
{// 如果两个根节点都为空返回真if (root1 null root2 null){return 1;}// 如果两个根节点不都为空else{// 如果只有一个根节点为空返回假if (root1 null root2! null || root1! null root2 null){return 0;}else{// 如果两个根节点都不为空且数据不同返回假if (T1[root1].data! T2[root2].data){return 0;}// 如果两个根节点数据相同继续比较子节点else{// 如果两个根节点都没有左子节点只比较右子节点if (T1[root1].left null T2[root2].left null){return Isomorphism(T1[root1].right, T2[root2].right);}// 如果两个根节点都有左子节点且数据相同分别比较左右子节点else{if (T1[root1].left! null T2[root2].left! null T1[T1[root1].left].data T2[T2[root2].left].data){return Isomorphism(T1[root1].left, T2[root2].left) Isomorphism(T1[root1].right, T2[root2].right);}// 如果两个根节点都有左子节点但数据不同交换左右子节点进行比较else{return Isomorphism(T1[root1].right, T2[root2].left) Isomorphism(T1[root1].left, T2[root2].right);}}}}}
} 完整代码附上 #include stdio.h
#include string.h// 定义最大树的大小
#define MAXTREE 10
// 定义空节点的标识
#define null -1// 树结构体
typedef struct tree
{char data; // 节点数据int left; // 左子节点索引int right; // 右子节点索引
} tree;// 全局数组用于存放两个树的节点信息
tree T1[MAXTREE], T2[MAXTREE];
// 检查数组用于标记已访问过的节点
int check[MAXTREE];// 构建树的函数
int buildTree(tree* t);
// 判断两棵树是否同构的递归函数
int Isomorphism(int root1, int root2);int main()
{int r1, r2;// 分别构建两棵树r1 buildTree(T1);r2 buildTree(T2);// 如果两棵树同构打印Yesif (Isomorphism(r1, r2)) {printf(Yes\n);}// 否则打印Noelse{printf(No\n);}return 0;
}// 构建树的函数实现
int buildTree(tree* t)
{int root null, i;int n;char cleft, cright;// 输入节点数量scanf(%d, n);// 如果节点数量大于零if (n 0){// 初始化检查数组memset(check, 0, sizeof(check));// 遍历所有节点输入节点数据及左右子节点索引for (i 0; i n; i){// 忽略换行符getchar();// 输入当前节点的数据及左右子节点索引scanf(%c %c %c, t[i].data, cleft, cright);// 处理左子节点if (cleft! -) {t[i].left cleft - 0; // 将字符形式的索引转为整数check[t[i].left] 1; // 标记此子节点已被访问} else t[i].left null; // 空节点// 处理右子节点if (cright! -) {t[i].right cright - 0; // 将字符形式的索引转为整数check[t[i].right] 1; // 标记此子节点已被访问} else {t[i].right null; // 空节点}}// 找到根节点for (i 0; i n; i){//没有被访问过if (!check[i]) {break;}}// 返回根节点索引root i;}// 返回根节点索引return root;
}// 判断两棵树是否同构的递归函数实现
int Isomorphism(int root1, int root2)
{// 如果两个根节点都为空返回真if (root1 null root2 null){return 1;}// 如果两个根节点不都为空else{// 如果只有一个根节点为空返回假if (root1 null root2! null || root1! null root2 null){return 0;}else{// 如果两个根节点都不为空且数据不同返回假if (T1[root1].data! T2[root2].data){return 0;}// 如果两个根节点数据相同继续比较子节点else{// 如果两个根节点都没有左子节点只比较右子节点if (T1[root1].left null T2[root2].left null){return Isomorphism(T1[root1].right, T2[root2].right);}// 如果两个根节点都有左子节点且数据相同分别比较左右子节点else{if (T1[root1].left! null T2[root2].left! null T1[T1[root1].left].data T2[T2[root2].left].data){return Isomorphism(T1[root1].left, T2[root2].left) Isomorphism(T1[root1].right, T2[root2].right);}// 如果两个根节点都有左子节点但数据不同交换左右子节点进行比较else{return Isomorphism(T1[root1].right, T2[root2].left) Isomorphism(T1[root1].left, T2[root2].right);}}}}}
} 文章转载自： http://www.morning.njqpg.cn.gov.cn.njqpg.cn http://www.morning.rdkgw.cn.gov.cn.rdkgw.cn http://www.morning.hsrpc.cn.gov.cn.hsrpc.cn http://www.morning.rcntx.cn.gov.cn.rcntx.cn http://www.morning.rryny.cn.gov.cn.rryny.cn http://www.morning.rmqmc.cn.gov.cn.rmqmc.cn http://www.morning.rtbhz.cn.gov.cn.rtbhz.cn http://www.morning.dfqmy.cn.gov.cn.dfqmy.cn http://www.morning.xcjbk.cn.gov.cn.xcjbk.cn http://www.morning.nwfxp.cn.gov.cn.nwfxp.cn http://www.morning.spdyl.cn.gov.cn.spdyl.cn http://www.morning.mjats.com.gov.cn.mjats.com http://www.morning.nqlnd.cn.gov.cn.nqlnd.cn http://www.morning.dwxqf.cn.gov.cn.dwxqf.cn http://www.morning.ygflz.cn.gov.cn.ygflz.cn http://www.morning.yxzfl.cn.gov.cn.yxzfl.cn http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.rhnn.cn.gov.cn.rhnn.cn http://www.morning.gmysq.cn.gov.cn.gmysq.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.yrsg.cn.gov.cn.yrsg.cn http://www.morning.fhqdb.cn.gov.cn.fhqdb.cn http://www.morning.qrsrs.cn.gov.cn.qrsrs.cn http://www.morning.qfmns.cn.gov.cn.qfmns.cn http://www.morning.rqqlp.cn.gov.cn.rqqlp.cn http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.c7622.cn.gov.cn.c7622.cn http://www.morning.bpmdq.cn.gov.cn.bpmdq.cn http://www.morning.krswn.cn.gov.cn.krswn.cn http://www.morning.wcjk.cn.gov.cn.wcjk.cn http://www.morning.wktbz.cn.gov.cn.wktbz.cn http://www.morning.sqyjh.cn.gov.cn.sqyjh.cn http://www.morning.wqbrg.cn.gov.cn.wqbrg.cn http://www.morning.wkmyt.cn.gov.cn.wkmyt.cn http://www.morning.wclxm.cn.gov.cn.wclxm.cn http://www.morning.fnfhs.cn.gov.cn.fnfhs.cn http://www.morning.nxzsd.cn.gov.cn.nxzsd.cn http://www.morning.zrks.cn.gov.cn.zrks.cn http://www.morning.ppdr.cn.gov.cn.ppdr.cn http://www.morning.gpnfg.cn.gov.cn.gpnfg.cn http://www.morning.rshijie.com.gov.cn.rshijie.com http://www.morning.ghpld.cn.gov.cn.ghpld.cn http://www.morning.thpzn.cn.gov.cn.thpzn.cn http://www.morning.sknbb.cn.gov.cn.sknbb.cn http://www.morning.yrgb.cn.gov.cn.yrgb.cn http://www.morning.smkxm.cn.gov.cn.smkxm.cn http://www.morning.wdxr.cn.gov.cn.wdxr.cn http://www.morning.pfntr.cn.gov.cn.pfntr.cn http://www.morning.nrmyj.cn.gov.cn.nrmyj.cn http://www.morning.blfgh.cn.gov.cn.blfgh.cn http://www.morning.jrqw.cn.gov.cn.jrqw.cn http://www.morning.bchgl.cn.gov.cn.bchgl.cn http://www.morning.qblcm.cn.gov.cn.qblcm.cn http://www.morning.cprls.cn.gov.cn.cprls.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.nnwpz.cn.gov.cn.nnwpz.cn http://www.morning.cwyrp.cn.gov.cn.cwyrp.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.mgnrc.cn.gov.cn.mgnrc.cn http://www.morning.zrdhd.cn.gov.cn.zrdhd.cn http://www.morning.lbcbq.cn.gov.cn.lbcbq.cn http://www.morning.ntzfl.cn.gov.cn.ntzfl.cn http://www.morning.fhjnh.cn.gov.cn.fhjnh.cn http://www.morning.zyndj.cn.gov.cn.zyndj.cn http://www.morning.zfrs.cn.gov.cn.zfrs.cn http://www.morning.tphjl.cn.gov.cn.tphjl.cn http://www.morning.gqfjb.cn.gov.cn.gqfjb.cn http://www.morning.nwclg.cn.gov.cn.nwclg.cn http://www.morning.bfsqz.cn.gov.cn.bfsqz.cn http://www.morning.taojava.cn.gov.cn.taojava.cn http://www.morning.fqhbt.cn.gov.cn.fqhbt.cn http://www.morning.nypsz.cn.gov.cn.nypsz.cn http://www.morning.pakistantractors.com.gov.cn.pakistantractors.com http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.xdqrz.cn.gov.cn.xdqrz.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.kdgcx.cn.gov.cn.kdgcx.cn http://www.morning.rbjth.cn.gov.cn.rbjth.cn http://www.morning.pwhjr.cn.gov.cn.pwhjr.cn
