Isomorphism in N-ary trees

Isomorphism is defined as two trees having the same or mirrored structure. In the case of a mirror structure, the left node's data will always match the right node. For example, we will take a number that is the closest mirror image and see what its inverse is, which is the true concept of isomorphism.

In this article, we will check whether two different binary trees are isomorphic.

Let us take the isomorphism of N-ary tree as an example-

Please note that L represents the left node and R represents the right node

Mirror structure of P and Q trees in the second leftmost partition on the left

These two diagrams show how they are isomorphic to each other by giving four matching conditions (root nodes of P and Q).

• Left-left nodes can match.

• Either can match right-right nodes.

• Both the left and right nodes can be matched.

• Either right or left cannot match.

grammar

The following syntax is used in the program −

struct name_of_structure{
   data_type var_name;   
   // data member or field of the structure.
}

parameter

• struct − This keyword is used to represent the structure data type.

• name_of_structure − We provide any name for the structure.

• A structure is a collection of various related variables in one place.

algorithm

• We will start the program with a header file called 'iostream'.

• We are creating a structure called 'tree_node' containing an integer type 'd' and an initialized pointer variable - 'l' and 'r', respectively represent the data of the left and right child nodes.

• Now we create another structure using a function called 'create_node()' which accepts a parameter called 'data' to specify the root The value of the node. At the same time, we create a pointer named 'tree_node' and use the given data to initialize the left and right child node pointers to null and return the root node. Using this function, we will insert the node of left child node and right child node.

• We are creating a function called 'check_isomorphism_tree which uses the boolean data type, taking two tree_node pointers p and q as input parameter and returns a Boolean value. In it, we create an "if statement" twice to check if the data in p is equal to the data in q.

• Check if both p and q are null, if so, return true because the tree is isomorphic.

• Check if either p or q is null, and if so, return false because the two trees are not isomorphic.

• In the 'check_isomorphism_tree' function, we use the logical operators "&&" and "||" to recursively check the nodes 'p' and 'q All possible combinations of left and right child nodes of '.

• We start from the main function and create two tree nodes "p" and "q" to provide information.

• In the main function, we call the 'check_isomorphism_tree' function using an if statement and pass the given parameters p and q to verify whether these integer values ​​are isomorphic. If they are isomorphic, the print statement is "This given node information will generate an isomorphic tree", otherwise the opposite is true.

The Chinese translation of

Example

is:

Example

In this program, we will check whether two binary trees are isomorphic.

#include<iostream>
using namespace std;
struct tree_node{
   int d;
   tree_node*l;  // l = left
   tree_node*r;  // r = right
};
struct tree_node* create_node(int data){
   struct tree_node*root= new tree_node;
   root->d= data;
   root->l= NULL;
   root->r= NULL;
   return root;    
}
bool check_isomorphism_tree(tree_node*p, tree_node*q)  {
// p and q both are different tree
   if(p==NULL and q==NULL){
      return true;
   }
   if(p==NULL or q==NULL){
      return false;
   }
   // return all the possible condition 
   return (p->d==q->d && ((check_isomorphism_tree(p->l,q->r)&& check_isomorphism_tree(p->r,q->l))||(check_isomorphism_tree(p->l,q->l)&& check_isomorphism_tree(p->r,q->r))));
}
int main(){
   // Tree of root p
	struct tree_node *p = create_node(10); 
   p->l  = create_node(5); 
   p->r = create_node(4); 
   p->l->l = create_node(11); 
   p->r->r = create_node(12);
   p->l->r = create_node(51); 
   p->r->l = create_node(6); 
   p->l->r->l = create_node(7); // left->right->left
   p->l->l->l = create_node(9); // left->left->left
   // Tree of root q
   struct tree_node *q = create_node(10); 
   q->l  = create_node(5); 
   q->r = create_node(4); 
   q->l->l = create_node(11); 
   q->r->r = create_node(12);
   q->l->r = create_node(51); 
   q->r->l = create_node(6); 
   q->l->r->l = create_node(7); 
   q->l->l->l = create_node(9);
   if(check_isomorphism_tree(p,q)){
      cout<<"This given information of node will make isomorphism tree"<<endl;
   } else {
      cout<<" This given information of node will not make isomorphism tree "<<endl;
   }
   return 0;
}

Output

This given information of node will make isomorphism tree

in conclusion

In this program, we understand the concept of isomorphism in N-ary trees. We saw how to use structures to represent tree nodes, and to build trees using left-left nodes, right-left nodes, left-right-left nodes, etc. The following operations help satisfy the isomorphic nature of trees.

The above is the detailed content of Isomorphism in N-ary trees. For more information, please follow other related articles on the PHP Chinese website!