একটি বাইনারি ট্রি হলো একটি ট্রি ডেটা স্ট্রাকচার যাতে প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড থাকে, যাদের বাম চাইল্ড ও ডান চাইল্ড বলে সংজ্ঞায়িত করা হয়।
অ্যালগরিদম
শুরু function identical(): دوটি নোড r1 এবং r2 প্যারামিটার হিসেবে নিন। r1 এবং r2 NULL হলে true রিটার্ন করুন। r1 বা r2 NULL হলে false রিটার্ন করুন। রিটার্ন (r1->d r2->d এর সমান এবং Function Identical(r1->l, r2->l) কল করুন এবং Function Identical(r1->r, r2->r) কল করুন ); function Subtree(node *T, node *S) : if (S == NULL) then return true; if (T == NULL) then return false; if (Identical(T, S) কল করুন) return true; return Subtree(T->l, S) or Subtree(T->r, S); শেষ।
উদাহরণ কোড
#include <iostream> using namespace std; struct n { int d; struct n* l; struct n* r; }; bool Identical(struct n * r1, struct n *r2) { if (r1 == NULL && r2 == NULL) return true; if (r1 == NULL || r2 == NULL) return false; return (r1->d == r2->d && Identical(r1->l, r2->l) && Identical(r1->r, r2->r) ); } bool Subtree(struct n *T, struct n *S) { if (S == NULL) return true; if (T == NULL) return false; if (Identical(T, S)) return true; return Subtree(T->l, S) || Subtree(T->r, S); } struct n* newN(int d) { struct n* nod = (struct n*)malloc(sizeof(struct n)); nod->d = d; nod->l = NULL; nod->r = NULL; return(nod); } int main() { struct n *T = newN(24); T->r = newN(2); T->r->r = newN(5); T->l = newN(7); T->l->l = newN(3); T->l->l->r = newN(40); T->l->r = newN(6); struct n *S = newN(20); S->r = newN(5); S->l = newN(3); S->l->r = newN(50); if (Subtree(T, S)) cout << "দেয়া ট্রি বাইনারি ট্রির সাবট্রি" << "\n"; else cout << "দেয়া ট্রি বাইনারি ট্রির সাবট্রি নয়" << "\n"; struct n *T1 = newN(30); T1->r = newN(20); T1->r->r = newN(19); T1->l = newN(17); T1->l->l = newN(4); T1->l->l->r = newN(40); T1->l->r = newN(15); struct n *S1 = newN(17); S1->r = newN(15); S1->l = newN(4); S1->l->r = newN(40); if (Subtree(T1, S1)) cout << "দেয়া ট্রি বাইনারি ট্রির সাবট্রি"; else cout << "দেয়া ট্রি বাইনারি ট্রির সাবট্রি নয়"; getchar(); return 0; }আউটপুট
দেয়া ট্রি বাইনারি ট্রির সাবট্রি নয় দেয়া ট্রি বাইনারি ট্রির সাবট্রি
