同构被定义为两棵树具有相同或镜像结构。在镜像结构的情况下，左节点的数据将始终与右节点匹配。例如，我们将取一个最接近镜像的数字，看看它的反向是什么，这就是同构的真正概念。
在本文中，我们将检查两个不同的二叉树是否同构。
让我们以N叉树的同构为例-
请注意，L代表左节点，而R代表右节点
左侧最左第二分区的P和Q树的镜像结构
这两个图示展示了它们如何通过给出四个匹配条件（P和Q的根节点）来彼此同构。
左-左节点可以匹配。
要么可以匹配右-右节点。
左右节点均可匹配。
要么右左无法匹配。
语法
程序中使用了以下语法−
struct name_of_structure{
data_type var_name;
// data member or field of the structure.
}
登录后复制
参数
算法
我们将使用一个名为‘iostream’的头文件来开始程序。
我们正在创建名为‘tree_node’的结构，其中包含整数类型‘d’和初始化指针变量- ‘l’和‘r’，分别表示左右子节点的数据。
现在我们使用一个名为‘create_node()’的函数创建另一个结构，该函数接受一个名为‘data’的参数来指定根节点的值。同时，我们创建一个名为‘tree_node’的指针，并使用给定的数据来初始化左子节点和右子节点的指针为空，并返回根节点。使用这个函数，我们将插入左子节点和右子节点的节点。
我们正在创建一个名为‘check_isomorphism_tree 的函数，它使用布尔数据类型，以两个tree_node指针p和q作为输入参数，并返回一个布尔值。在其中，我们两次创建一个“if语句”来检查p中的数据是否等同于q中的数据。
在‘check_isomorphism_tree’函数中，我们使用逻辑运算符“&&”和“||”递归检查节点‘p’和‘q’的所有可能的左右子节点组合。
我们从主函数开始，创建两个树节点“p”和“q”来提供信息。
在主函数中，我们使用if语句调用‘check_isomorphism_tree’函数，并传递给定的参数p和q来验证这些整数值是否同构。如果它们是同构的，则打印语句为“这个给定的节点信息将生成同构树”，否则相反。
Example
的中文翻译为：
示例
在这个程序中，我们将检查两个二叉树是否同构。
#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;
}
登录后复制
输出
This given information of node will make isomorphism tree
登录后复制
结论
在这个程序中，我们理解了N叉树中同构的概念。我们看到了如何使用结构来表示树节点，以及使用左-左节点、右-左节点、左-右-左节点等来构建树，以下操作有助于满足树的同构性质。
以上是N元树中的同构性的详细内容。更多信息请关注PHP中文网其他相关文章！
