小白专场-树的同构-c语言实现.md

概述目录 一、题意理解 二、求解思路 2.1 二叉树表示 2.2 程序框架搭建 2.3 如何建二叉树 2.4 如何判别两二叉树同构 更新、更全的《数据结构与算法》的更新网站，更有python、go、人工智能教学等着你：https://www.cnblogs.com/nickchen121/p/11407287.html 一、题意理解 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，

目录

一、题意理解 二、求解思路 2.1 二叉树表示 2.2 程序框架搭建 2.3 如何建二叉树 2.4 如何判别两二叉树同构

更新、更全的《数据结构与算法》的更新网站，更有python、go、人工智能教学等着你：https://www.cnblogs.com/nickchen121/p/11407287.html

一、题意理解

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

输入格式：输入给出2棵二叉树的信息：

先在一行中给出该树的结点树，随后N行

第i行对应编号第i个结点，给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的编号

如果孩子结点为空，则在相应位置给出“-”

如下图所示，有多种表示的方式，我们列出以下两种：

二、求解思路 二叉树表示 建二叉树 同构判别 2.1 二叉树表示

结构数组表示二叉树：静态链表

/* c语言实现 */#define MaxTree 10#define ElementType char#define Tree int#define Null -1struct TreeNode{  ElementType Element;  Tree left;  Tree Right;} T1[MaxTree],T2[MaxTree];

2.2 程序框架搭建

需要设计的函数：

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

/* c语言实现 */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;}

2.3 如何建二叉树

/* c语言实现 */Tree BuildTree(struct TreeNode T[]){  ...;  scanf("%d\n",&N); // 输入需要建立树的长度  if (N) {    ...;    for (i=0; i<N; i++) {      scanf("%c %c %c\n",&T[i].Element,&cl,&cr);      ...;    }    ...;    Root = ??? // 可以通过T[i]中没有任何结点的left(cl)和right(cr)指向他这个条件获取。  }  return Root;}

/* c语言实现 */Tree BuildTree(struct TreeNode T[]){  ...;  scanf("%d\n",&N); // 输入需要建立树的长度  if (N) {    for (i=0; i<N; i++) check[i] = 0;    for (i=0; i<N; i++) {      scanf("%c %c %c\n",&cr);      if (cl != '-'){        T[i].left = cl-'0';        check[T[i].left] = 1;      }      else T[i].left = Null;      ...;  // 对cr的对应处理    }    for (i=0; i<N; i++)      if (!check[i]) break;    Root = i; // 可以通过T[i]中没有任何结点的left(cl)和right(cr)指向他这个条件获取。  }  return Root;}

2.4 如何判别两二叉树同构

/* c语言实现 */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));  }}

总结

以上是内存溢出为你收集整理的小白专场-树的同构-c语言实现.md全部内容，希望文章能够帮你解决小白专场-树的同构-c语言实现.md所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。