Isomorphisme dans les arbres N-aires-C++-php.cn

Isomorphisme dans les arbres N-aires

PHPz

Libérer： 2023-09-15 09:01:05

avant

1390 Les gens l'ont consulté

同构被定义为两棵树具有相同或镜像结构。在镜像结构的情况下，左节点的数据将始终与右节点匹配。例如，我们将取一个最接近镜像的数字，看看它的反向是什么，这就是同构的真正概念。

在本文中，我们将检查两个不同的二叉树是否同构。

让我们以N叉树的同构为例-

请注意，L代表左节点，而R代表右节点

左侧最左第二分区的P和Q树的镜像结构

这两个图示展示了它们如何通过给出四个匹配条件（P和Q的根节点）来彼此同构。

左-左节点可以匹配。
要么可以匹配右-右节点。
左右节点均可匹配。
要么右左无法匹配。

语法

程序中使用了以下语法−

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

Copier après la connexion

参数

struct − 这个关键字用于表示结构数据类型。
name_of_structure − 我们为结构提供任何名称。
结构是将各种相关变量集中在一个地方的集合。

算法

我们将使用一个名为‘iostream’的头文件来开始程序。
我们正在创建名为‘tree_node’的结构，其中包含整数类型‘d’和初始化指针变量- ‘l’和‘r’，分别表示左右子节点的数据。
现在我们使用一个名为‘create_node()’的函数创建另一个结构，该函数接受一个名为‘data’的参数来指定根节点的值。同时，我们创建一个名为‘tree_node’的指针，并使用给定的数据来初始化左子节点和右子节点的指针为空，并返回根节点。使用这个函数，我们将插入左子节点和右子节点的节点。
我们正在创建一个名为‘check_isomorphism_tree 的函数，它使用布尔数据类型，以两个tree_node指针p和q作为输入参数，并返回一个布尔值。在其中，我们两次创建一个“if语句”来检查p中的数据是否等同于q中的数据。

检查p和q是否都为null，如果是，则返回true，因为树是同构的。
检查 p 或 q 中是否有任何一个为 null，如果是，则返回 false，因为这两棵树不是同构的。

在‘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;
}

Copier après la connexion

输出

This given information of node will make isomorphism tree

Copier après la connexion

结论

在这个程序中，我们理解了N叉树中同构的概念。我们看到了如何使用结构来表示树节点，以及使用左-左节点、右-左节点、左-右-左节点等来构建树，以下操作有助于满足树的同构性质。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!