Course topic 8 exercises¶

Trees¶

Below is a tree. Answer the following based on that tree. (You can find info on trees on course topic 8 lecture slides, for example):

Note. Write answers uncapitalized, in alphabetic order, and use comma to separate items.

C++ structs for a node in the above tree¶

In the following two exercises, you need to select from the given C++ structs those that can be used as a tree node for the tree presented above.

Please note that you have to assume that there are no other C++ structs or classes in the code aside from the given one. In addition, you need to save the information stored in a node with the correct data type.

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;
};

Pre-order traversal¶

In-order traversal¶

Post-order traversal¶

Iterator invalidation¶

All the following three (broken) functions can be found from the updated repository under the directory wk04_trees/iterator_invalidation. You can run both the functions and the tests run by the graders locally using Qt Creator. Tests can be run by clicking the run button, which runs all the tests, or by running each individual test case, adjusting the command line parameters accordingly. Alternatively, you can run the tests via the command line by providing the parameters when running the compiled program.

If you want to test the first function with the second test for that function, change the command line parameters to be 1 2. If on the other hand you want to test the second function with the third test (random values) with a vector with 20 elements, change the command line parameters to be 2 3 20

The size parameter (third number) is optional, and will not have effect on every test, by default the parameter has a value of 10. Two first parameters are compulsory. If you try to run a test function which does not exist, the program will print an error related to this.