Basic experiment 4-2.1 isomorphism of trees

Give two trees T1 and T2. If T1 can be changed into T2 through several child exchanges, we call the two trees "isomorphic". For example, the two trees given in Figure 1 are isomorphic, because after we exchange the left and right children of nodes A, B and G of one tree, we get another tree. Figure 2 is not isomorphic.
Figure 1 (isomorphism)

Figure 2 (non isomorphism)

Basic experiment 4-2.1 isomorphism of tree (25 points)

algorithm analysis

For the binary tree algorithm, I summed up two very important ideas in the process of doing the problem.

1. The recursive definition of the tree itself leads to the degradation analysis and generalization verification method.
2. "Sentinel" thought.

Degradation analysis, generalization, verification

Since the tree itself is recursively defined, the algorithm required by the hypothesis problem is in the complex tree T T If it is established on T, then for T T Every subtree of T must be established. More popularly, any tree that meets the conditions of the topic must also be established, even if that tree can not be simplified any more.
  let's use this topic as an example to describe in detail how to analyze and verify.

analysis

First, we draw an extremely degenerate tree to study the isomorphism condition in the topic. What is the degradation? As shown in the figure below, there are only two nodes in the tree.

[the external link image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-JBp9CJCK-1620786816455)(/img/bVbKr4D "image.png")]

Obviously, the binary tree of two nodes is only in the above two cases when the data field of the node is not considered. There are only two cases of isomorphism.

First case
  for the binary tree on the left of the graph T _ 1 T\_1 T_1. It must be isomorphic with itself. Similarly, for the binary tree on the right of the graph T _ 2 T\_2 T_2. It is also isomorphic with itself. According to the recursive nature of binary tree, all its subtrees must also be isomorphic with themselves.

The second case
  another situation, we found, T _ 1 T\_1 T_1 and T _ 2 T\_2 T_2 is also isomorphic. Namely T _ 1 T\_1 T_ Left subtree of 1 and T _ 2 T\_2 T_ Right subtree isomorphism of 2, T _ 1 T\_1 T_ Right subtree of 1 (null) and T _ 2 T\_2 T_ The left subtree (null) of 2 is isomorphic.

Through the analysis of two node binary tree, we find the condition of isomorphism. Namely:

1. Two trees T _ 1 T\_1 T_1 and T _ 2 T\_2 T_2. The data fields of the current node are equal.
2. T _ 1 T\_1 T_ Left subtree of 1 and T _ 2 T\_2 T_ Left subtree isomorphism of 2, T _ 1 T\_1 T_1 right subtree and T _ 2 T\_2 T_2 right subtree isomorphism.
3. T _ 1 T\_1 T_ Left subtree of 1 and T _ 2 T\_2 T_ Right subtree isomorphism of 2, T _ 1 T\_1 T_1 right subtree and T _ 2 T\_2 T_2 left subtree isomorphism.

As long as the conditions are met, Kate parse error: expected 'EOF', got '&' at position 4: 1\& ̲\& 2 or KAtex parse error: expected 'EOF', got '&' at position 4: 1\& ̲\& The two trees are isomorphic.
  therefore. By simplifying the form of binary tree, we can intuitively and quickly analyze a row and effective algorithm (regardless of performance).

Generalization verification

Then we can bring our algorithm into a more complex binary tree for verification to see if we can get a counterexample. Recently, we are busy reviewing the postgraduate entrance examination. Time is limited. This step is left to you to try.

Sentinel thought

There is another small detail in the previous step. I don't know if you have noticed it. In the second case, if a subtree is empty, we don't judge it. We only default that the empty subtree is isomorphic, that is, null is isomorphic to null.
  this idea brings great convenience to our code implementation. We don't need to judge whether it is a leaf node or not, and we don't need to tangle with the fact that the current node doesn't have a special case to deal with when recursing. Instead, we use a logical "sentry" to judge.
The concept of "sentinel" is used in many classic algorithms. For example, quick sorting, KMP algorithm, etc. Using sentinel flexibly helps to simplify the implementation of our recursive algorithm.

Input processing

In addition, there is a small trap in this problem, that is, the input data is not given in the order of front, middle and back or hierarchical traversal. It should be given randomly. We need to find the root node in the input data.
  because it is a tree structure, we know that a tree is a semi linear structure, and each node has 1 1 1 to n n n successors, but each node has at most 1 1 1 precursor. That is, except for the root node, the penetration of each node is 1 1 1. In other words, except for the root node, each node has a pointer or reference to it. So we can judge which is the root node by counting the penetration or the reference to the node. The only thing that is not pointed to is the root node.

code

#include <stdio.h>

typedef struct Node{
    char c;
    int lchild;
    int rchild;
}BTNode;

int input_tree(int n, BTNode node[]);

/*
   @params node1 Tree 1, node2, tree 2, i, subscript of current node of tree 1, subscript of current node of j tree 2 
   @return Isomorphism returns 1, otherwise it returns 0 
*/
int is_same(BTNode node1[], BTNode node2[], int i, int j);

int main(){
    BTNode node1[11]={0}, node2[11]={0};
    int n;
    scanf("%d", &n);
    int root1 = input_tree(n, node1); //Read in the tree and return the subscript of the tree root 
    scanf("%d", &n);
    int root2 = input_tree(n, node2);
    int ans = is_same(node1, node2, root1, root2); //Judge whether node1 and node2 are isomorphic 
    if(ans == 1) printf("Yes\n");
        else printf("No\n");
    return 0;
}

int input_tree(int n, BTNode node[]){
    char ch, lc, rc;
    int a[11]={0};
    for(int i=0; i<n; i++){
        scanf(" %c %c %c", &ch, &lc, &rc);
        node[i].c = ch;
        node[i].lchild = -1;
        node[i].rchild = -1;
        if (lc != '-'){
            node[i].lchild = lc - 48; // The ascii code of the number minus 48 is the value of the number 
            a[lc-48] = 1;
        }
        if (rc != '-'){
            node[i].rchild = rc - 48;
            a[rc-48] = 1;
        }
    }
    int root = -1;
    for(int i=0; i<n; i++){ // a the subscript of the array with 0 is the subscript of the root node 
          if(a[i]==0){
              root = i;
              break;
          }
    }
    return root;
}

int is_same(BTNode node1[], BTNode node2[], int i, int j){
    if ((i == -1 && j != -1) || (i == -1 && j != -1)) return 0; //Null on one side and non null on the other 
    if(i==-1 && j==-1) return 1; //The current nodes are null 
    if (node1[i].c != node2[j].c) return 0; //Unequal characters 
    int ll = is_same(node1, node2, node1[i].lchild, node2[j].lchild); //Left and left isomorphism 
    int rr = is_same(node1, node2, node1[i].rchild, node2[j].rchild); //Right and right isomorphism
    int lr = is_same(node1, node2, node1[i].lchild, node2[j].rchild); //Left and right isomorphism 
    int rl = is_same(node1, node2, node1[i].rchild, node2[j].lchild); //Right and left isomorphism
    if((ll==1 && rr==1) || (lr==1 && rl==1)) return 1; // Left left right right isomorphism or left right left isomorphism, then subtree isomorphism 
    else return 0;
}