Struktury danych/drzewo

pytanie zadane 31 marca 2020 w C i C++ przez Programmingc100 Bywalec (2,620 p.)

Witam, planuje napisać strukturę drzewa genealogicznego rodziny używając drzewa(chyba najbardziej się nada). I zastanawiam się jak to mogłoby wyglądać bo każdy węzeł chyba będzie musiał mieć w sobie dane o dwóch członkach rodziny np: I co jeśli dzieci będzie więcej niż 2 , należy użyć tablicy wskaźników?

dziadek/ babcia

syn/żona córka/mąż

struct 
{
  // dane
 struct *prawy;
struct *lewy;

}czlonek_rodziny;

2 odpowiedzi

odpowiedź 31 marca 2020 przez Artur_K Nowicjusz (240 p.)

Osobiście spróbowałbym ze strukturą obiektów, które miałyby wskaźnik do swojego rodzica. Rodzice dzieci mogą mieć ileś lub 0, ale dziecko musi mieć rodzica. Wskaźnik na mamę i tatę. Rodzice żeby nie pgubily pociech - tak jak mówisz - lista wskaźników.

komentarz 31 marca 2020 przez Programmingc100 Bywalec (2,620 p.)

Dlaczego wskaźnik na swojego rodzica? Jeśli na samej górze drzewa będzie babcia/dziadek to elementy drzewa nie powinny mieć wskaźników na swoje dzieci?

komentarz 31 marca 2020 przez Artur_K Nowicjusz (240 p.)

Takie 'wskazywanie' rodzic-dziecko i dziecko-rodzic może mieć znaczenie, żeby za często nie szukać po drzewie, czy grafie. Za każdym razem kiedy będziemy chcieli zapytać o najbliższą rodzinę to będzie można to wyciągnąć z obiektu, w innym przypadku będzie trzeba szukać w strukturze.

Korzeń drzewa (struktury) czyli seniorzy rodu, ich wskaźniki na rodziców, których możemy nie znać będą wskazywały null.

komentarz 1 kwietnia 2020 przez Programmingc100 Bywalec (2,620 p.)

Czyli to będzie B-drzewo ?

odpowiedź 31 marca 2020 przez tkz Nałogowiec (42,000 p.)

Nawet jeśli nazywa się „drzewo”, jest to zła struktura: wyobraź sobie dwóch braci, którzy poślubią dwie siostry.

Ogólna struktura grafów byłaby najlepsza (drzewo jest swoistą formą wykresu). Krawędź przenosi związek. Następnie możesz uruchomić algorytm znajdowania ścieżki (jak stara dobra dijkstra) tylko na krawędziach reprezentujących związek krwi.

Samo zadanie nie jest aż tak trywialne https://stackoverflow.com/questions/6163683/cycles-in-family-tree-software

komentarz 31 marca 2020 przez Programmingc100 Bywalec (2,620 p.)

Ale jakieś bardziej prymitywne drzewo genealogiczne można zrobić za pomocą struktury drzewa?

1	komentarz 31 marca 2020 przez tkz Nałogowiec (42,000 p.) Możesz zrobić za pomocą czego tylko chcesz, kwestia optymalności.

komentarz 31 marca 2020 przez Programmingc100 Bywalec (2,620 p.)

A w czym będzie to najprościej zrobić?

1	komentarz 31 marca 2020 przez tkz Nałogowiec (42,000 p.) Zależy jak bardzo chcesz rozbudować, ale drzewo wydaje się być proste.

komentarz 31 marca 2020 przez Programmingc100 Bywalec (2,620 p.)

Jak dla początkującego chyba wolałbym spróbować użyć drzewa bo to prostsze niż grafy

1	komentarz 1 kwietnia 2020 przez tkz Nałogowiec (42,000 p.) Wydaje Ci się, bo ich nie znasz, albo przynajmniej abstrakcyjnie tego nie łapiesz. Zrób dwa, nic nie stracisz.

komentarz 1 kwietnia 2020 przez Programmingc100 Bywalec (2,620 p.)

Dwa tzn i drzewo i graf?

1	komentarz 1 kwietnia 2020 przez tkz Nałogowiec (42,000 p.) Tak, dwa osobne projekty. Jedno opierające się na drzewie, drugi na grafach.

komentarz 1 kwietnia 2020 przez Programmingc100 Bywalec (2,620 p.)

#include <stdio.h>
#include <stdlib.h>

#define M 10 /// maximum numbers of children


struct family_tree
{
    char name_f[20];                   ///name of father family member
    char name_m[20];                   /// name of mother family member
    int age_f;
    int age_m;                         /// age of family member
    struct family_tree* children[M];    /// pointers to children
    struct family_tree *next;          /// pointer to next children
    struct family_tree *previous;      /// pointer to previous children


};

struct family_tree *root = NULL;

struct family_tree *add_members(struct family_tree *member)
{

    struct family_tree *new_member = (struct family_tree*)malloc(sizeof(struct family_tree));
    printf("Enter data of new  member of family: ");
    scanf("%s",new_member->name_f);
    scanf("%s",new_member->name_m);
    scanf("%d",&new_member->age_f);
    scanf("%d",&new_member->age_m);


}

int main()
{
  


    return 0;
}

Tak zaimplementowałem element główny drzewa, teraz robię dodawanie członków rodziny, tutaj tak samo jak w drzewie bianrnym trzeba będzię wywoływać to rekurencyjnie?