पुनरावृत्ति के साथ या बिना एक गैर बाइनरी पेड़ कैसे बनाया जाए?

Question

मैं एक पदानुक्रमित डेटा है कि इस तरह से चला जाता है है:

+----------------------+-------+ 
| name     | depth | 
+----------------------+-------+ 
| ELECTRONICS   |  0 | 
| TELEVISIONS   |  1 | 
| TUBE     |  2 | 
| LCD     |  2 | 
| PLASMA    |  2 | 
| PORTABLE ELECTRONICS |  1 | 
| MP3 PLAYERS   |  2 | 
| FLASH    |  3 | 
| CD PLAYERS   |  2 | 
| 2 WAY RADIOS   |  2 | 
+----------------------+-------+ 

ट्यूब, एलसीडी और प्लाज्मा टीवी के बच्चे हैं। फ्लैश एमपी 3 प्लेयर का बच्चा है। एमपी 3 प्लेयर, सीडी प्लेयर और 2 वे रेडियोज़ पोर्टेबल इलेक्ट्रॉनिक्स के बच्चे हैं। आपको ड्रिल मिलता है।

अब, मेरे पास एक नोड है जिसमें एक नोड है जिसमें इसके आईडी और उसके बच्चे हैं, और इसी तरह, एक पेड़ बनाने के लिए। इस तरह:

struct Node 
{ 
    int id; 
    list<Node*> children; 
} 

प्रत्येक आइटम (, इलेक्ट्रॉनिक्स = 0, टीवी = 1 और इसी तरह) एक आईडी है, जो पंक्ति संख्या है द्वारा पहचाना जाता है, तो यह पता लगाने के लिए आसान है जो एक के बच्चे हैं नोड।

यह वह पेड़ है जिसे मैं बनाने की कोशिश कर रहा हूं। यह पेड़ बाइनरी नहीं है, जैसा कि आप देख सकते हैं। तो पुनरावृत्ति लागू करना एक आसान विचार की तरह प्रतीत नहीं होता है। यदि मैं गलत हूं तो मुझे सही करों।

तो मैं यह कैसे कर सकता हूं? मदद!

Answer 1

आपको इसके बजाय नोड्स को पॉइंटर्स का उपयोग करना चाहिए, अन्यथा आप प्रत्येक स्तर पर अपने पेड़ में डेटा डुप्लिकेट करेंगे।

मैं यह भी सुझाव दूंगा कि आप int आईडी के बजाय enum का उपयोग करें, यह कोड को थोड़ा और स्पष्ट बनाता है।

गैर-बाइनरी पेड़ के साथ रिकर्सन का उपयोग करने में कोई समस्या नहीं है, तो आपको list<Node*> में प्रत्येक रिकर्सिव फ़ंक्शन कॉल में left/right (या इसी तरह) को कॉल करने की बजाय आवश्यकता है।

Answer 2

कोई सीमा नहीं है कि वृक्ष इसे बार-बार बनाने के लिए बाइनरी होना चाहिए। यह दोनों रिकर्सिव और गैर-पुनरावर्ती विधि दोनों के साथ बनाया जा सकता है।

मेरे लिए, मैं एक शीर्ष नीचे फैशन में पेड़ का निर्माण करूंगा, यानी बच्चों के सामने पैरेंट नोड बनाएं। मैं किसी भी तरह से खपत रैखिक बनाने के लिए इनपुट डेटा सॉर्ट करेंगे। एक नया नोड जोड़ने के लिए, पैरामीटर के रूप में गहराई दें और रूट (जब तक रूट से नीचे जा रहे हों) जब तक यह 0 तक न पहुंच जाए, वहीं नोड होना चाहिए। बेशक, नोड के लिए पैरेंट पथ की जानकारी आवश्यक है।

Answer 3

कुछ इस तरह:

int main() 
{ 
    Node flash(FLASH_ID); 
    Node mp3(MP3_ID); 

    mp3.children.push_back(flash); 
    // repeat 
} 

Answer 4

आप एक से अधिक जोड़ने सूचक का उपयोग कर सकते हैं। अर्थात

struct node 
{ 
int id; 
node *first_child; 
node *second child; 
node *third_child; 
} 

आप में मामला अधिकतम 3. है आप अलग अलग बच्चों के साथ नोड्स इंगित करें और उन तक पहुँच सकते हैं। यदि, 3 से कम बच्चे हैं, तो आप इसे पूर्ण कर सकते हैं।