كود Newton’s Apple

السلام عليكم ورحمه الله وبركاته

مشكلة تفاحة نيوتن

Newton’s Apple

الترجمه من قوقل :

وصف

شجرتين ثنائي (وتسمى A و B) وتعادل إذا وفقط إذا كان أحد الشروط التالية اثنين

يحمل:

1. على حد سواء الأشجار فارغة. أو،

2. العقد الجذرية على حد سواء من الأشجار على قدم المساواة، وإما:

(أ) الشجرة يسار ما يعادل الشجرة الأيسر من وباء والشجرة الفرعية (أ) هو حق من

أي ما يعادل الشجرة حق باء أو،

(ب) والشجرة يسار ما يعادل الشجرة حق من وباء والشجرة الفرعية (أ) هو حق من

أي ما يعادل الشجرة الفرعية اليسار من B.

على سبيل المثال، الأشجار الثلاثة على يسار الشكل التالي كلها يعادل بعضها البعض ولكن

أي ما يعادل شجرة أقصى اليمين.

كتابة البرنامج الذي يحدد ما إذا كان شجرتين ثنائي معين وتعادل أم لا.

نسق إدخال

وسيتم اختبار البرنامج على عدد من حالات الاختبار. في السطر الأول من إدخال يحتوي على

صحيح D الذي يمثل عدد حالات الاختبار. يتم تحديد كل حالة اختبار على سطرين.

السطر الأول يحدد أول شجرة، مع الشجرة الثاني المحدد في السطر الثاني. كل شجرة

تم تحديد باستخدام ترميز POSTFIX اليسار إلى اليمين حيث يتم تحديد بشكل واضح كل الشجرة فارغ

باستخدام الكلمة الأساسية لا شيء. جميع البيانات في شجرة هي أعلى حالة الأحرف. تم تحديد نهاية السطر

باستخدام نهاية الكلمة. على سبيل المثال، تم تحديد شجرة على الجانب الأيسر من هذا الرقم على النحو التالي:

لا شيء لا شيء لا شيء لا شيء لا شيء جي اف سي لا شيء لا شيء لا شيء D E B A نهاية

تنسيق الإخراج

لكل حالة اختبار، طباعة على سطر منفصل، فإن كلمة "صحيح" في حال الأشجار هما ما يعادلها.

طباعة خلاف ذلك "كاذبة".

صفحة 10 من 16

حالات الاختبار 2 في العينة التالية I / O تمثل أشجار 4 رسمها على السابقة

صفحة (من اليسار إلى اليمين)

اكواادي

#include <stdio.h> 
#include <stdlib.h> 


struct node 
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 

bool areIdentical(struct node * root1, struct node *root2) 
{ 
      if(root1 == NULL && root2 == NULL) 
        return true; 

    if(root1 == NULL || root2 == NULL) 
        return false; 

    return (root1->data == root2->data   && 
            areIdentical(root1->left, root2->left) && 
            areIdentical(root1->right, root2->right) ); 
} 
bool isSubtree(struct node *B, struct node *A) 
{ 
      if (A == NULL) 
        return true; 

    if (B == NULL) 
        return false; 


    if (areIdentical(B, A)) 
        return true; 


    return isSubtree(B->left, A) || 
           isSubtree(B->right, A); 
} 
struct node* newNode(int data) 
{ 
    struct node* node = 
        (struct node*)malloc(sizeof(struct node)); 
    node->data  = data; 
    node->left  = NULL; 
    node->right = NULL; 
    return(node); 
} 
int main() 
{ 

    struct node *B        = newNode(a); 
    B->right              = newNode(b); 
B->right->right       = newNode(d); 
    B->left               = newNode(f); 
    B->left->left         = newNode(g); 
    B->right->right->right  = newNode(e); 


    struct node *A    = newNode(a); 
    A->right          = newNode(f);
    A->right->right       = newNode(g); 
    A->left           = newNode(b); 
    A->left->right    = newNode(d);
A->left->right->right  = newNode(e);
A->left->left         = newNode(c);  


    if( isSubtree(B, A) ) 
        printf("Tree A is subtree of tree B"); 
    else
        printf("Tree A is not a subtree of tree B"); 

    getchar(); 
    return 0; 
}

اتمنى مساعدتكم

هل الحل للموضوع صحيح ام خطأ ؟