Kurssiaiheen 8 tehtävät¶

Puut¶

Tarkastele alla olevaa puuta, ja vastaa seuraaviin kysymyksiin tämän puun perusteella. (Lisää tietoa puista löytyy esimerkiksi kurssiaiheen 8 luentomateriaaleista):

Huomaa. Kirjoita vastaukset pienillä kirjaimilla, aakkosjärjestyksessä ja käytä pilkkua kohteiden erottelussa.

C++ structeja yllä olevalle puun solmulle¶

Seuraavissa kahdessa tehtävässä sinun tulee valita esitetyistä C++ structeista ne, joita voidaan käyttää yllä esitetyn puun solmuina.

Huomaathan, että tehtävissä tulee olettaa, että annetun structin lisäksi muu koodi ei sisällä structeja tai luokkia. Ja lisäksi huomioi, että solmussa täytyy tallettaa solmun sisältämä tieto oikealla tietotyypillä.

Struct A

1
2
3
4
5

struct Node {
   Node* parent = nullptr;
   char value;
   std::unordered_set<Node*> children = {};
};

Struct B

1
2
3
4

struct {
   char value;
   std::vector<Node*> children
};

Struct C

1
2
3
4
5

struct TreeNode {
   char data;
   Node* leftChild = nullptr;
   Node* rightChild = nullptr;
};

Struct D

1
2
3
4
5

struct Node {
   Node* parent = nullptr;
   char value;
   std::vector<Node*> children = {};
};

Struct E

1
2
3
4
5

struct TreeNode {
   char data;
   TreeNode* leftChild = nullptr;
   TreeNode* rightChild = nullptr;
};

Struct F

1
2
3
4
5

struct Node {
   char data;
   Node* leftChild = nullptr;
   Node* rightChild = nullptr;
};

Struct G

1
2
3
4
5

struct Node {
   Node* parent;
   Node* data;
   std::pair<Node*,Node*> children;
};

Struct H

1
2
3
4
5

struct Node {
   Node* parent;
   double data;
   std::pair<Node*,Node*> children;
};

Struct I

1
2
3
4
5

struct Node {
   Node* parent;
   char data;
   std::pair<Node*,Node*> children;
};

Struct J

1
2
3
4
5

struct Node {
   Node* parent;
   bool data;
   std::pair<Node*,Node*> children;
};

Esijärjetys¶

Välijärjestys¶

Jälkijärjestys¶

Iteraattoreiden mitätöityminen¶

Kaikki kolme alla olevaa (rikkinäistä) funktiota löytyvät päivitetystä reposta hakemistosta wk04_trees/iterator_invalidation. Funktioita ja graderien ajamia testejä voi ajaa myös paikallisesti, se onnistuu Qt Creatorin kanssa vaihtamalla komentojonoparametrit ja komentojonoa käyttäen antamalla parametrit ohjelmaa ajettaessa. Jos jätät parametrit antamatta, ajetaan tällöin kaikki testit.

Jos haluat testata ensimmäistä funktiota siihen liitetyllä testillä 2, vaihda komentojonoparametreiksi 1 2. Jos taas haluat testata toista funktiota siihen liitetyllä testillä 3 (satunnaiset arvot) kahdenkymmenen alkion sisääntulovektorilla vaihda komentojonoparametreiksi 2 3 20.

Koon määrittelevä (eli kolmas numero) komentojonoparametri ei ole pakollinen eikä vaikuta kaikkiin testeihin, oletuksena koko on 10. Kaksi ensimmäistä parametria ovat pakollisia, jos yrität ajaa jollekin funktiolle testiä, jota ei ole olemassa, ohjelma tulostaa tästä virheen.