देना चाहिए, मुझे पता है कि बाइनरी सर्च पेड़ पर इन-ऑर्डर ट्रैवर्सल (विज़िट बाएं, रूट रूट, विज़िट राइट) मुझे एक क्रमबद्ध परिणाम देता है। लेकिन मुझे बाइनरी पेड़ पर पोस्ट-ऑर्डर ट्रैवर्सल (विज़िट बाएं, विज़िट राइट, विज़िट रूट) करने की ज़रूरत है और परिणाम मुझे मूल्यों को क्रमबद्ध करना चाहिए।एक बाइनरी पेड़ का निर्माण करें जैसे पोस्ट-ऑर्डर ट्रैवर्सल को क्रमबद्ध परिणाम
यह प्राप्त करने के लिए, मुझे अपने बाइनरी पेड़ को कैसे बनाना चाहिए?
चूंकि रूट का अंतिम बार दौरा किया जाता है, इसमें सबसे बड़ी वस्तु होनी चाहिए। चूंकि बाएं उपट्री का सही उपट्री से पहले दौरा किया जाता है, बाएं उपट्री में सभी आइटम दाएं उपट्री में किसी भी आइटम से छोटे होने चाहिए।
तो इस तरह का पेड़ बनाने के लिए आप निम्नानुसार आगे बढ़ सकते हैं: यदि आप रूट से अधिक एक वस्तु डालते हैं, तो वह आइटम नई रूट बन जाता है। यदि आप एक आइटम डालते हैं जो रूट से छोटा है लेकिन बाएं उपट्री की जड़ से अधिक है, तो इसे सही उपट्री में डालें। अन्यथा इसे बाएं उपट्री में डालें।
आप सुनिश्चित करने के लिए पेड़ के प्रत्येक नोड पर निम्न की जरूरत है: नोड पर
यह सबरूटीन जहां वृक्ष संरचना
struct tree
{
int data;
tree * left;
tree *right;
tree(int n) // constructor
{
data = n;
left = right = NULL;
}
};
एल्गोरिथ्म है पेड़ में डालने के लिए है।
2. यदि रूट नोड के डेटा से नए नोड का डेटा बड़ा नोड
पेड़ की जड़ बनाता है।
3. अन्य पेड़ के बाएं उपट्री में नया नोड डालें।
tree * insert(tree *root,int n)
{
if(root == NULL)
{
root = new tree(n);
return root;
}
else
{
if(n > root -> data)
{
tree * t = new tree(n);
t -> left = root;
return t;
}
else
{
root -> left = insert(root -> left,n);
return root;
}
}
}
currently accepted answer एक अच्छा ऑनलाइन एल्गोरिथ्म देता है। कुछ हद तक सरल समाधान --- जो ऑनलाइन नहीं है और संभावित रूप से धोखा देने के लिए --- मूल बिंदुओं में एक क्रमबद्ध लिंक्ड सूची को स्टोर करना है।
दूसरे शब्दों में: डेटा को सॉर्ट करें; जड़ में सबसे बड़ी वस्तु डालें, इसके उपनिवेशों में से एक को रिक्त बनाएं और शेष उप-1 वस्तुओं के पोस्ट-ऑर्डर-सॉर्ट किए गए पेड़ को अन्य उपट्री में दोबारा बनाएं।
पेड़ की ऊंचाई एन होगी, एकल पत्ता सूची का प्रमुख है और रूट पूंछ-सबसे तत्व है। यदि आप पत्ते से पेड़ तक पेड़ के माध्यम से चलते हैं तो तत्व एक बढ़ते अनुक्रम का निर्माण करेंगे, और यह पथ वास्तव में एक पोस्टऑर्डर ट्रैवर्सल के अनुरूप होगा।
विलोपन
:
7 6
/\ /\
3 6 =========DELETING 7 ============> 4 5
/\/\ /
1 2 4 5 3
/\
1 2
यह काम करेंगे, लेकिन यह जरूरी नहीं कि एक संतुलित पेड़ लिए नेतृत्व नहीं करेंगे - एल्गोरिथ्म संतुलन के कुछ प्रकार की जरूरत है। –
अच्छा समाधान .. – bragboy