Рекурсивное вычисление высоты дерева

168
03 ноября 2018, 14:50

Написала функцию Hight(int r, int *mas), которая должна вычислять высоту дерева. Дерево представляется в виде массива чисел, где mas[i] = это родитель i - го ребенка. Если mas[i] == -1, то i-ый элемент - это корневой элемент дерева. Но почему то ответ неправильный, хотя вроде использовала правильный алгоритм. На тесте n = 5 с массивом [4 -1 4 1 1] hight= 1. Совсем не понимаю, почему так. Не ругайтесь, пожалуйста, за глупые вопросы. Только недавно начала изучать С++.

#include <iostream>
#include<vector>
using namespace std;
int n = 0;
int r = 0;
int max(int a, int b){
    return a > b ? a : b;
}
int Hight(int r, int *mas){
    int hight = 1;
    vector<int> children;
    for(int i = 0; i < n; ++i){
        if(mas[i] == r){
            children.push_back(i);
        }
    }
    for(int i =0; i < children.size(); ++i){
        hight = max(hight, Hight(i, mas) + 1);
    }
    return hight;
}
int main(){
    int n;
    cin>>n;
    int *mas = new int[n];
    for(int i = 0; i < n; ++i){
        cin>>mas[i];
        if(mas[i] == -1)
            r = i;
    }
    cout<<Hight(r, mas);

}
Answer 1

Главное - у Вас дважды определено n и в функции используется нулевое глобальное

Вот здесь:

for(int i =0; i < children.size(); ++i){
      hight = max(hight, Hight(i, mas) + 1);

в Hight передаётся индекс в векторе children, а должно быть children[i] (где содержится индекс в массиве mas)

https://ideone.com/IYcfxP

Посоветую почаще использовать отладку - глазами я про n не увидел, а вот вывод важных параметров после входа в функцию сразу показал, где собака зарыта.

READ ALSO
Как с помощью глобального хука отменить действие мыши?

Как с помощью глобального хука отменить действие мыши?

Есть мысль написать ремапер мышиНо для этого необходимо отменять определённые действия мыши

205
Сортировка компонентов в NetBeans

Сортировка компонентов в NetBeans

Подскажите пожалуйста, как установить сортировку компонентов в пакете по типуРаботаю в IDE NetBenas

154