Isomorfisme dalam pokok N-ary

Isomorfisme ditakrifkan sebagai dua pokok yang mempunyai struktur yang sama atau bercermin. Dalam kes struktur cermin, data nod kiri akan sentiasa sepadan dengan nod kanan. Sebagai contoh, kita akan mengambil nombor yang merupakan imej cermin terdekat dan melihat apakah songsangnya, iaitu konsep sebenar isomorfisme.

Dalam artikel ini, kami akan menyemak sama ada dua pokok binari berbeza adalah isomorfik.

Mari kita ambil isomorfisme pokok N-ary sebagai contoh-

Sila ambil perhatian bahawa L mewakili nod kiri dan R mewakili nod kanan

Struktur cermin pokok P dan Q di sekatan kedua paling kiri di sebelah kiri

Dua rajah ini menunjukkan bagaimana ia isomorfik antara satu sama lain dengan memberikan empat keadaan padanan (nod akar P dan Q).

• Nod kiri-kiri boleh sepadan.

• Sama ada boleh memadankan nod kanan-kanan.

• Kedua-dua nod kiri dan kanan boleh dipadankan.

• Atau kanan dan kiri tidak boleh sepadan.

Tatabahasa

Sintaks berikut digunakan dalam program −

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

Parameter

• struct − Kata kunci ini digunakan untuk mewakili jenis data struktur.

• nama_struktur − Kami menyediakan sebarang nama untuk struktur tersebut.

• Sesuatu struktur ialah himpunan pelbagai pembolehubah yang berkaitan di satu tempat.

Algoritma

• Kami akan menggunakan fail pengepala dipanggil ‘iostream’ untuk memulakan program.

• Kami sedang mencipta struktur yang dipanggil 'tree_node', yang mengandungi jenis integer 'd' dan pembolehubah penunjuk yang dimulakan - 'l' dan 'r', mewakili data nod anak kiri dan kanan masing-masing.

• Sekarang kita mencipta struktur lain menggunakan fungsi yang dipanggil ‘create_node()’ yang menerima parameter yang dipanggil ‘data’ untuk menentukan nilai nod akar. Pada masa yang sama, kami mencipta penuding bernama ‘tree_node’ dan menggunakan data yang diberikan untuk memulakan penuding nod anak kiri dan kanan kepada null dan mengembalikan nod akar. Menggunakan fungsi ini, kami akan memasukkan nod nod anak kiri dan nod anak kanan.

• Kami sedang mencipta fungsi yang dipanggil ‘check_isomorphism_tree , yang menggunakan jenis data Boolean, mengambil dua tree_node penunjuk p dan q sebagai parameter input dan mengembalikan nilai boolean. Di dalamnya, kami mencipta "penyataan jika" dua kali untuk menyemak sama ada data dalam p adalah sama dengan data dalam q.

• Semak jika kedua-dua p dan q adalah batal, jika ya, kembalikan benar kerana pokok itu adalah isomorfik.

• Semak sama ada p atau q adalah batal, dan jika ya, kembalikan palsu kerana kedua-dua pokok itu bukan isomorfik.

• Dalam fungsi ‘check_isomorphism_tree’, kami menggunakan operator logik “&&” dan “||” untuk menyemak semua kemungkinan gabungan nod anak kiri dan kanan nod ‘p’ dan ‘q’.

• Kami bermula dari fungsi utama dan mencipta dua nod pokok "p" dan "q" untuk memberikan maklumat.

• Dalam fungsi utama, kami memanggil fungsi ‘check_isomorphism_tree’ menggunakan pernyataan if dan lulus parameter p dan q yang diberikan untuk mengesahkan sama ada nilai integer ini adalah isomorfik. Jika ia adalah isomorfik, pernyataan cetakan ialah "Maklumat nod yang diberikan ini akan menjana pokok isomorfik", jika sebaliknya adalah benar.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Dalam program ini, kami akan menyemak sama ada dua pokok binari adalah isomorfik.

#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

Kesimpulan

Dalam program ini, kami memahami konsep isomorfisme dalam pokok N-ary. Kami melihat cara menggunakan struktur untuk mewakili nod pokok, dan untuk membina pokok menggunakan nod kiri-kiri, nod kanan-kiri, nod kiri-kanan-kiri, dll. Operasi berikut membantu memenuhi sifat isomorfik pokok.

Atas ialah kandungan terperinci Isomorfisme dalam pokok N-ary. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!