N元樹中的同構性

同構被定義為兩棵樹具有相同或鏡像結構。在鏡像結構的情況下，左節點的資料將始終與右節點相符。例如，我們將取一個最接近鏡像的數字，看看它的反向是什麼，這就是同構的真正概念。

在本文中，我們將檢查兩個不同的二元樹是否同構。

讓我們以N叉樹的同構為例-

請注意，L代表左節點，而R代表右節點

左側最左第二分區的P和Q樹的鏡像結構

這兩個圖示展示了它們如何透過給出四個匹配條件（P和Q的根節點）來彼此同構。

• 左-左節點可以匹配。

• 要嘛可以匹配右-右節點。

• 左右節點皆可配對。

• 要嘛右左無法匹配。

文法

程式中使用了以下語法−

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

參數

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

輸出

This given information of node will make isomorphism tree

結論

在這個程式中，我們了解N叉樹中同構的概念。我們看到如何使用結構來表示樹節點，以及使用左-左節點、右-左節點、左-右-左節點等來建構樹，以下操作有助於滿足樹的同構性質。

以上是N元樹中的同構性的詳細內容。更多資訊請關注PHP中文網其他相關文章！