03-树1 树的同构 （C语言链表实现）

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef char ElemType; typedef struct BinTree {     ElemType data;     struct BinTree *left;     struct BinTree *right; }BinTree; bool TreeCmp(BinTree * a, BinTree * b); //判断a树与b树是否同构 BinTree * BinTree_new(int n); int main() {     int n;     scanf("%d", &n);     BinTree * a = BinTree_new(n);     scanf("%d", &n);     BinTree * b = BinTree_new(n);     bool flag = TreeCmp(a, b);     if (flag)         printf("Yes");     else         printf("No");     ; } BinTree * BinTree_new(int n) {     )     {         return  NULL;     }     else     {         int i, li, ri;         ElemType c, lc, rc;         BinTree * T = (BinTree *)malloc(n * sizeof(BinTree));         bool *head = (bool *)malloc(n * sizeof(bool));         memset(head, true ,sizeof(head));         ; i < n ; ++i )         {             scanf(" %c %c %c", &c, &lc, &rc);             li = lc-';             ri = rc-';             T[i].data = c;             if (lc != '-')             {                 T[i].left = &T[li];                 head[li] = false;             }             else                 T[i].left = NULL;             if (rc != '-')             {                 T[i].right = &T[ri];                 head[ri] = false;             }             else                 T[i].right = NULL;         }         //寻找树的树根（树根没有其它的结点指向它）         ; i < n ; ++i )             if (head[i] == true)                 break;         free(head);         return &T[i];     } } bool TreeCmp(BinTree * a, BinTree * b) {     if (a == NULL && b == NULL)//两棵树都为空         return true;     if (a == NULL || b == NULL)//有一棵树为空         return false;     if (a->data != b->data)//树结点的值不相等         return false;     if (a->left == NULL && b->left == NULL)//两棵树的左子树都为空         return TreeCmp(a->right, b->right);//就比较右子树     //两棵树的左子树都不为空，且两个值相等就比较两棵树的子树     if (a->left != NULL && b->left != NULL &&(a->left->data == b->left->data))         return (TreeCmp(a->left,b->left)&&TreeCmp(a->right,b->right));     //交换后再比较     else         return (TreeCmp(a->left,b->right)&&TreeCmp(a->right,b->left)); }