0

Написала функцию 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);



}
4
  • странная конструкция. Обычно, когда реализуют дерево через массив исходят из того, что 0-вой элемент - это корень дерева, 1-й его левый потомок, а 2-й правый. Дальше получается, что 3-й это левый потомок 1-ого и т.д. Если не ошибаюсь, это еще называют пирамидальной сортировкой. 15 авг 2018 в 10:07
  • Да, такое я делала. Просто теперь хотела через родителей попробовать
    – NN_05
    15 авг 2018 в 10:08
  • ну а почему не сделать соответствующий класс для дерева и работать с ним напрямую, а не через массив? Да и тут непонятно что у вас с элементами должно происходить, так как дерево подразумевает сортировку элементов. 15 авг 2018 в 10:10
  • Просто дали задание именно сделать с помощью рекурсивной функции и для такого массива, где члены - это родители. HeapSort я делала, теперь хотела вот так
    – NN_05
    15 авг 2018 в 10:12

1 ответ 1

2

Главное - у Вас дважды определено 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 не увидел, а вот вывод важных параметров после входа в функцию сразу показал, где собака зарыта.

4
  • Сделала вот вместо i children[i], но в том же тесте [4 -1 4 1 1 ] все равно ответ hight = 1 .
    – NN_05
    15 авг 2018 в 10:01
  • Не понимаю, почему(( Вроде же все правильно
    – NN_05
    15 авг 2018 в 10:16
  • уберите объявление n из main
    – MBo
    15 авг 2018 в 10:16
  • Ура, спасибо вам большое , она заработала! Извините, за невнимательность(
    – NN_05
    15 авг 2018 в 10:22

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.