Inserting a node on a Tree

[JimD C++ Newb]

Hello all!!!

First off, I'd like to say THANK YOU for such a great site. I've learned a lot here in the last 2 months!

I'm currently in a Data Structures class and our current assignment is:

Read data from a .dat file (name, address, phone #) and store the info in a BST using the phone number as the unique key for each node.

I have been successful in opening the file, retrieving the information, and parsing it out. What I am not successful in is actually putting the info ON the tree.

Could somebody take a look and point me in the right direction? Thank you!

Jim

//Project: Populating a BST with a .DAT file and traversing the tree

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include "binarySearchTree.h"

using namespace std;

struct Data
{
  string name;
  string address;
};

template <class Data>
void insert (int key, Data data);

int main()
{
int key;
const int MAXCHARS = 81;
Data data;
BST <int, Data> tree;

ifstream dfile;
dfile.open ("phone.dat");

while (dfile.good())
 {
  string phone, name, address;
  std::getline(dfile, phone, ':');
  std::getline(dfile, name, ':');
  std::getline(dfile, address, '\n');
 
  key = atoi(phone.c_str());  

//  cout << "The phone # is: " << phone << endl;
//  cout << "The name is: " << name << endl;
//  cout << "The address is: " << address << endl;

  tree.insert (key, data);

  cout << "The phone # for " << address << "is: " << phone << endl;
  cout << "\nThe unique key is: " << key << endl;
 }

dfile.close();

return 0;
}

I hope I used the code tags correctly!

Thank you again,

Jim

P.S. - I did not include the binarySearchTree.h file, but if you need to know part of it I can include it.

[Narue]

Well, you didn't show any of your tree, so the best I can do is link you to a tutorial I feel is good: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_bst1.aspx

[JimD C++ Newb]

Narue,

Thank you! I will go read that thread - looks long but informative! Thank you.

If by the code for the tree you meant part of the .h file that is included in the top, here is the insertion portion of it (It was provided to us by our professor...I cerainly can't take credit for writing it myself) :)

template <class KeyType, class DataType> 
bool  BST<KeyType, DataType>::insert (KeyType key, DataType data)
{
    TreeNode<KeyType, DataType>* newPtr = new TreeNode<KeyType, DataType>;
    
    if (!newPtr)
        return false;
    newPtr->key  = key;
    newPtr->data = data;
    newPtr->left = NULL;
    newPtr->right = NULL;
    return (_insert (key, newPtr, root));
}



//   recursive insert given a key, pointer to the node to insert, and a tree to look at
template <class KeyType, class DataType> 
bool  BST<KeyType, DataType>::_insert (KeyType key, TreeNode<KeyType, DataType>* newPtr, 
							TreeNode<KeyType, DataType>* & root)
{
    
    if (!root)
        {
        root = newPtr;
    	return true;
    	}
    if (key == root->key)
	{
	delete newPtr;   // updated 3/28/2006 must delete allocated memory
    	return false;   //  duplicate key
	}
    if (newPtr->key  <  root->key)
        return (_insert (key, newPtr, root->left));
     else
        return (_insert (key, newPtr, root->right));

}

Thank you again for the link!

Jim

[Narue]

>It was provided to us by our professor
Then presumably it should work and you don't need to worry about it.

>tree.insert (key, data);
Don't forget to assign the parsed values to the data object before storing it in the tree.

[JimD C++ Newb]

Yes, this is where I seem to get lost...

I parse the file into 3 different strings...

1 (phone number) can be changed to an int, and therefore can be used as the key.

but I can't seem to figure out how to handle the other 2 parts: a) parse it as a struct called Data or b) convert the string I parsed to a struct called Data.

Several sites I've looked at say it's impossible to do the conversion, so that leaves...

Can you point me to a place where I can learn to parse it as a struct and not as a string? Maybe I'm google-ing the wrong thing.

Much appreciated!

Jim

[chococrack]

Data superStruct;
superStruct.name = thatLastNameIRead;
superStruct.address = thatAddressIRead;
int mySuperKey = thatKeyIRead;

myBST.insert(thatKeyIRead, superStruct);

What is the question?

You don't need to do anything to the other two inputs, they're strings already, which is what the struct's values are.

Parsing refers to breaking something into parts, in general. Hope this helps.

[Narue]

>Can you point me to a place where I can learn to parse it as a struct and not as a string?
You're already breaking the string down into component parts that can be assigned to the struct instance:

string phone, name, address;

getline(dfile, phone, ':');
getline(dfile, name, ':');
getline(dfile, address, '\n');
 
key = atoi(phone.c_str());
data.name = name;
data.address = address;

tree.insert (key, data);

There's no magic to parsing. All you're doing is recognizing and extracting component parts (as strings!) that can be converted to the appropriate types and used within your application logic.

[JimD C++ Newb]

Oh, silly me!

Thank you!!

/smackhead

Sometimes the easiest problems are the hardest to see :)

Jim