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

Да се напишат функции, която в дадено наредено двоично дърво намират сумата на:

  1. всички върхове в дървото
  2. всички поддървета в дървото
  3. вътрешните върхове в дървото
  4. върховете от всяко едно ниво на дървото
Публикувано в 12а с етикети . Постоянна връзка.

2 Responses to Брой на върхове в дърво

  1. dreanor каза:
    #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;
    }
    

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

    • Данаил каза:

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

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