Harjoitukset viikkoharjoitussessioon 9¶

Tehtävä 1¶

Tässä tehtävässä käytetään alla olevaa puuta. (puun juuri on “8”)

Sinulla on mahdollisuus päästä käsiksi juurisolmun osoittimeen

Kaikki solmut käyttävät seuraavan näköistä structia:

struct Node {
  int key=NO_KEY;
  Node* parent = NO_NODE;
  std::unordered_set<Node*> children = {};
}

Jossa vakiot ovat seuraavat:

int NO_KEY = -1;
Node* NO_NODE = nullptr;

Jokaisesta puun solmusta on olemassa uniikki reitti juureen. Esimerkiksi reitti solmusta, jonka avain on 4 on seuraavan näköinen: { 4, 7, 6, 8 }.

Tee C++ funktio, joka tuottaa unordered_set<std::deque<int>>:in reiteistä jokaisesta solmusta juurisolmuun kun funktiolle annetaan osoitin juurisolmuun.

std::unordered_set<std::deque<int>> get_paths_to_root(Node* node){
  // TODO
}

Reittien järjestyksellä ei ole merkitystä, mutta yksittäisen reitin järjestys tulee aina olla halutusta solmusta kohti juurisolmua (ja viimeisenä sisältää juurisolmu) kuten esimerkissäkin.

Jos haluat, voit tehdä tehtävän pseudokoodilla.