Struktura drzewa binarnego (rodzic ze wskaźnikami na dzieci).

0

Witam.
Musze napisać algorytm który stworzy drzewo i na jego podstawie wyszuka najbardziej wartościową drogę w podanej ilości ruchów.
Lecz problem zaczyna się z samym tworzeniem drzewa.
Na wejściu dostaje index rodzica i index dziecka (rodzic może mieć 2 dzieci).
Chciałem zrobić, aby rodzić miał 2 wskaźniki na swoje dzieci i tak dalej i tak dalej.
Jeśli ma tylko jedno dziecko albo wcale to wskaźniki ustawiam na nullptr;
Przykładowa wizualizacja takiego drzewa
o
/ \
o nullptr
/ \
nullptr o
/ \
... o o...

Kod wygląda następująco:
main()
Flavors to są punkty które musze zbierać po drodze


   int numberOfPaths = 0;
    scanf("%d", &numberOfPaths);

    int maxMoves;
    scanf("%d", &maxMoves);

    Path *tree = new Path[numberOfPaths+1];

    for(int i = 1 ; i < numberOfPaths+1 ;i++){
        tree[i] = *new Path(0);
    }

    for(int i = 0 ; i < numberOfPaths ; i++){
        int pathFrom;
        scanf("%d", &pathFrom);

        int pathTo;
        scanf("%d", &pathTo);

        int flavors;
        scanf("%d", &flavors);

       //Ustawiam wartosc temu węzłowi
        tree[pathTo].setFlavors(flavors);
       //Ustawiam rodzicowi wskaźnik na dziecko i tutaj pojawia się problem
        tree[pathFrom].setPath(&tree[pathTo]);
    }

Problem jest taki że gdy ustawiam wskaźnik (setPath() na dziecko to w debugerze widze, że ustawiam wskaźnik na całą tablice. )
Path to jest węzeł

class Path {
    Path * path1;
    Path * path2;
    int flavors;

public:

    Path(int _flavors): path1(nullptr), path2(nullptr), flavors(_flavors) { }

    void setPath(Path * path);

    int getFlavors();
    Path* getPath1(){
        return path1;
    }
    Path* getPath2(){
        return path2;
    }

    void setFlavors(int i);

    Path();
};
void Path::setPath( Path * path) {
    if(path1 == nullptr){
        path1 = path;
    }else{
        path2 = path;
    }
}

int Path::getFlavors() {

    return this->flavors;
}

void Path::setFlavors(int i) {
    this->flavors = i;

}

Path::Path() {
flavors = 0;
}

Screen z debuggera po kilku iteracjach z takiego wejścia:
5 2
1 2 2
2 3 10
2 4 8
4 5 11
4 6 8

user image

1

Przy takich danych wejściowych masz wyjście poza zakres tablicy.

numberOfPaths=5 maxMoves=2
pathFrom=1 pathTo=2 flavors=2
pathFrom=2 pathTo=3 flavors=10
pathFrom=2 pathTo=4 flavors=8
pathFrom=4 pathTo=5 flavors=11
pathFrom=4 pathTo=6 flavors=8


Path *tree = new Path[numberOfPaths+1];

numberOfPaths=5
pathTo=6:
tree[pathTo].setFlavors(flavors); <= wyjście poza zakres tablicy (maksymalny index to [5+1]-1 = 5)
tree[pathFrom].setPath(&tree[pathTo]); <= to samo co wyżej

0

Dzięki wielkie. Pomogło :)
Nie wiem tylko dlaczego w debuggerze cały czas wskaźnik który powinien wskazywać na obiekt, po rozwinięciu pokazuje tablice elementów.
I dlaczego tablica elementów ma nieskończenie wiele elementów skoro podałem rozmiar 6 ?

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0