आपको अग्रिम-आदेश ट्रैवर्सल का परिणाम दिया गया है। आपको उन तत्वों की संख्या ज्ञात करनी होगी जो रूट से छोटे हों।
प्रीऑर्डर ट्रैवर्सल में पहला तत्व बीएसटी की जड़ है। आइए एक उदाहरण देखें।
इनपुट
preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]
आउटपुट
3
ऐसे तीन तत्व हैं जो जड़ से छोटे हैं। जड़ 5 है।
एल्गोरिदम
-
एक सरणी में अग्रिम-आदेश परिणाम प्रारंभ करें।
-
पहले एलिमेंट यानी बीएसटी के रूट को एक वेरिएबल में स्टोर करें।
-
एक लूप लिखें जो प्रीऑर्डर परिणाम के दूसरे तत्व से पुनरावृत्त हो।
-
प्रत्येक तत्व की जड़ से तुलना करें।
-
यदि वर्तमान तत्व मूल से बड़ा है, तो गिनती बढ़ाएँ।
-
-
गिनती वापस करें।
कार्यान्वयन
C++ में उपरोक्त एल्गोरिथम का कार्यान्वयन निम्नलिखित है
#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n) {
if (n < 0) {
return 0;
}
int i, root = arr[0], count = 0;
for(i = 1; i < n; i++) {
if(arr[i] < root) {
count += 1;
}
}
return count;
}
int main() {
int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
int n = 8;
cout << getElementsCount(preorder, n) << endl;
return 0;
} आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
3