Isomorphismus in N-ary-Bäumen

Isomorphismus ist definiert als zwei Bäume mit der gleichen oder gespiegelten Struktur. Bei einer Spiegelstruktur stimmen die Daten des linken Knotens immer mit denen des rechten Knotens überein. Nehmen wir zum Beispiel eine Zahl, die dem Spiegelbild am nächsten kommt, und sehen wir uns an, was ihre Umkehrung ist, was das wahre Konzept des Isomorphismus ist.

In diesem Artikel prüfen wir, ob zwei verschiedene Binärbäume isomorph sind.

Nehmen wir als Beispiel den Isomorphismus des N-ary-Baums-

Bitte beachten Sie, dass L den linken Knoten und R den rechten Knoten darstellt

Spiegelstruktur der P- und Q-Bäume in der zweiten Partition ganz links

Diese beiden Diagramme zeigen, wie sie bei vier übereinstimmenden Bedingungen (Wurzelknoten von P und Q) zueinander isomorph sind.

• Links-Links-Knoten können übereinstimmen.

• Beides kann mit Rechts-Rechts-Knoten übereinstimmen.

• Sowohl der linke als auch der rechte Knoten können abgeglichen werden.

• Oder rechts und links können nicht übereinstimmen.

Grammatik

Die folgende Syntax wird im Programm verwendet −

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

Parameter

• struct - Dieses Schlüsselwort wird verwendet, um den Strukturdatentyp darzustellen.

• name_of_structure − Wir geben einen beliebigen Namen für die Struktur an.

• Eine Struktur ist eine Sammlung verschiedener verwandter Variablen an einem Ort.

Algorithmus

• Wir werden eine Header-Datei namens ‘iostream‘ verwenden, um das Programm zu starten.

• Wir erstellen eine Struktur namens 'tree_node', die den Ganzzahltyp 'd' und initialisierte Zeigervariablen - 'l' und 'r' enthält und die Daten des linken und rechten untergeordneten Knotens darstellt jeweils.

• Jetzt erstellen wir eine weitere Struktur mit einer Funktion namens ‘create_node()‘, die einen Parameter namens ‘data‘ akzeptiert, um den Wert des Wurzelknotens anzugeben. Gleichzeitig erstellen wir einen Zeiger mit dem Namen ‘tree_node‘ und verwenden die angegebenen Daten, um die Zeiger des linken und rechten untergeordneten Knotens auf Null zu initialisieren und den Wurzelknoten zurückzugeben. Mit dieser Funktion fügen wir den Knoten des linken untergeordneten Knotens und des rechten untergeordneten Knotens ein.

• Wir erstellen eine Funktion namens ‘check_isomorphism_tree , die den booleschen Datentyp verwendet, zwei tree_node-Zeiger p und q als Eingabeparameter verwendet und einen booleschen Wert zurückgibt. Darin erstellen wir zweimal eine „if-Anweisung“, um zu prüfen, ob die Daten in p gleich den Daten in q sind.

• Überprüfen Sie, ob sowohl p als auch q null sind. Wenn ja, geben Sie true zurück, da der Baum isomorph ist.

• Überprüfen Sie, ob p oder q null ist, und wenn ja, geben Sie false zurück, da die beiden Bäume nicht isomorph sind.

• In der Funktion ‚check_isomorphism_tree‘ verwenden wir die logischen Operatoren „&&“ und „||“, um rekursiv alle möglichen linken und rechten untergeordneten Knotenkombinationen der Knoten ‘p‘ und ‘q‘ zu überprüfen.

• Wir beginnen mit der Hauptfunktion und erstellen zwei Baumknoten „p“ und „q“, um Informationen bereitzustellen.

• In der Hauptfunktion rufen wir die Funktion „check_isomorphism_tree“ mit einer if-Anweisung auf und übergeben die angegebenen Parameter p und q, um zu überprüfen, ob diese ganzzahligen Werte isomorph sind. Wenn sie isomorph sind, lautet die Druckanweisung „Diese gegebenen Knoteninformationen erzeugen einen isomorphen Baum“, andernfalls ist das Gegenteil der Fall.

Beispiel

Beispiel

In diesem Programm prüfen wir, ob zwei Binärbäume isomorph sind.

#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;
}

Ausgabe

This given information of node will make isomorphism tree

Fazit

In diesem Programm verstehen wir das Konzept des Isomorphismus im N-ary-Baum. Wir haben gesehen, wie man Strukturen verwendet, um Baumknoten darzustellen und Bäume mithilfe von Links-Links-Knoten, Rechts-Links-Knoten, Links-Rechts-Links-Knoten usw. zu erstellen. Die folgenden Operationen helfen dabei, der isomorphen Natur von Bäumen gerecht zu werden.

Das obige ist der detaillierte Inhalt vonIsomorphismus in N-ary-Bäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!