Родословно дърво

Да се напише програма, която позволява да се въведе родослово дърво (като показаното на схемата) и след това отпечатва:

  1. родословно дървоимето на всеки човек и неговите родители
  2. предците ни по бащина линия и тези по майчина
  3. всички предци – мъже и всички предци – жени
  4. всичките ни предци, чиито родители не са ни известни
  5. има ли в рода ни човек с дадено име (например Ана)
  6. цялата ни фамилия, като имената на хората са изредени с запетаи
  7. цялата ни фамилия, като се започне от най-възрастните
  8. цялата ни фамилия в реда: майка, баща, син
  9. цялата ни фамилия в реда: майка, син, баща
  10. всичките ни предци, за които знаем родителите
  11. за колко поколения назад имаме информация
  12. дали двама души са мъж и жена
  13. дали двама души са баща и син
  14. дали един човек е наследник на друг
Публикувано в 12в с етикети . Постоянна връзка.

2 коментара по Родословно дърво

  1. Данаил каза:

    Ето кодът с примерно решение на точки 1-5, който можете да използвате за отправна точка:

    #include <cstdlib>
    #include <iostream>
    #include <string.h>
      
    using namespace std;
      
    // структура, която съхранява данните за един елемент
    struct tree {
        char ime[20];
        tree* parent;
        tree* left;
        tree* right;
    };
      
    // добавя елемент в дървото
    tree* insert_tree(char ime[],
                      tree* parent,
                      tree* left, 
                      tree* right) {
        tree* p;
      
        p = new tree;
        p->parent = parent;
        p->left = left;
        if (left) left->parent = p;
        p->right = right;
        if (right) left->parent = p;
        strcpy(p->ime, ime);
         
        return p;
    }
      
    // търсене на стойност в дървото
    tree* search_tree(tree* t, char ime[]) {
        // ако няма дърво, няма какво да търсиме
        if (t == NULL) return NULL;
        // ако сме попаднали на точният елемент - също
        if (strcmp(t->ime, ime) == 0) return t;
        // търсим в едното, после в другото поддърво
        tree* p = search_tree(t->left, ime);
        if (p) return p;
        else return search_tree(t->right, ime);
    }
      
    // изтриване на цялото дърво
    void delete_tree(tree* &t) {
        // ако няма дърво, няма какво да изтриваме
        if (t == NULL) return;
        // изтриваме поддърветата
        delete_tree(t->left);
        t->left=NULL;
        delete_tree(t->right);
        t->right=NULL;
        // изтриваме самият елемент
        delete t;
        t=NULL;
    }
      
    // отпечатване на всеки елемент и неговите родители
    void print_tree_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на човека
        cout<<t->ime;
        // отпечатваме наследниците му (за задачата там съхраняваме родителите му)
        if (t->left) cout<< " Bashta: "<<t->left->ime;
        if (t->right) cout<< " Maika: "<<t->right->ime;
        cout<<endl;
        // изпълняваме същото за поддърветата
        print_tree_children(t->left);
        print_tree_children(t->right);
    }
    
    
    // отпечатване на всеки елемент от дървото
    void print_tree(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на човека
        cout<<t->ime<<endl;
        // изпълняваме същото за поддърветата
        print_tree(t->left);
        print_tree(t->right);
    }
    
    // отпечатване на наследниците отляво
    void print_left_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на наследниците отляво
        if (t->left) cout<< t->left->ime<<endl;
        // изпълняваме същото за поддърветата
        print_left_children(t->left);
        print_left_children(t->right);
    }
     
    // отпечатване на наследниците отдясно
    void print_right_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на наследниците отдясно
        if (t->right) cout<< t->right->ime<<endl;
        // изпълняваме същото за поддърветата
        print_right_children(t->left);
        print_right_children(t->right);
    }
    
    // отпечатване на листата
    void print_no_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // ако елемента е листо, отпечатваме го
        if ((t->left==NULL)&&(t->right==0)) cout<< t->ime<<endl;
        // изпълняваме същото за поддърветата
        print_no_children(t->left);
        print_no_children(t->right);
    }
      
    int main()
    {
        // създаваме празно дърво
        tree* t = NULL;
         
        // попълваме елементите в него
        t = insert_tree("Georgi", NULL,
                insert_tree("Ivan", NULL,
                  insert_tree("Andrei", NULL, NULL, NULL),
                  insert_tree("Ana", NULL, NULL, NULL)
                ), 
                insert_tree("Maria", NULL,
                  insert_tree("Boyan", NULL, NULL, NULL),
                  insert_tree("Tereza", NULL, NULL, NULL)
                ) 
            );
        // отпечатваме дървото
        cout<<"VSEKI ZAEDNO S NEGOVITE RODITELI:";
        print_tree_children(t);
    
        
        cout<<"\nRODITELI PO BASHTINA LINIA:\n";
        print_tree(t->left);
        cout<<"\nRODITELI PO MAICHINA LINIA:\n";
        print_tree(t->right);
    
        cout<<"\nRODITELI MAJE:\n";
        print_left_children(t);
        cout<<"\nRODITELI JENI:\n";
        print_right_children(t);
    
        cout<<"\nBEZ RODITELI:\n";
        print_no_children(t);
    
        cout<<"\nTARSENE NA ANA:\n";
        if(search_tree(t, "Ana"))
          cout<<"V roda vi ima Ana.\n";
        else cout<<"V roda vi niama Ana.\n";
        
        // освобождаваме заеманата памет
        delete_tree(t);
         
      
        return 0;
    }
  2. kaloyan каза:

    До 10 точка

    #include <cstdlib>
    #include <iostream>
    #include <string.h>
       
    using namespace std;
       
    // структура, която съхранява данните за един елемент
    struct tree {
        char ime[20];
        tree* parent;
        tree* left;
        tree* right;
    };
       
    // добавя елемент в дървото
    tree* insert_tree(char ime[],
                      tree* parent,
                      tree* left,
                      tree* right) {
        tree* p;
       
        p = new tree;
        p->parent = parent;
        p->left = left;
        if (left) left->parent = p;
        p->right = right;
        if (right) left->parent = p;
        strcpy(p->ime, ime);
          
        return p;
    }
       
    // търсене на стойност в дървото
    tree* search_tree(tree* t, char ime[]) {
        // ако няма дърво, няма какво да търсиме
        if (t == NULL) return NULL;
        // ако сме попаднали на точният елемент - също
        if (strcmp(t->ime, ime) == 0) return t;
        // търсим в едното, после в другото поддърво
        tree* p = search_tree(t->left, ime);
        if (p) return p;
        else return search_tree(t->right, ime);
    }
       
    // изтриване на цялото дърво
    void delete_tree(tree* &t) {
        // ако няма дърво, няма какво да изтриваме
        if (t == NULL) return;
        // изтриваме поддърветата
        delete_tree(t->left);
        t->left=NULL;
        delete_tree(t->right);
        t->right=NULL;
        // изтриваме самият елемент
        delete t;
        t=NULL;
    }
       
    // отпечатване на всеки елемент и неговите родители
    void print_tree_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на човека
        cout<<t->ime;
        // отпечатваме наследниците му (за задачата там съхраняваме родителите му)
        if (t->left) cout<< " Bashta: "<<t->left->ime;
        if (t->right) cout<< " Maika: "<<t->right->ime;
        cout<<endl;
        // изпълняваме същото за поддърветата
        print_tree_children(t->left);
        print_tree_children(t->right);
    }
     
     
    // отпечатване на всеки елемент от дървото
    void print_tree(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на човека
        cout<<t->ime<<endl;
        // изпълняваме същото за поддърветата
        print_tree(t->left);
        print_tree(t->right);
    }
     
    // отпечатване на наследниците отляво
    void print_left_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на наследниците отляво
        if (t->left) cout<< t->left->ime<<endl;
        // изпълняваме същото за поддърветата
        print_left_children(t->left);
        print_left_children(t->right);
    }
     
    // отпечатване на наследниците отдясно
    void print_right_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме името на наследниците отдясно
        if (t->right) cout<< t->right->ime<<endl;
        // изпълняваме същото за поддърветата
        print_right_children(t->left);
        print_right_children(t->right);
    }
     
    // отпечатване на листата
    void print_no_children(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // ако елемента е листо, отпечатваме го
        if ((t->left==NULL)&&(t->right==0)) cout<< t->ime<<endl;
        // изпълняваме същото за поддърветата
        print_no_children(t->left);
        print_no_children(t->right);
    }
    
    // отпечатване на цялата ни фамилия, като имената на хората са изредени с запетаи
    void print_all_zapetai(tree* t, bool first) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме имената
        if (first) {
            cout<< t->ime <<", ";
            first=false;
        }
        if (t->left) cout<< t->left->ime <<", ";
        if (t->right) cout<< t->right->ime <<", ";
        // изпълняваме същото за поддърветата
        print_all_zapetai(t->left, first);
        print_all_zapetai(t->right, first);
    }
    
    // отпечатване на цялата ни фамилия, като се започне от най-възрастните
    void print_all_vazrastni(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // изпълняваме същото за поддърветата
        print_all_vazrastni(t->left);
        print_all_vazrastni(t->right);
        // отпечатваме имената
        if (t->left) cout<< t->left->ime <<", ";
        if (t->right) cout<< t->right->ime <<", ";
        if (t->left != 0 && t->right != 0) cout<<t->ime;
    }
    
    // отпечатване на цялата ни фамилия(майка, баща, син)
    void print_all_mbs(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме имената
        if (t->right) cout<< t->right->ime <<", ";
        if (t->left) cout<< t->left->ime <<", ";
        if (t) cout<<t->ime<<endl;
        // изпълняваме същото за поддърветата
        print_all_mbs(t->left);
        print_all_mbs(t->right);
    }
    
    // отпечатване на цялата ни фамилия(майка, син, баща)
    void print_all_msb(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме имената
        if (t->right) cout<< t->right->ime<<" ";
        if (t) cout<<t->ime<<" ";
        	if(t->left == 0 && t->right == 0) cout<<endl;
    	if (t->left) cout<< t->left->ime <<endl;
        // изпълняваме същото за поддърветата
        print_all_msb(t->left);
        print_all_msb(t->right);
    }
    
    // всичките ни предци, за които знаем родителите
    void print_all_bez_lista(tree* t) {
        // ако няма дърво, няма и нищо за отпечатване
        if (t == NULL) return;
        // отпечатваме имената
        if(t->left && t->right) cout<<t->ime<<endl;
        // изпълняваме същото за поддърветата
        print_all_bez_lista(t->left);
        print_all_bez_lista(t->right);
    }
    
    int main()
    {
        // създаваме празно дърво
        tree* t = NULL;
          
        // попълваме елементите в него
        t = insert_tree("Georgi", NULL,
                insert_tree("Ivan", NULL,
                  insert_tree("Andrei", NULL, NULL, NULL),
                  insert_tree("Ana", NULL, NULL, NULL)
                ),
                insert_tree("Maria", NULL,
                  insert_tree("Boyan", NULL, NULL, NULL),
                  insert_tree("Tereza", NULL, NULL, NULL)
                )
            );
        // отпечатваме дървото
        cout<<"VSEKI ZAEDNO S NEGOVITE RODITELI:";
        print_tree_children(t);
     
         
        cout<<"\nRODITELI PO BASHTINA LINIA:\n";
        print_tree(t->left);
        cout<<"\nRODITELI PO MAICHINA LINIA:\n";
        print_tree(t->right);
     
        cout<<"\nRODITELI MAJE:\n";
        print_left_children(t);
        cout<<"\nRODITELI JENI:\n";
        print_right_children(t);
     
        cout<<"\nBEZ RODITELI:\n";
        print_no_children(t);
     
        cout<<"\nTARSENE NA ANA:\n";
        if(search_tree(t, "Ana"))
          cout<<"V roda vi ima Ana.\n";
        else cout<<"V roda vi niama Ana.\n";
        
        cout<<"\nVSICHKI IZREDENI S ZAPETAI:\n";
        print_all_zapetai(t, true);
        cout<<endl;
        
        cout<<"\nVSICHKI KATO SE ZAPOCHNE OT NAI-VAZRASTNITE\n";
        print_all_vazrastni(t);
        cout<<endl;
        
        cout<<"\nVSICHKI V REDA MAIKA, BASHTA, SIN\n";
        print_all_mbs(t);
        
        cout<<"\nVSICHKI V REDA MAIKA, SIN, BASHTA\n";
        print_all_msb(t);
        
        cout<<"\nVSICHKI ZA KOITO ZNAEM RODITELITE\n";
        print_all_bez_lista(t);
         
        // освобождаваме заеманата памет
        delete_tree(t);
          
       
        return 0;
    } 

Вашият коментар