একটি বাইনারি ট্রি হল একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকে, যাকে বাম শিশু এবং ডান শিশু হিসাবে সংজ্ঞায়িত করা হয়।
অ্যালগরিদম
Begin function identical(): Take two nodes r1 and r2 as parameter. If r1 and r2 is NULL then Return true. If r1 or r2 is NULL then Return false. Return (r1->d is equal to r2->d and Call function Identical(r1->l, r2->l) and Call functions Identical(r1->r, r2->r) ); function Subtree(node *T, node *S) : if (S == NULL) then return true; if (T == NULL) then return false; if (call function Identical(T, S)) return true; return Subtree(T->l, S) or Subtree(T->r, S); End.
উদাহরণ কোড
#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<<"given tree is subtree of Binary tree"<<"\n";
else
cout<<"given tree is not subtree of Binary tree"<<"\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<<"given tree is subtree of Binary tree";
else
cout<<"given tree is not subtree of Binary tree";
getchar();
return 0;
} আউটপুট
given tree is not subtree of Binary tree given tree is subtree of Binary tree
