同構被定義為兩棵樹具有相同或鏡像結構。在鏡像結構的情況下，左節點的資料將始終與右節點相符。例如，我們將取一個最接近鏡像的數字，看看它的反向是什麼，這就是同構的真正概念。
在本文中，我們將檢查兩個不同的二元樹是否同構。
讓我們以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中文網其他相關文章！
