प्री-ऑर्डर ट्रैवर्सल के साथ पेड़ का निर्माण

Question

एक विशेष प्रकार का पेड़ दिया जाता है जहां सभी पत्तियों को L के साथ चिह्नित किया जाता है और अन्य N के साथ चिह्नित होते हैं। प्रत्येक नोड में 0 या अधिकतम 2 नोड्स हो सकते हैं। पेड़ के प्रीऑर्डर ट्रैवर्सल दिया जाता है।

इस ट्रैवर्सल से पेड़ बनाने के लिए एक एल्गोरिदम दें।

Preorder(T) 
    if (T is not null) 
    print T.label 
    Preorder(T.left) 
    Preorder(T.right) 

के NNLLNL के इनपुट के लिए एक एल्गोरिथ्म को खोजने के लिए कोशिश करते हैं:

Answer 1

यह अग्रिम आदेश ट्रावर्सल एल्गोरिथ्म है।

स्पष्ट रूप से रूट का लेबल पहले मुद्रित होता है। तो आप जानते हैं कि रूट में N लेबल है। अब एल्गोरिदम बाएं subtree पर recurses। इनपुट के अनुसार यह N भी है। उस के बाएं उपट्री पर रिकर्स, जो L है। अब आपको बैकट्रैक करना है, क्योंकि आप एक पत्ते पर पहुंच गए हैं। इनपुट में अगली स्थिति भी L है, इसलिए वर्तमान नोड का सही बच्चा L के साथ लेबल किया गया है। एक बार बैकट्रैक। बैकट्रैक फिर से, क्योंकि आपने वर्तमान नोड (अधिकतम 2 बच्चे) के सभी बच्चों को जोड़ा है। अब आप रूट पर फिर से हैं। आपको सही जाना है, क्योंकि आप पहले ही चले गए हैं। इनपुट के अनुसार, यह N है। तो रूट का सही बच्चा N है। उस का बायां बच्चा L होगा। यह आपके पेड़ है:

 N 
    / \ 
    N  N 
/\ /
    L L L 

ध्यान दें कि समाधान निश्चित रूप से अनन्य नहीं है, लेकिन यह आप एक संभव समाधान मिल जाएगा।

स्यूडोकोड:

k = 0 
input = ... get preorder traversal vector from user ... 
Reconstruct(T) 
    if input[k] == N 
    T = new node with label N 
    k = k + 1 
    Reconstruct(T.left) 
    Reconstruct(T.right) 
    else 
    T = new node with label L 
    T.left = T.right = null 
    k = k + 1 

एक अशक्त नोड के साथ बुलाया गया।

अनुवर्ती प्रश्न: अलग-अलग नोड लेबल वाले बाइनरी पेड़ के प्रीऑर्डर और इनऑर्डर ट्रैवर्सल दोनों को देखते हुए, आप विशिष्ट रूप से पेड़ का पुनर्निर्माण कैसे कर सकते हैं?