In the file treenode.h implement a template class TreeNode that represents a node in a binary search tree. It should have four publicmember variables:
computer science
Description
Binary Search Trees
In these questions you will be making
a Binary Search Tree template class.
Note that in answering these questions, you should not add any #include or using statements:
you must implement the functionality yourself, without using any additional
data structures from the standard library. I have added #include <memory> for std::unique_ptr, #include <utility> for std::pair, and #include <iostream>. If you have a convincing need for adding a
different #include please post in the forum on KEATS.
Make sure you don't commit any compiled code to your GitHub repository;
or if you choose to use an IDE, any large project directories created by your
IDE. You can make these on your machine, but don't commit or add them to your repository -- this
isn't what git is designed for.
Binary search
tree nodes [3 marks]
In the file treenode.h implement a
template class TreeNode that represents a node in a
binary search tree. It should have four publicmember variables:
- The data stored in that node.
The type of this should be a template argument.
- A unique_ptr for the left child of the node;
- A unique_ptr for the right child of the node;
- A pointer to the parent of the node (NB not a
unique_ptr)
Make a constructor that takes an item
of data, stores it in the node, and sets the parent pointer to nullptr.
Make a function setLeftChild(TreeNode*
child) that:
- stores child in the left unique_ptr
- sets the parent pointer of the child
to point to this
Write an analogous function setRightChild for setting
the right child of the node.
Make a function write that takes an
ostream reference, and prints to it:
- The result of calling write on the left child
(if there is one)
- A space character
- The data from the node
- A space character
- The result of calling write on the right child
(if there is one)
You should then be able to write,
e.g:
someNode->write(cout);
...to be able to print the subtree starting at some node to screen.
(NB write should be marked as const.)
To test your code, compile and run
TestTreeNode.cpp. A Makefile has been provided, run:
make TestTreeNode
...at the command line. This makes
four tree nodes, linked to each other, then prints out the tree.
