An introduction to trees
On this page
This lesson contains approximately 47 minutes of video content.
An introduction to trees
Binary trees
Trees with unbound branching
Other tree representations
In this activity, you will implement a
Your
How do I interact with
If you're curious about how you should interact with an
BranchingTree<T>. The BranchingTree<T> type will contain a single private data member named root_ that is typed Node<T>*. We will now introduce the types involved in this assignment and what you're responsible for implementing.
Node<T>
| public: | |
Node<T>* parent |
Points to a respective node's parent node in the tree structure |
std::list<Node<T>*> children |
A list of pointers to the individual node's children |
T data |
T data, the data stored in the node. |
BranchingTree<T>
Your BranchingTree<T> implementation will define three public behaviors and one private data member:
| public: | |
BranchingTree(const T& data) |
Parameterized constructor: initializes a new BranchingTree<T> object with a single node with data pointed to by root_. |
const Node<T>* GetRoot() const |
Completed for you. Returns a pointer pointing to the tree's root node (read-only). |
Node<T>* GetRoot() |
Completed for you. Returns a pointer pointing to the tree's root node. |
| private: | |
Node<T>* root_;
| Pointer to the root of the BranchingTree<T>. |
Non-member helper functions
You will also define two non-member helper function templates.Node<T>* InsertChild(Node<T>* parent, T data) |
If the parent's children list does not contain a node with data, inserts a new node whose data is data and parent is parent into the parent's children list; otherwise, throws an exception. Returns the address of the new node. |
unsigned int FindDepth(const Node<T>* node) |
Returns the depth of the node in a BranchingTree<T> object. A Node<T> whose parent is nullptr has a depth of 0. |
Both functions should throw an exception if the passed Node<T>* is nullptr.
How do I interact with std::list?
If you're curious about how you should interact with an std::list, consider this example:
std::list l;
l.push_back(11);
l.push_back(12);
for (const int& i : l) {
std::cout << i << std::endl;
} #include <iostream>
#include "branching_tree.hpp"
int main() {
/* Example Usage */
// BranchingTree<int> bt(11);
// auto root = bt.GetRoot();
// auto node12 = InsertChild(root, 12);
// auto node12_depth = FindDepth(node12);
}
#ifndef BRANCHING_TREE_HPP
#define BRANCHING_TREE_HPP
#include "node.hpp"
template<typename T>
class BranchingTree {
public:
BranchingTree(const T& data);
const Node<T>* GetRoot() const {return root_;}
Node<T>* GetRoot() {return root_;}
private:
Node<T>* root_;
};
// helper function declarations
template<typename T>
Node<T>* InsertChild(Node<T>* parent, T data);
template<typename T>
unsigned int FindDepth(const Node<T>* node);
// implementations
template<typename T>
BranchingTree<T>::BranchingTree(const T& data) {
// does something;
}
template<typename T>
Node<T>* InsertChild(Node<T>* parent, T data) {
// does something;
return nullptr;
}
template<typename T>
unsigned int FindDepth(const Node<T>* node) {
// does something else;
return 0;
}
#endif
#include "branching_tree.hpp"
#ifndef NODE_HPP
#define NODE_HPP
#include <list>
template<typename T>
struct Node {
T data;
Node<T>* parent = nullptr;
std::list<Node<T>*> children;
};
#endif
> Click Run to compile and run your code.