तो मेरे पास यह छद्म कोड एल्गोरिदम है जो मुझे एक साक्षात्कार के लिए दिया गया था जो एक बाइनरी पेड़ को पार करता है और किसी प्रकार का मूल्य देता है। एक निकाले गए बाइनरी ट्री के साथ एल्गोरिथम का पता लगाने के बाद, मैंने खुद को दूसरा अनुमान लगाया कि क्या मैं अंतिम कॉल पर 2 + valOne + valTwo लौटाता हूं, जब एल्गोरिदम रूट पर वापस लौटता है या नहीं। जब मैंने इसे लागू किया, तो मेरी गणना के अनुसार लौटाई गई संख्या 2 * (पेड़ की ऊंचाई) थी, और मैं यह जांचना चाहता था कि मेरा उत्तर और तर्क सही था या नहीं। अभ्यास पत्र के अनुसार उत्तर का दावा है कि यह एक पेड़ में किनारों की संख्या को गिनता है लेकिन मुझे यह बिल्कुल समझ में नहीं आता कि यह कैसे संभव है।

public int foo(r){
         if(r is leaf) return 0;
         else{
             valOne = foo(r.leftChild());
             valTwo = foo(r.rightChild());
             return 2 + valOne + valTwo;
         }

तो क्या return 2 + valOne + valTwo पूरे पेड़ की जड़ पर भी लगाया जाता है? और अगर है तो क्या मेरा जवाब सही नहीं होगा? आप लोगों को धन्यवाद!

0
CosmicCat 27 अक्टूबर 2019, 03:31

3 जवाब

सबसे बढ़िया उत्तर

एक बाइनरी ट्री के लिए जिसके प्रत्येक नॉन-लीफ नोड में लेफ्ट और राइट चाइल्ड नोड दोनों होते हैं, यह किनारों की संख्या की गणना करता है।

valOne = foo(r.leftChild()); // count edges in left subtree

valTwo = foo(r.rightChild()); //count edges in right subtree

return 2 + valOne + valTwo; // 2  (the edges from this node to its children) + edges in sub trees
if(r is leaf) return 0; //leaf nodes have no edges pointing out
1
Martin'sRun 27 अक्टूबर 2019, 08:55
क्या होगा अगर हमारे पास एक गैर-संतुलित बाइनरी ट्री है?
 – 
CosmicCat
27 अक्टूबर 2019, 05:58
यह गैर-संतुलित पेड़ों के लिए भी काम करता है, जब तक कि प्रत्येक नोड में 2 बच्चे हों, जो एम्सवर को सही करते हैं। पहला नोड जिसमें दोनों बच्चे नहीं हैं और एक पत्ता नहीं है, जब तक संभाला नहीं जाता है, तब तक एक शून्य सूचक अपवाद हो सकता है।
 – 
Martin'sRun
27 अक्टूबर 2019, 08:50

प्रदान किए गए छद्म कोड के साथ, यदि यह संलग्न ग्राफ़ में से एक जैसा पेड़ है, तो प्रत्येक नोड का मान ग्राफ़ में वर्णित के अनुसार उचित होगा।

enter image description here

0
garykwwong 27 अक्टूबर 2019, 06:09

यह मान्य जावा कोड नहीं है।

आइए समझने की कोशिश करें कि आप क्या पूछना चाह रहे हैं। शायद आपका मतलब इस स्निपेट से था:

public int foo(Node r) {
    if (r instanceof Leaf) return 0;
    int valOne = foo(r.leftChild());
    int valTwo = foo(r.rightChild());
    return 2 + valOne + valTwo;
}

लाइन int valOne = ... इसी विधि को फिर से आमंत्रित करती है, इस बार बाएं बच्चे पर। और यदि बायां बच्चा एक पत्ता नहीं है, तो बाएं बच्चे पर इस विधि के निष्पादन के दौरान, वह भी अपने बच्चों के लिए फिर से खुद को बुलाएगा।

वापसी विवरण दिलचस्प नहीं है और जो भी रिकर्सन में संलग्न नहीं है। यह valOne = और valTwo = लाइनें हैं।

-1
rzwitserloot 27 अक्टूबर 2019, 05:30