रिकर्सन

Question

के माध्यम से इंटीजर बाइनरी ट्री का आकार निर्धारित करें मेरे पास बाएं और दाएं बच्चे और बाइनरी ट्री (इंट रूटवेल) के साथ बाइनरी ट्रीनोड रूट के साथ बाइनरी ट्रीनोड रूट (रूट वैल्यू) है जिसमें रूट वैल इसके मूल्य के रूप में है। मैं पेड़ में नोड्स (कक्षा BinaryTreeNode में) की संख्या की गणना करने के लिए एक कोड विकसित की है, लेकिन यह एक NullPointerException की वजह से काम नहीं करता है:

public int size(){ 
    if(this == null) { // base case 
     return 0; 
    } else { 
     return 1 + left.size() + right.size(); 
    } 
} 

हालांकि एक और समाधान मैंने पाया, एक ऐसी ही रणनीति के साथ, काम करता है :

public int size(BinaryTreeNode refNode){ 
    if(refNode == null) { // base case 
     return 0;  
    } else { 
     return 1 + size(refNode.left) + size(refNode.right); 
    } 
} 

मुझे समझ में आया है कि मेरा कोड अपवाद क्यों फेंकता है (ऐसा इसलिए है क्योंकि बाएं/दाएं शून्य को इंगित करेंगे)। लेकिन मैं समझना चाहता हूं कि दूसरा समाधान समान सिद्धांत के साथ काम करता है। अग्रिम धन्यवाद!

Answer 1

अपने पहले उदाहरण में आप इससे पहले कि आप null के लिए जाँच आकार खोजने की कोशिश आपने बस null

if(this == null) { // base case 
    return 0; 
... 

पर विधि को बुलाया है

इसलिए leftnull है, तो आप size() विधि में पहुंचने से पहले एनपीई प्राप्त करते हैं।

मुख्य बात यहाँ याद करने के लिए, यह है कि thisकभी नहींnull हो सकता है। यदि यह था, तो आप पहली जगह पर एक विधि नहीं चला सकते थे। तो आप वास्तव में null मामले पर अपने रिकर्सन को समाप्त नहीं कर रहे थे जैसे आपने सोचा था कि आप थे।

अगर refNode:

दूसरा आप null पहले की जांच करने में

।बाईं null यहाँ

return 1 + size(refNode.left) + size(refNode.right); 

size() विधि-जाँच पूर्व

if(refNode == null) { // base case 
    return 0; 
... 

एक करता है और सुरक्षित रूप से 0 देता है।

आप स्पष्ट रूप से प्रत्येक शाखा पर पहले अशक्त की जांच रख कर अपनी पहली विधि काम कर सकता है:

public int size(){ 
    return 1 
     + left == null ? 0 : left.size() // check for null first 
     + right == null ? 0 : right.size(); // check for null first 
} 

Answer 2

this चल रहे वर्ग के अंदर कभी भी null नहीं हो सकता है। आपको एनपीई मिल जाएगी क्योंकि left == null या right == null वाला नोड size() कोड पर कॉल करने में सक्षम नहीं होगा, क्योंकि सूचक कुछ भी नहीं संदर्भित करता है।

शायद अपने कोड अधिक रक्षात्मक हो सकता है और उनके आकार प्राप्त करने का प्रयास करने से पहले जांच लें कि क्या बच्चों अशक्त हैं चाहिए:

public int size() { 
    int total = 1; 
    if (left != null) 
     total += left.size(); 
    if (right != null) 
     total += right.size(); 
    return total; 
} 

Answer 3

आधार मामला गलत तरीके से आयोजित किया जाता है; वर्तमान उदाहरण पर null की जांच करने से कोई मतलब नहीं आता है। इस प्रकार विधि को फिर से लिखा जाना चाहिए।

पहले आप

left.size() 

फोन और फिर size() विधि के अंदर आप वस्तु देखने हेतु जांचने:

public int size(){ 
    int sizeLeft = 0; 
    if (this.left != null) 
     sizeLeft = left.size(); 
    int sizeRight = 0; 
    if (this.right != null) 
     sizeRight = right.size(); 
    return 1 + sizeLeft + sizeRight; 
}