Then, this tree can be specified in a file as follows. Note that the first node $($the root$)$ is

numbered $0,$ and no other nodes point to it$.$A $$decision tree$$ is a model that is frequently used to

support decision$-$making. The model has a $$tree$$

structure, with $$question nodes$$ that branch to other

nodes depending on the answer. Eventually, one arrives

at a decision. A very simple tree is shown in slide $37$ in

the presentation on pointers, reproduced here for

convenience:

An example application of a decision tree would be a set of questions to determine if it is

safe for a technician to enter a potentially hazardous room. A robot might use a decision

tree to decide whether a product component is defective.

Decision trees are also used to classify objects based on their $$features$.$ For example, $$if it

has wings and two feet, it$$s a bird; if it has wings and six feet, it$$s an insect$.$ A common

machine learning technique is to develop algorithms that automatically build classifier

trees based on training data. For more information on this technique, see here.

In this project, you will develop a program that reads the specification of a decision tree

from a file, and then walks the user through the tree until a decision is reached. The tree

will be implemented using structs and pointers. The kind of tree you will work with is

called a $$binary tree$$: each question can have only two possible answers: $$yes$$ or $$no$.$

Specification of a Decision Tree

Assume that a struct Node is defined as in Lab $12\mathrm{.}25.$ Then, the tree can be defined as a

vector of pointers to nodes $($that is$,$ the vector elements have type Node $*).$

How to describe a tree in textual form? One possible way is to use three lines to specify one

node. The first line consists of the node$$s textual description; the second and third lines

$($integers$)$ specify the node to jump to if the answer is $$yes$$ or $$no$,$ respectively. If both

lines are $0,$ then this is a leaf node $($a decision$).$

Assume the nodes are labeled as in the figure below:

Then, this tree can be specified in a file as follows. Note that the first node $($the root$)$ is

numbered $0,$ and no other nodes point to it$.$

Are you Hungry?

$1$

$2$

Is it early?

$3$

$4$

You should study.

$0$

$0$

You should eat breakfast.

$0$

$0$

Is it midday?

$5$

$6$

You should eat a sandwich.

$0$

$0$

You should eat pasta.

$0$

$0$

Program Requirements

Your program$$s functionality must meet the following requirements.

$1.$ It must ask the user for a filename.

$2.$ It must open and read a file with the provided name, with $.$txt$$ appended to it$.$ For

example, if the user provides the file name $$tree$,$ the program must open and read

the file $$tree$.$txt$.$

$3.$ The file must contain a textual description of a binary decision tree as in the

example above.

$4.$ This file must specify a tree of your own design. It is suggested to design a tree on a

topic you like, or a hobby, or something you are interested in and are knowledgeable

about.

$5.$ The tree must have at least five question nodes; there is no upper limit$.$

$6.$ After reading the file, the program must walk the user through the tree until a

decision is reached.

$7.$ The program must use at least one function, which should read the provided file and

return a tree. This function must be present in a separate file. The prototype of this

function should be:

vector readtree$($ifstream &$)$;

The function argument is an input file stream; the function assumes that the file was

already opened successfully, so it can start reading from the stream directly. Here,

Node is a struct defined as in the slides on pointers and in Lab #$12.$

$8.$ A header file must be provided.

Aside from these requirements, you get to decide how your program presents the questions

and the decision, and what to do after that.

Note that you may assume that the file contains no errors $($there is no need to handle

invalid text files$).$

Other Program Requirements:

$$ Only the following C$++$ keywords are accepted in this project:

o All type declarations $($int$,$ float, etc.$)$

o All arithmetic operations $(+,/,\%,$ etc.$)$

o cin, cout and the output configuration from iomanip $($setw$,$ etc.$)$

o Branching with if$/$else and switch.

o The loops covered in class.

o Strings as covered in class, including the functions atoi and stoi to convert

characters and strings to integers.

o Vectors as covered in class.

o Functions as covered in class.

o I$/$O streams as covered in class.

o Structs and pointers as covered in class.

If you need a particular keyword not in this list, ask your instructor first.