प्रत्येक नोड

Question

पर गहराई को असाइन करना मैंने यहां कुछ अन्य लेख पढ़े जो समान दिखते थे, लेकिन मेरी समस्या का काफी जवाब नहीं दिया। मुझे प्रत्येक नोड को बाइनरी पेड़ में अपनी संबंधित गहराई को आवंटित करने के लिए एक असाइनमेंट के लिए एक प्रश्न दिया गया है। मैं बस इसे काफी नहीं मिल सकता है।

struct treeNode { 
    int item; 
    int depth; 
    treeNode *left; 
    treeNode *right; 
}; 
typedef treeNode *Tree; 

int assignDepth(Tree &T, int depth) 
{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 
     T->depth = depth; 
     depth = assignDepth(T->right, depth++); 
    } 
    else //leaf 
     return depth--; 
} 

मैं कागज और कलम के साथ यह माध्यम से चल रहे की कोशिश की और यह ठीक देखा, लेकिन मेरी मेज कौशल की जाँच के स्पष्ट रूप से कमी है:

संदर्भ के लिए यह मेरा कोड है।

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

उत्तर:

void treecoords(Tree &T, int depth) 
{ 
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values 
    if(T!=NULL) 
    { 
     treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack 
     count++; 
     T->x = count; 
      T->y = depth; 
     treecoords(T->right, depth+1); 
    } 
} 

Answer 1

आप 'डॉन टी की जरूरत है

else //leaf 
    return depth--; 

तुम भी गहराई चर बढ़ाने के लिए नहीं करना चाहते हैं, बस + 1 अगले interation को गहराई गुजरती हैं।

इसके अलावा कोई मूल्य वापस करने की आवश्यकता नहीं है।

इस प्रयास करें:

void assignDepth(Tree T, int depth) 
{ 
    if(T!=NULL) 
    { 
     assignDepth(T->left, depth+1); 
     T->depth = depth; 
     assignDepth(T->right, depth+1); 
    } 
} 

Answer 2

ठीक है, शुरुआत के लिए, आप के बाद वेतन वृद्धि/कमी का उपयोग कर रहे, तो आप शायद मतलब सही काम के लिए ++depth/--depth और बाकी वापसी;

इसके अलावा, संदर्भ सूचक के रूप में पॉइंटर क्यों पास करते हैं?

Answer 3

int assignDepth(Tree &T, int depth) 

आप एक treeNode के सूचक के रूप Tree को परिभाषित किया है। आपको संदर्भ द्वारा इसे पास करने की आवश्यकता नहीं है। आप जिस नोड को इंगित करते हैं उस नोड को संशोधित कर सकते हैं।

{ 
    if(T!=NULL) 
    { 
     depth = assignDepth(T->left, depth++); 

पोस्टफ़िक्स ++ सुनिश्चित करता है कि आप मूल depth नीचे गुजर रहे हैं। यह वही नहीं है जो आप चाहते हैं। इससे पहले depth बढ़ाएं, और फ़ंक्शन परिणाम के रूप में इसे वापस करने के बारे में भूल जाएं।

T->depth = depth; 

यह ठीक है।

 depth = assignDepth(T->right, depth++); 

पिछले पुनरावर्ती कॉल के लिए के रूप में समान है, सिवाय इसके कि यहाँ आप बिल्कुल depth संशोधित नहीं करना चाहिए, क्योंकि यह पहले से ही वृद्धि की गई है।

} 
    else //leaf 
     return depth--; 

आप किसी भी गहराई से जानकारी वापस जाने के लिए की आवश्यकता नहीं है (या एक अनकहा आवश्यकता है कि है?)।

} 

चीयर्स & hth।,

Answer 4

1. एक बार जब आप एक पत्ता नोड पहुँच गए हैं, तो आप, इसकी गहराई किसी भी अधिक की परवाह नहीं तो वापसी मान कुछ भी नहीं पूरा करने के लिए प्रकट होता है है।

2. दो कथनों में:

   depth = assignDepth(T->left, depth++); 
   // and 
   depth = assignDepth(T->right, depth++); 
   

आप एक बीच के अनुक्रम बिंदु के बिना depth को संशोधित करने में दो बार (हालांकि ऐसा लगता है जैसे होना चाहिए से अपरिभाषित व्यवहार है, वहाँ है नहीं के बीच एक दृश्य बिंदु असाइनमेंट के दाएं और बाएं किनारे)।

Answer 5

1. नोड न्यूल होने पर आप वापस क्यों आ रहे हैं। आपके विनिर्देश के अनुसार आपको किसी भी गहराई को वापस करने की आवश्यकता नहीं है

2. अन्य मामले में आपको केवल गहराई में वृद्धि करने और फ़ंक्शन कॉल पर भेजने की आवश्यकता है। निम्नलिखित कोड के अपने संस्करण है

   शून्य assignDepth (ट्री & टी, पूर्णांक गहराई) { यदि (टी == शून्य) वापसी; अन्य { टी-> गहराई = गहराई; अगर (टी-> बाएं! = एनयूएलएल) असाइन डीपथ (टी-> बाएं, गहराई + 1); अगर (टी-> दाएं! = एनयूएलएल) असाइन डेपथ (टी-> दाएं, गहराई + 1); } }

Answer 6

मैं नोड प्रकार अलग-अलग लिए थोड़ी ज्यादा जटिल डिजाइन है और ऐसा किया, तो मैं आईडी शेयर सोचा।

यदि आपके पास एक पेड़ है जो नोड से नोड (बाइनरी, यूनरी इत्यादि) में भिन्न होता है तो नोड्स प्रकार की जांच करने के लिए गंदा एम्बेडेड आईएफ से बचने के लिए पारंपरिक विधि को सरल बनाना उचित है।

दो कार्य:

• 1: जड़ से, प्रत्येक नोड के माध्यम से चलाने के लिए और recursivly ही बुला और हर माता-पिता के लिए 1 जोड़कर जड़ तक इसकी दूरी की जाँच करें। प्रत्येक नोड को स्टोर करने के लिए एक गहराई चर दें।
• 2: पेड़ में नोड्स के पूर्ण सेट से प्रत्येक नोड गहराई के विरुद्ध MAX चेक चलाएं, उच्चतम संख्या पेड़ के की गहराई के बराबर होगी।

इस तरह से प्रसंस्करण स्पष्ट प्रकार की जांच को हटा देता है और नोड की गणना करता है चाहे उसके पास एक, दो या सौ बच्चे हों।

आशा इस कोई मदद करता है!