बाइनरी ट्री में, लगता है कि कितने दादा

Question

        8 
           / \ 
           4   12 
          /\  /\ 
          3 6  2 1 
         /\ /\ //\ 
         7 10 13 15 5 9 11 
              /
              14 

मैं इस उदाहरण में मैं केवल एक दादा, संख्या 12 (मुझे लगता है कि वह है केवल दो या जरूरत है, एक पेड़ के दादा को खोजने की जरूरत है केवल दो या तीन grandchildrens तीन पोते)।

int T(struct node * tree){ 
    int t = 0; 
    if (tree == NULL) 
     return 0; 
    if (tree->left && tree->right) 
    { //In this case i check if we NOT have all the four grandchildrens. 
     if (!((tree->left->left) && (tree->left->right) && (tree->right->left) && (tree->right->right))) 
     { 
      t = 1 + T(tree->left) + T(tree->right); 
      T(tree->left); 
      T(tree->right); 

     } 
     else 
     { 
      T(tree->left); 
      T(tree->right); 
     } 

    } 

    return t; 

} 

दुर्भाग्य से यह काम नहीं करता ... किसी ने मुझे इस के साथ मदद कर सकते हैं:

यह वही है मैं अब तक की कोशिश की है?

Answer 1

एक कुशल दृष्टिकोण परिणामों की एक जोड़ी को दोबारा लौटने के लिए है। वहाँ सी ++ में एक जोड़ी वापस जाने के लिए और अधिक सुरुचिपूर्ण तरीके हैं, लेकिन मैं सूचक द्वारा एक इनपुट के माध्यम से एक उत्पादन लौटने के पुराने kludgy सी रास्ते का उपयोग करेंगे:

int T2(struct node * tree, int* child_count) 
{ 
    int t = 0; // Count the things we are supposed to count 
    int g = 0; // Count grandchildren of the current node 
    if (tree == NULL) 
     return 0; 
    if (tree->left) 
    { 
     ++ *child_count; 
     t += T2(tree->left, &g); 
    } 
    if (tree->right) 
    { 
     ++ *child_count; 
     t += T2(tree->right, &g); 
    } 
    if (g==2 || g==3) 
     ++t; 
    return t; 
} 

int T(struct node * tree) {int dummy; return T2(tree, &dummy); } 

समारोह दो बातें एक साथ करता है। सरल काम यह है कि *child_count में वृद्धि करके यह अपने माता-पिता के पोते को गिनने में मदद करता है, और यह t में जमा करके मुख्य कार्य भी करता है।

---

नीचे दिए तरीक़े को समझने के लिए आसान हो सकता है, लेकिन कम सुरुचिपूर्ण है:

int T(struct node * tree) 
{ 
    struct node *c; 
    int t = 0; // Count the things we are supposed to count 
    int g = 0; // Count grandchildren of the current node 
    if (tree == NULL) 
     return 0; 
    if ((c=tree->left) != NULL) 
    { 
     g += (c->left != NULL) + (c->right != NULL); 
     t += T(c); 
    } 
    if ((c=tree->right) != NULL) 
    { 
     g += (c->left != NULL) + (c->right != NULL); 
     t += T(c); 
    } 
    if (g==2 || g==3) 
     ++t; 
    return t; 
} 

Answer 2

अगर आप बच्चे की गिनती कार्यों की एक जोड़ी, एक है कि बच्चों में गिना जाता है और एक कि मायने रखता परिचय यह आसान हो जाता है पोते:

int children(node* tree) 
{ 
    if (!tree) 
    { 
     return 0; 
    } 
    int count = 0; 
    if (tree->left) 
    { 
     count += 1; 
    } 
    if (tree->right) 
    { 
     count += 1; 
    } 
    return count; 
} 

int grandchildren(node* tree) 
{ 
    if (!tree) 
    { 
     return 0; 
    } 
    return children(tree->left) + children(tree->right); 
} 

int grandparents(node* tree) 
{ 
    if (!tree) 
    { 
     return 0; 
    } 
    int count = grandchildren(tree); 
    if (count == 2 || count == 3) 
    { 
     return 1 + grandparents(tree->left) + grandparents(tree->right); 
    } 
    else 
    { 
     return grandparents(tree->left) + grandparents(tree->right); 
    } 
}