Trong cây nhị phân, mỗi nút chứa hai nút con, tức là nút con bên trái và nút con bên phải. Giả sử chúng ta có hai cây nhị phân và nhiệm vụ là kiểm tra xem một trong hai cây có thể lấy được bằng cách lật trái cây khác hay không.
Một cây là Isomorphic nếu nó có thể được lấy bằng cách lật cây khác ở phía bên trái của nó.
Ví dụ
Đầu vào-1
Đầu ra: Isomorphic
Giải thích: Có thể lấy được Cây-2 đã cho bằng cách lật Cây-1 ở phía bên trái, do đó Cây là đẳng cấu.
Phương pháp tiếp cận để giải quyết vấn đề này
Một cách tiếp cận đệ quy để giải quyết vấn đề cụ thể này là một hàm Boolean sẽ kiểm tra các nút gốc của cả hai cây. Nếu rễ của cả hai cây đều trống hoặc NULL, thì trả về True và kiểm tra đệ quy xem cả hai gốc có cùng dữ liệu hay không. Sau đó, chúng tôi sẽ kiểm tra đệ quy các nút bên trái và bên phải của cây.
- Tạo các nút cho hai cây nhị phân.
- Một hàm Boolean isIsomorphicTree (nút * r1, nút * r2) lấy gốc của hai cây và trả về nếu cây đó là Isomorphic hay không.
- Ban đầu, nếu cây trống hoặc không có bất kỳ nút nào trong đó, thì trả về True.
- Nếu cây con gốc không được lật và nếu cả hai đều bị lật, thì trả về True.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isIsomorphicTree(treenode * r1, treenode * r2) {
if (r1 == NULL and r2 == NULL) {
return true;
}
if (r1 == NULL or r2 == NULL) {
return false;
}
return (r1 -> data == r2 -> data && ((isIsomorphicTree(r1 -> left, r2 -> right) && isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) && isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
struct treenode * r1 = createNode(1);
r1 -> left = createNode(2);
r1 -> right = createNode(3);
r1 -> left -> left = createNode(4);
r1 -> left -> right = createNode(5);
r1 -> right -> left = createNode(6);
r1 -> left -> right -> left = createNode(7);
r1 -> left -> right -> right = createNode(8);
struct treenode * r2 = createNode(1);
r2 -> left = createNode(3);
r2 -> right = createNode(2);
r2 -> right -> left = createNode(4);
r2 -> right -> right = createNode(5);
r2 -> left -> right = createNode(6);
r2 -> right -> right -> left = createNode(8);
r2 -> right -> right -> right = createNode(7);
if (isIsomorphicTree(r1, r2)) {
cout << "Isomorphic" << endl;
} else {
cout << "Not an Isomorphic" << endl;
}
return 0;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
Isomorphic
Giải thích: Có thể lấy được cây đã cho bằng cách lật ngược cây còn lại về phía bên trái của nó, do đó nó là Cây đa hình.