BST traversals
This lesson contains approximately 20 minutes of video content.
Inorder traversal
Correction: In this video,
Node<T>* objects should have been typed BinaryTreeNode<T1,T2>*. Also, return type of InorderTreeWalk should be void in this example. Sorry y'all! Preorder traversal
Correction: In this video,
Node<T>* objects should have been typed BinaryTreeNode<T1,T2>*. Also, return type of PreorderTreeWalk should be void in this example. Sorry y'all! Postorder traversal
Correction: In this video,
Node<T>* objects should have been typed BinaryTreeNode<T1,T2>*. Also, return type of PostorderTreeWalk should be void in this example. Sorry y'all! Activity: Compute the average of integer values contained in a binary search tree
Graded Playground Autograder
Activity Prompt:
In this activity, you will implement an algorithm that computes the average integer value stored in the nodes of an IntegerTree. We have defined IntegerTree as non-templated Binary Search Tree that stores integer data in Node<int>s.
IntegerTree and the class template Node<T>. You will find definitions for these types in the relevant files in your workspace. Here is the public member function of IntegerTree that you're required to define:
double AverageValue(); |
This behavior returns the average (arithmetic mean) of the values stored in the nodes of an IntegerTree. To compute the average, you'll need to accumulate the node values and divide that total by the number of nodes in the tree. You're encouraged to define helper function(s) that are invoked by AverageValue to perform this computation; you can solve this problem iteratively (with an std::stack) or recursively. A recursive implementation is recommended. If the tree is empty, throw an exception. |
We will only transmit the contents of your integer_tree.hpp and integer_tree.cc files to the grader. Let's get started!
#include "integer_tree.hpp"
#include <iostream>
int main() {
}
#ifndef INTEGER_TREE_HPP
#define INTEGER_TREE_HPP
#include "node.hpp"
class IntegerTree {
public:
// assigned
double AverageValue();
// provided
IntegerTree() = default;
private:
Node<int>* root_ = nullptr;
};
#endif
#include "integer_tree.hpp"
#include <stdexcept>
#ifndef NODE_HPP
#define NODE_HPP
template <typename T>
struct Node {
int value = 0; // NOLINT
Node<T>* parent = nullptr; // NOLINT
Node<T>* left = nullptr; // NOLINT
Node<T>* right = nullptr; // NOLINT
Node() = default;
Node(int value) : value(value) {}
};
#endif
Submit is not supported in this site.