home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ตรวจสอบว่า Tree เป็น Isomorphic หรือไม่ใน C++

ในไบนารีทรี แต่ละโหนดมีลูกสองคน นั่นคือ ลูกซ้ายและลูกขวา สมมติว่าเรามีไบนารีทรีสองต้น และภารกิจคือตรวจสอบว่าได้ต้นไม้ต้นใดต้นหนึ่งได้จากการพลิกต้นไม้อื่นทางซ้ายของต้นไม้นั้นหรือไม่

ต้นไม้จะเป็นแบบ Isomorphic หากสามารถรับได้จากการพลิกต้นไม้อีกต้นหนึ่งทางด้านซ้ายของต้นไม้

ตัวอย่าง

อินพุต-1

ตรวจสอบว่า Tree เป็น Isomorphic หรือไม่ใน C++

ผลลัพธ์: ไอโซมอร์ฟิค

คำอธิบาย: สามารถหา Tree-2 ที่ให้มาได้โดยพลิก Tree-1 ไปทางซ้าย ดังนั้น Tree จึงมี isomorphic

แนวทางในการแก้ปัญหานี้

วิธีการแบบเรียกซ้ำในการแก้ปัญหานี้คือฟังก์ชันบูลีนจะตรวจสอบโหนดรากของต้นไม้ทั้งสอง หากรากของต้นไม้ทั้งสองว่างเปล่าหรือเป็น NULL ให้คืนค่า True และตรวจซ้ำว่ารากทั้งสองมีข้อมูลเดียวกันหรือไม่ จากนั้นเราจะตรวจสอบโหนดซ้ายและขวาของต้นไม้ซ้ำๆ

  • สร้างโหนดสำหรับต้นไม้ไบนารีสองต้น
  • ฟังก์ชันบูลีน isIsomorphicTree(node*r1, node*r2) รับรากของต้นไม้สองต้นและส่งคืนถ้าต้นไม้นั้นเป็น Isomorphic หรือไม่
  • ในขั้นต้น หากต้นไม้ว่างเปล่าหรือไม่มีโหนดในนั้น ให้คืนค่า True
  • หากทรีย่อยที่รูทแล้วไม่ได้ถูกพลิกและหากทั้งสองถูกพลิก ให้คืนค่า True

ตัวอย่าง

#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 &amp;&amp; ((isIsomorphicTree(r1 -> left, r2 -> right) &amp;&amp;       isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) &amp;&amp; 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;
}

การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น

ผลลัพธ์

Isomorphic

คำอธิบาย: สามารถหาต้นไม้ที่ให้มาได้โดยพลิกอีกต้นไปทางซ้าย จึงเป็น Isomorphic