एक बाइनरी ट्री एक ट्री डेटा स्ट्रक्चर है जिसमें प्रत्येक नोड में अधिकतम दो बच्चे होते हैं, जिन्हें लेफ्ट चाइल्ड और राइट चाइल्ड के रूप में परिभाषित किया जाता है।
एल्गोरिदम
शुरुआत
function identical():
दो नोड्स r1 और r2 को पैरामीटर के रूप में लें
यदि r1 और r2 दोनों NULL हैं तो
true लौटाएं
यदि r1 या r2 NULL है तो
false लौटाएं
लौटाएं (r1->d, r2->d के बराबर है और
identical(r1->l, r2->l) कॉल करें और
identical(r1->r, r2->r) कॉल करें)
function Subtree(node* T, node* 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)
समाप्तिउदाहरण कोड
#include <iostream>
#include <cstdlib>
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() {
// ट्री T
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);
// ट्री S
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 << "दिया गया ट्री बाइनरी ट्री का सबट्री नहीं है";
return 0;
}आउटपुट
दिया गया ट्री बाइनरी ट्री का सबट्री नहीं है
दिया गया ट्री बाइनरी ट्री का सबट्री हैट्री संरचना
पहला टेस्ट केस - सबट्री नहीं
T: 24 S: 20
/ \ / \
7 2 3 5
/ \ \ / \
3 6 5 50
\
40
S, T का सबट्री नहीं है क्योंकि मान अलग हैं (20 vs 7, 50 vs 40)
दूसरा टेस्ट केस - सबट्री है
T1: 30 S1: 17
/ \ / \
17 20 4 15
/ \ \ / \
4 15 19 40
\
40
S1, T1 का सबट्री है (नोड 17 पर जड़ित)
समय जटिलता
- O(m × n) जहां m = T का साइज़, n = S का साइज़
- खराब केस: हर नोड पर identical() चेक होता है
ऑप्टिमाइज़ेशन
- ट्री सीरियलाइज़ेशन + सबस्ट्रिंग सर्च (KMP): O(m + n)
- हैशिंग (मर्कल ट्री): O(m + n) औसत
