बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम दो बच्चे होते हैं, जिन्हें बाएँ बच्चे और दाएँ बच्चे के रूप में परिभाषित किया जाता है।
एल्गोरिदम
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