Write your own version of a Binary Tree class template that can hold values of any data type. Name this file BinaryTree.h. (more details about this class in the BINARYTREE.H section of this document) Then, create a class for a Pokemon called Pokemon which should contain attributes for the Pokemons index and the Pokemons name. Name this file Pokemon.h. (more details about this class in the POKEMON.H section of this document) Next, write the driver program (Program3.cpp) that will do the following: Create a Binary Tree object that can contain Pokemon objects in each tree node. Read all the Pokemon data from the given text file named pokedex.txt and for each index & name read in, create a Pokemon object. If this object is not yet in the Binary Search Tree, then insert it in the tree. Print out if the Pokemon read in was inserted in the tree or not. Keep track of how many Pokemon are inserted in the tree and print this number out. Display all the Pokemon from the Binary Search Tree in order by the index. Refer to the sample output at the end of this document to see the format of how things should be printed out.

WHAT YOU WILL TURN IN Zip the following files in a single zip file and upload the zip file to the submission folder in ilearn. BinaryTree.h Pokemon.h Program3.cpp pokedex.txt

BINARYTREE.H This should be a template class which contains the following private & public members:

PRIVATE ATTRIBUTES & FUNCTIONS TreeNode struct containing a value of the template type, a pointer to the left TreeNode and a pointer to the right TreeNode A pointer to the root TreeNode Private functions: o Insert recursive function that will insert a new node into the binary search tree o destroySubTree recursive function that will delete all nodes in the binary search tree o displayInOrder recursive function that will print out each node in order

PUBLIC FUNCTIONS Constructor Destructor (which should call destroySubTree) insertNode - should accept a template type as a parameter and create a new node with this parameter as its value and then call the insert function displayInOrder (should call the displayInOrder private function, sending the root) searchNode should accept a template type as a parameter and return true if the node value is found and false otherwise POKEMON.H Pokemon class should hold the following (private) information: Pokemon Index Number: an integer Pokemon Name: a string This class should also implement the following public functions: Constructor (setting the index & name) use default arguments for the parameters; setting index to zero and name to None setID setName getID getName overloaded < operator (needed to be able to insert in binary search tree & search) overloaded == operator (needed to be able to search) overloaded << operator (needed to print out the Pokemon)

SAMPLE OUTPUT Inserting Pokemon with index 83 into the Pokedex. Inserting Pokemon with index 185 into the Pokedex. Inserting Pokemon with index 177 into the Pokedex. Inserting Pokemon with index 8 into the Pokedex. Inserting Pokemon with index 178 into the Pokedex. Inserting Pokemon with index 1 into the Pokedex. Inserting Pokemon with index 5 into the Pokedex. Inserting Pokemon with index 6 into the Pokedex. Inserting Pokemon with index 11 into the Pokedex. Inserting Pokemon with index 12 into the Pokedex. Inserting Pokemon with index 14 into the Pokedex. Inserting Pokemon with index 2 into the Pokedex. Inserting Pokemon with index 3 into the Pokedex. Inserting Pokemon with index 4 into the Pokedex. Inserting Pokemon with index 9 into the Pokedex. Inserting Pokemon with index 13 into the Pokedex. Inserting Pokemon with index 28 into the Pokedex. Inserting Pokemon with index 27 into the Pokedex. Inserting Pokemon with index 26 into the Pokedex. Inserting Pokemon with index 19 into the Pokedex. Inserting Pokemon with index 17 into the Pokedex. Inserting Pokemon with index 16 into the Pokedex. Oops! The Pokemon with index 27 is already in the Pokedex. Inserting Pokemon with index 132 into the Pokedex. Inserting Pokemon with index 21 into the Pokedex. Inserting Pokemon with index 30 into the Pokedex. Inserting Pokemon with index 24 into the Pokedex. Inserting Pokemon with index 23 into the Pokedex. Inserting Pokemon with index 34 into the Pokedex. Inserting Pokemon with index 35 into the Pokedex. Inserting Pokemon with index 39 into the Pokedex. Inserting Pokemon with index 37 into the Pokedex. Inserting Pokemon with index 36 into the Pokedex. Inserting Pokemon with index 42 into the Pokedex. Inserting Pokemon with index 44 into the Pokedex. Inserting Pokemon with index 45 into the Pokedex. Inserting Pokemon with index 49 into the Pokedex. Inserting Pokemon with index 53 into the Pokedex. Inserting Pokemon with index 119 into the Pokedex. Inserting Pokemon with index 188 into the Pokedex. Inserting Pokemon with index 104 into the Pokedex. Inserting Pokemon with index 100 into the Pokedex. Inserting Pokemon with index 96 into the Pokedex. Inserting Pokemon with index 84 into the Pokedex. Oops! The Pokemon with index 185 is already in the Pokedex.

43 Pokemon have been added to the Pokedex!

********************POKEDEX:********************

Pokemon Index Number: 1 Name: Rhydon Pokemon Index Number: 2 Name: Kangaskhan Pokemon Index Number: 3 Name: Nidoran Pokemon Index Number: 4 Name: Clefairy Pokemon Index Number: 5 Name: Spearow Pokemon Index Number: 6 Name: Voltorb Pokemon Index Number: 8 Name: Slowbro Pokemon Index Number: 9 Name: Ivysaur1 Pokemon Index Number: 11 Name: Lickitung Pokemon Index Number: 12 Name: Exeggcute Pokemon Index Number: 13 Name: Grimer Pokemon Index Number: 14 Name: Gengar Pokemon Index Number: 16 Name: Nidoqueen Pokemon Index Number: 17 Name: Cubone Pokemon Index Number: 19 Name: Lapras Pokemon Index Number: 21 Name: Mew Pokemon Index Number: 23 Name: Shellder Pokemon Index Number: 24 Name: Tentacool Pokemon Index Number: 26 Name: Scyther Pokemon Index Number: 27 Name: Staryu Pokemon Index Number: 28 Name: Blastoise Pokemon Index Number: 30 Name: Tangela Pokemon Index Number: 34 Name: Onix Pokemon Index Number: 35 Name: Fearow Pokemon Index Number: 36 Name: Pidgey Pokemon Index Number: 37 Name: Slowpoke Pokemon Index Number: 39 Name: Graveler Pokemon Index Number: 42 Name: Mr. Mime Pokemon Index Number: 44 Name: Hitmonchan Pokemon Index Number: 45 Name: Arbok Pokemon Index Number: 49 Name: Golem Pokemon Index Number: 53 Name: Electabuzz Pokemon Index Number: 83 Name: Ninetails Pokemon Index Number: 84 Name: Pikachu Pokemon Index Number: 96 Name: Sandshrew Pokemon Index Number: 100 Name: Jigglypuff Pokemon Index Number: 104 Name: Jolteon Pokemon Index Number: 119 Name: Venemoth Pokemon Index Number: 132 Name: Snorlax Pokemon Index Number: 177 Name: Squirtle Pokemon Index Number: 178 Name: Charmeleon Pokemon Index Number: 185 Name: Oddish Pokemon Index Number: 188 Name: Bellsprout

********************pokedex.txt******************** 83#Ninetails#185#Oddish#177#Squirtle#8#Slowbro#178#Charmeleon#1#Rhydon#5#Spearow#6#Voltorb#11#Lickitung#12#Exeggcute#14#Gengar#2#Kangaskhan#3#Nidoran#4#Clefairy#9#Ivysaur1#13#Grimer#28#Blastoise#27#Staryu#26#Scyther#19#Lapras#17#Cubone#16#Nidoqueen#27#Staryu#132#Snorlax#21#Mew#30#Tangela#24#Tentacool#23#Shellder#34#Onix#35#Fearow#39#Graveler#37#Slowpoke#36#Pidgey#42#Mr. Mime#44#Hitmonchan#45#Arbok#49#Golem#53#Electabuzz#119#Venemoth#188#Bellsprout#104#Jolteon#100#Jigglypuff#96#Sandshrew#84#Pikachu#185#Oddish#