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.
Changing command line parameters in Qt Creator¶
After opening the project, from the left ribbon menu in Qt Creator,
select projects (wrench icon).
From the opened menu, on the left part under the Build & Run section
select run. You may now find the setting for Command line arguments,
you can paste the arguments (such as 1 2) there.
Iterator invalidation 1, ascendingVector¶
Function ascendingVector creates a vector with ascending numbers from 0 - (n-1).
Fix it, push the changes to your git repository and send it for grading.
Your answer should be in the file wk04_trees/iterator_invalidation/invalidation1.cc
A+ presents the exercise submission form here.
Iterator invalidation 2, eraseEverySecond¶
Function eraseEverySecond erases every other element from the vector given as a reference parameter.
Example: {1, 2, 3, 4} -> {1, 3}
Fix it, push the changes to your git repository and send it for grading.
Your answer should be in the file wk04_trees/iterator_invalidation/invalidation2.cc
A+ presents the exercise submission form here.
Iterator invalidation 3, duplicateEvenRemoveUneven¶
Function duplicateEvenRemoveUneven as the name implies removes every odd element and duplicates all the even elements in the vector given as a reference parameter.
Example: {1, 2, 3, 4} -> {2, 2, 4, 4}
Fix it, push the changes to your git repository and send it for grading.
Your answer should be in the file wk04_trees/iterator_invalidation/invalidation3.cc
A+ presents the exercise submission form here.