Medis su nežinomu kiekiu šakų

Sveiki,

reikia padaryti medį, kuris nežinoma kiek turės šakų. Kaip siūlot padaryti?

Aš turiu tris idėjas, bet nežinau ar bent viena iš jų tinkama:

1. Sukurti rodyklių į kitas struktūras masyvą (bet nežinau ar galima).

2. Sukurti tarkim šaką next kaip stringą ir saugot šakų id, pvz: 3 4 15

3. Sukurti rodyklę atgal į tėvo šaką (bet ar tai skaitysis medis).

Lauksiu jūsų nuomonių :)

Žiūrint ką tau reikės daryti su tuo medžiu. Šiaip mažiausiai vietos naudojantis variantas būtų saugoti nuorodą (indeksą) į tėvinę viršūnę, tačiau tokiu atveju bus galima pereiti medį tik nuo lapų link šaknų.

struct node {
  int someData;
  int parent;
};

node tree[N];
tree[2].parent = 5; //antrai viršūnei tėvinė yra penkta viršūnė

Kitas variantas, tai saugoti grafui įprastu būdu. Bus galima pereiti nuo šaknies iki lapų:

struct node {
   int someData;
   list<int> childs;
}

node tree[N];
tree[5].childs.push_back(2); //antra viršūnė yra penktos viršūnės vaikas

Arba sukombinuoji abu variantus ir vaikštai kaip tik nori:

struct node {
  int someData;
  int parent;
  list<int> childs;
};

node tree[N];
tree[2].parent = 5;          //antrai viršūnei tėvinė yra penkta viršūnė
tree[5].childs.push_back(2); //antra viršūnė yra penktos viršūnės vaikas

Jei svarbu tik ryšiai tarp viršūnių ir pačios viršūnės nesaugo jokios informacijos, galima aprašyti dar paprasčiau:

list<int> childs[N];
int parents[N];

parents[2] = 5;
childs[5].push_back(2);