Брой на върхове в дърво

2 коментара по Брой на върхове в дърво

1. dreanor каза:

   14 април, понеделник в 15:02

   #include <cstdlib>
   #include <iostream>
    
   using namespace std;
    
   // структура, която съхранява данните за един елемент
   struct tree {
       int value;
       tree* parent;
       tree* left;
       tree* right;
   };
    
   // добавя елемент в дървото
   void insert_tree(tree* &t, int value, tree* parent) {
       tree* p;
    
       // ако добавяме на върха на дървото
       if (t == NULL) {
           p = new tree;
           p->left = p->right = NULL;
           p->parent = parent;
           p->value = value;
           t = p;
       }
    
       // добавяне в съответното поддърво
       else if (value < t->value)
           insert_tree(t->left, value, t);
       else
           insert_tree(t->right, value, t);
    
   }
    
   //1)   
   int broi_vurhove(tree* t) {
       // ако няма дърво, няма какво да търсиме
       if (t == NULL) return 0;
       // връща броя на върховете на дървото
       return 1 + broi_vurhove(t->left) + broi_vurhove(t->right);
   }
    
   int main()
   {
       // създаваме празно дърво
       tree* t = NULL;
    
       // добавяме елементи в него
       int n;
       cout<<"Vavedete broi na elementite: ";
       cin>>n;
       cout<<"Vavedete "<<n<<" chisla, koito da zapisha v darvoto: ";
       int value;
       for(int i=0; i<n; i++) {
         cin>>value;
         insert_tree(t, value, t);
       }
    
       cout<<"Broi vurhove: ";
       cout<<broi_vurhove(t)<<endl;
    
       system ("pause");
       return 0;
   }
   

   Решението на първата задача.

   Влезте, за да отговорите
   • Данаил каза:

     14 април, понеделник в 23:15

     А, супер! Значи успяхте и до решение да стигнете – и то до правилното :-) Може би малко може да се оптимизира – да вика рекурсивните функции само ако има нужда – но пък така кодът на broi_vurhove() е пределно прост! Позволих си да махна функциите, които нямат отношение към задачата и демонстрацията им, за да може по-лесно да се види същественото. Надявам се да не възразявате…

     Влезте, за да отговорите