एल्गोरिदम
CarTree क्लास बनाएं जिसमें min() फ़ंक्शन सरणी में न्यूनतम तत्व का इंडेक्स खोजने के लिए और inorder() फ़ंक्शन ट्री का इनऑर्डर ट्रैवर्सल के लिए हो। min() में: सरणी को पार करें और न्यूनतम मान और उसका इंडेक्स ट्रैक करें। inorder() में: यदि ट्री खाली है तो लौटें, अन्यथा बाएं सबट्री, रूट, दाएं सबट्री का इनऑर्डर ट्रैवर्सल करें।
उदाहरण कोड
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct nod {
int d;
struct nod* l;
struct nod* r;
};
class CarTree {
public:
nod *newNode(int);
int min(int [], int, int);
nod *buildTree(int [], int, int);
void inorder(nod* node);
void show(nod *, int);
CarTree() {}
};
int CarTree::min(int arr[], int s, int e) {
int i, min = arr[s], minind = s;
for (i = s + 1; i <= e; i++) {
if (arr[i] < min) {
min = arr[i];
minind = i;
}
}
return minind;
}
nod *CarTree::buildTree(int inorder[], int s, int e) {
if (s > e) return NULL;
int i = min(inorder, s, e);
nod *r = newNode(inorder[i]);
if (s == e) return r;
r->l = buildTree(inorder, s, i - 1);
r->r = buildTree(inorder, i + 1, e);
return r;
}
void CarTree::inorder(struct nod* node) {
if (node == NULL) return;
inorder(node->l);
cout << node->d << " ";
inorder(node->r);
}
void CarTree::show(nod *ptr, int level) {
int i;
if (ptr == NULL) return;
if (ptr != NULL) {
show(ptr->r, level + 1);
cout << endl;
for (i = 0; i < level; i++)
cout << " ";
cout << ptr->d;
show(ptr->l, level + 1);
}
}
nod *CarTree::newNode(int d) {
nod* t = new nod;
t->d = d;
t->l = NULL;
t->r = NULL;
return t;
}
int main() {
CarTree ct;
int i, n;
cout << "डालने के लिए तत्वों की संख्या दर्ज करें: ";
cin >> n;
int a[n];
for (i = 0; i < n; i++) {
cout << "तत्व " << i + 1 << " : ";
cin >> a[i];
}
nod *r = ct.buildTree(a, 0, n - 1);
cout << "कार्टेशियन ट्री संरचना: " << endl;
ct.show(r, 1);
cout << endl;
cout << "\n ट्री का इनऑर्डर ट्रैवर्सल \n" << endl;
ct.inorder(r);
cout << endl;
return 0;
}आउटपुट
डालने के लिए तत्वों की संख्या दर्ज करें: 10
तत्व 1 : 10
तत्व 2 : 30
तत्व 3 : 20
तत्व 4 : 40
तत्व 5 : 50
तत्व 6 : 70
तत्व 7 : 60
तत्व 8 : 80
तत्व 9 : 100
तत्व 10 : 112
कार्टेशियन ट्री संरचना:
112
100
80
60
70
50
40
20
30
10
इनऑर्डर ट्रैवर्सल: 10 30 20 40 50 70 60 80 100 112
