binary tree class

[jhdobbins]

what all do i have to do to make this work... this is my class and functions... and the errors are at the bottom...

do i have to overload operators or is there a much easier way? thanks.

and i know the return function isnt written yet.

#include <iostream>
#include <cstdlib>

using namespace std;

class binaryTree {

	public:

		binaryTree ();
		int menu ();

	private:

		typedef struct dataNode {
			char arriveCity[30];
			char departCity[30];
			int totalPassengers;
			int passengers;
			int flightNumber;
			struct dataNode * left;
			struct dataNode * right;
		};
	
		dataNode * root;

		bool insert (dataNode *&, dataNode &);
		bool search (dataNode *, dataNode &);
		bool retrieve (dataNode *, dataNode &);
		void inorder (dataNode *);

};

binaryTree::binaryTree() {

	dataNode * root = NULL;
	dataNode * left = NULL;
	dataNode * right = NULL;

}

bool binaryTree::insert(dataNode*& tree, dataNode &flightNumber) {

	if (tree == NULL) {

		tree = new dataNode;
		tree -> left = NULL;
		tree -> right = NULL;
		tree -> flightNumber = flightNumber;
		return true;
	
	}
	else if (flightNumber == tree -> flightNumber)
		return false;
	else if (flightNumber <= tree -> flightNumber)
		return insert (tree -> left, flightNumber);
	else 
		return insert (tree -> right, flightNumber);
}

bool binaryTree::search(dataNode * tree, dataNode &flightNumber) {

	if (tree == NULL)
		return false;
	else if (flightNumber == tree -> flightNumber)
		return true;
	else if (flightNumber <= tree -> flightNumber)
		return search (tree -> left, flightNumber);
	else 
		return search (tree -> right, flightNumber);
}

bool binaryTree::retrieve (dataNode * tree, dataNode &flightNumber) {

}

void binaryTree::inorder (dataNode * tree) {

	if (tree != NULL) {

		inorder (tree -> left);
		cout << tree->flightNumber << endl;
		inorder (tree -> right);

	}
}

int binaryTree::menu () {

int choice;

cout << endl;
cout << "Welcome to the JHD International Airport! How can we be of assistance?" << endl;
cout << "Please select the best option for you:" << endl;
cout << "  1. Create a new flight record." << endl; 
cout << "  2. Search for a flight." << endl;
cout << "  3. End current program session." << endl;
cin >> choice;
cout << endl;

if (choice == 2) {

	cout << "Please select the search option of your choice:" << endl;
	cout << "  1. Display all flight records." << endl;
	cout << "  2. Display all departing flights from a city." << endl;
	cout << "  3. Display all open flights." << endl;
	cout << "  4. Go back to the main menu." << endl;
	cin >> choice;
	cout << endl;

}

return choice;

}

C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp: In member
function `bool binaryTree::insert(binaryTree::dataNode*&,
binaryTree::dataNode&)':
C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp:49: error: cannot
convert `binaryTree::dataNode' to `int' in assignment
C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp:53: error: no
match for 'operator==' in 'flightNumber ==
tree->binaryTree::dataNode::flightNumber'
C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp:55: error: no
match for 'operator<=' in 'flightNumber <=
tree->binaryTree::dataNode::flightNumber'

C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp: In member
function `bool binaryTree::search(binaryTree::dataNode*,
binaryTree::dataNode&)':
C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp:65: error: no
match for 'operator==' in 'flightNumber ==
tree->binaryTree::dataNode::flightNumber'

C:/Documents and Settings/Josh/Desktop/JHD-cs111project6.cpp:67: error: no
match for 'operator<=' in 'flightNumber <=
tree->binaryTree::dataNode::flightNumber'

[jhdobbins]

nevermind... got it.

[jhdobbins]

alright my insert function is:

bool binaryTree::insert(dataNode*& tree, int &flightNumber) {

	if (tree == NULL) {

		tree = new dataNode;
		tree -> left = NULL;
		tree -> right = NULL;
		tree -> flightNumber = flightNumber;
		return true;
	
	}
	else if (flightNumber == tree -> flightNumber)
		return false;
	else if (flightNumber <= tree -> flightNumber)
		return insert (tree -> left, flightNumber);
	else 
		return insert (tree -> right, flightNumber);
}

and im guessing i need to put the information thats typed in... here in the insert function too..

but im not sure how to do that... because i have always done just *current with the linked lists and im confused about doing it with the left and right...

here is the info fields...:

typedef struct dataNode {
			char arriveCity[30];
			char departCity[30];
			int totalPassengers;
			int passengers;
			int flightNumber;
			struct dataNode * left;
			struct dataNode * right;
		};
	
		dataNode * root;

im sure i need to do a comparision like...

if (flightNumber < root -> flightNumber) 
       flightNumber = left -> flightNumber;
else if (flightNumber > root -> flightNumber)
       flightNumber = right -> flightNumber;

however i dont think that will cover everything and i dont know if it would balance the tree.... plus im not exactly sure where to put that into the insertion function...

and i just compare the flightnumbers but all the data in the struct needs to be... attatched to that one flight number.... i have to have it search for a flight then cout all the information that is linked with that flightnumber... or city or whatever the search field is...

am i on the right track? and where do i go from here?

[Narue]

>but im not sure how to do that
It would be easier to build the data part of a node in your client code and pass it to the binary tree class. That would involve something like this:

struct data {
  char arriveCity[30];
  char departCity[30];
  int totalPassengers;
  int passengers;
  int flightNumber;
};

struct node {
  data item;
  node *left, *right;
};

Then the input function could be easily modified:

bool binaryTree::insert(dataNode*& tree, data item) {
  if (tree == NULL) {
    tree = new node;
    tree -> left = NULL;
    tree -> right = NULL;
    tree -> item = item;
    return true;
  }
  else if (item -> flightNumber == tree -> item -> flightNumber)
    return false;
  else if (item -> flightNumber <= tree -> item -> flightNumber)
    return insert (tree -> left, item);
  else 
    return insert (tree -> right, item);
}

>i dont know if it would balance the tree
No, it won't. Balancing is much more complicated than that. I have several binary search tree tutorials on my website if you want to take a look at them.

[jhdobbins]

Thanks narue.. I already did some other things by the time i saw this post. But I have more problems with it. And my code looks alot different tahn before. I changed the majority of everything to get it to work.

and it does compile!!!!

#include <iostream>
#include <cstdlib>

using namespace std;

class binaryTree {

	public:

		binaryTree ();
		~binaryTree ();
		void menu ();

	private:

		typedef struct dataNode {
			char arriveCity[30];
			char departCity[30];
			int totalPassengers;
			int passengers;
			int flightNumber;
			struct dataNode * left;
			struct dataNode * right;
		};
	
		dataNode * root;
		void insert (dataNode *, dataNode &);
		void retrieveAll (dataNode *);
		void retrieveOpen (dataNode *);
		void retrieveCity (dataNode *);

};

binaryTree::binaryTree() {

	dataNode * root = NULL;
	dataNode * left = NULL;
	dataNode * right = NULL;

}

binaryTree::~binaryTree() {
                          
   delete root;
   
}

void binaryTree::insert(dataNode* tree, dataNode &newNode) {

	if (tree == NULL) {
 
        tree = new dataNode;
        tree -> left = NULL;
		tree -> right = NULL;
		
        cout << "Please input the six digit flight number (100000 - 999999): ";
        cin >> tree -> flightNumber;

        if (tree -> flightNumber < 100000 || tree -> flightNumber > 999999) {
            cout << "Invalid flight number reference" << endl << endl;
            void insert(dataNode*& tree, dataNode &newNode);
        }

        cout << endl << "What is the departure city? ";
        cin >> tree -> departCity[30];
        cout << endl << "What city is the flight destination? ";
        cin >> tree -> arriveCity[30];
        cout << endl << "What is the maximum capacity for this flight? ";
        cin >> tree -> totalPassengers;
        cout << endl << "How many passengers currently have tickets? ";
        cin >> tree -> passengers;
        cout << endl;   

		tree -> flightNumber = newNode.flightNumber;
		tree -> totalPassengers = newNode.totalPassengers;
        tree -> passengers = newNode.passengers;
        strcpy(tree -> arriveCity, newNode.arriveCity);
        strcpy(tree -> departCity, newNode.departCity);
        
	}
}

void binaryTree::retrieveAll (dataNode * tree) {

     while (root != NULL){  
           retrieveAll (tree -> left);
           cout << tree -> flightNumber << " " ;
           cout << tree -> departCity[30] << " ";
           cout << tree -> arriveCity[30] << " "; 
           cout << tree -> passengers << " ";
           cout << tree -> totalPassengers << " " << endl;
           retrieveAll (tree -> right);
      }
}

void binaryTree::retrieveOpen(dataNode * tree) {    
      
      while (root != NULL) {
            if (tree -> passengers < tree -> totalPassengers) {
                         retrieveOpen (tree -> left);
                         cout << tree -> flightNumber << " " ;
                         cout << tree -> departCity[30] << " ";
                         cout << tree -> arriveCity[30] << " "; 
                         cout << tree -> passengers << " ";
                         cout << tree -> totalPassengers << " " << endl; 
                         retrieveOpen (tree -> right);
            }
       }
}

void binaryTree::retrieveCity(dataNode * tree) {
     
     char city[30];
     cout << "What city would you like to see departing flights from? ";
     cin >> city;
     
     
     while (root!= NULL) {
           if (tree -> departCity == city) {
                        retrieveCity (tree -> left);
                        cout << tree -> flightNumber << " " ;
                        cout << tree -> departCity[30] << " ";
                        cout << tree -> arriveCity[30] << " "; 
                        cout << tree -> passengers << " ";
                        cout << tree -> totalPassengers << " " << endl;
                        retrieveCity (tree -> right);
           }
     }
}         
                                  
void binaryTree::menu () {
    

    int choice = 0, searchChoice = 0;

    while (choice != 3) {
    
        cout << endl;
        cout << "Welcome to the JHD International Airport! How can we be of assistance?" << endl;
        cout << "Please select the best option for you:" << endl;
        cout << "  1. Create a new flight record." << endl; 
        cout << "  2. Search for a flight." << endl;
        cout << "  3. End current program session." << endl;
        cin >> choice;
        cout << endl;
        
        if (choice == 1) 
           void insert(dataNode * tree, dataNode &newNode);
        
        else if (choice == 2) {
    
    	   cout << "Please select the search option of your choice:" << endl;
    	   cout << "  1. Display all flight records." << endl;
    	   cout << "  2. Display all departing flights from a city." << endl;
    	   cout << "  3. Display all open flights." << endl;
    	   cout << "  4. Go back to the main menu." << endl;
    	   cin >> searchChoice;
    	   cout << endl;
    
           if (searchChoice == 1)
                void retrieveAll(dataNode & newNode);
           else if (searchChoice == 2)
                void retrieveCity(dataNode & newNode);
           else if (searchChoice == 3)
                void retrieveOpen(dataNode & newNode);
           else if (searchChoice == 4)
                void menu ();
           else {
                cout << endl << "That is invalid an option" << endl;
                void menu ();
           } 
        }
        
        else if (choice == 3)
             break;
             
        else {
        
             cout << "That is an invalid option" << endl;
             void menu();
        }
    }
}

int main () {

binaryTree binTree;
binTree.menu();

return 0;

}

tried to minimize the main function.

Anyways, it goes to the menu and lets you select an option... if type in an invalid choice that works.. and if you pick the option to quit that works, all the others seen to just keep looping around.

am i calling my functions wrong or are my functions just wrong period? i think my insert is lacking?

and as a quick side topic... we never had to write destructors before so i know itll be more than delete root... what else is needed there?

[Dave Sinkula]

For my benefit, could you fix this part:

typedef struct dataNode {
			char arriveCity[30];
			char departCity[30];
			int totalPassengers;
			int passengers;
			int flightNumber;
			struct dataNode * left;
			struct dataNode * right;
		};

The name of the typedef is between the } and the ; - that empty part. I've tried to look at some things a number of times, but these little fixits here and there begin to discourage me.

Because, you see, for me it does not compile.

Error E2092 testpp.cpp 24: Storage class 'typedef' is not allowed here

[jhdobbins]

i dont understand? just delete the word typedef?

[jhdobbins]

sorry dave, i still dont know what you were asking me to remove. so for everyone else out there... my program is seg faulting. and a debugger isnt helping so i am wondering you anyone can pick up on the problem that i am overlooking...

it allows you to input information but if you want to search - display information off menu option 2 then any of the search options - the program seg faults... i changed my while loop from (root != Null) to (tree != Null) and that didnt fix it... any other ideas? thank you.

#include <iostream>
#include <cstdlib>

using namespace std;

class binaryTree {

	public:

		binaryTree ();
		~binaryTree ();
		void menu ();

	private:

		typedef struct dataNode {
			char arriveCity[30];
			char departCity[30];
			int totalPassengers;
			int passengers;
			int flightNumber;
			struct dataNode * left;
			struct dataNode * right;
		};
	
		dataNode * root;
		void info (dataNode & newNode);
        void insert (dataNode *, dataNode &);
		void retrieveAll (dataNode *);
		void retrieveOpen (dataNode *);
		void retrieveCity (dataNode *);

};

binaryTree::binaryTree() {

	dataNode * root = NULL;
	dataNode * left = NULL;
	dataNode * right = NULL;

}

binaryTree::~binaryTree() {
                          
   delete root;
   
}

void binaryTree::info(dataNode & newNode) {
     
        cout << "Please input the six digit flight number (100000 - 999999): ";
        cin >> newNode.flightNumber;

        if (newNode.flightNumber < 100000 || newNode.flightNumber > 999999)
            cout << "Invalid flight number reference" << endl << endl;
        
        cin.ignore();    
        cout << endl << "What is the departure city? ";
        cin.getline(newNode.departCity, 30);
        cout << endl << "What city is the flight destination? ";
        cin.getline(newNode.arriveCity, 30); 
        cout << endl << "What is the maximum capacity for this flight? ";
        cin >> newNode.totalPassengers;
        cout << endl << "How many passengers currently have tickets? ";
        cin >> newNode.passengers;
        cout << endl; 
}

void binaryTree::insert(dataNode* tree, dataNode &newNode) {
    
	if (tree == NULL) {
 
        tree = new dataNode;
        tree -> left = NULL;
		tree -> right = NULL;
		tree -> flightNumber = newNode.flightNumber;
		tree -> totalPassengers = newNode.totalPassengers;
        tree -> passengers = newNode.passengers;
        strcpy(tree -> arriveCity, newNode.arriveCity);
        strcpy(tree -> departCity, newNode.departCity);
        
	}
}

void binaryTree::retrieveAll (dataNode * tree) {

     while (root != NULL){  
           retrieveAll (tree -> left);
           cout << tree -> flightNumber << " " ;
           cout << tree -> departCity[30] << " ";
           cout << tree -> arriveCity[30] << " "; 
           cout << tree -> passengers << " ";
           cout << tree -> totalPassengers << " " << endl;
           retrieveAll (tree -> right);
      }
}

void binaryTree::retrieveOpen(dataNode * tree) {    
      
      while (root != NULL) {
            if (tree -> passengers < tree -> totalPassengers) {
                         retrieveOpen (tree -> left);
                         cout << tree -> flightNumber << " " ;
                         cout << tree -> departCity[30] << " ";
                         cout << tree -> arriveCity[30] << " "; 
                         cout << tree -> passengers << " ";
                         cout << tree -> totalPassengers << " " << endl; 
                         retrieveOpen (tree -> right);
            }
       }
}

void binaryTree::retrieveCity(dataNode * tree) {
     
     char city[30];
     cout << "What city would you like to see departing flights from? ";
     cin.getline(city, 30);
     
     while (root!= NULL) {
           if (tree -> departCity == city) {
                        retrieveCity (tree -> left);
                        cout << tree -> flightNumber << " " ;
                        cout << tree -> departCity[30] << " ";
                        cout << tree -> arriveCity[30] << " "; 
                        cout << tree -> passengers << " ";
                        cout << tree -> totalPassengers << " " << endl;
                        retrieveCity (tree -> right);
           }
     }
}         
                                  
void binaryTree::menu () {
    
    int choice = 0, searchChoice = 0;
    
    while (choice != 3) {   
          
        cout << endl;
        cout << "Welcome to the JHD International Airport! How can we be of assistance?" << endl;
        cout << "Please select the best option for you:" << endl;
        cout << "  1. Create a new flight record." << endl; 
        cout << "  2. Search for a flight." << endl;
        cout << "  3. End current program session." << endl;
        cin >> choice;
        cout << endl;
        
        if (choice == 1) {
           dataNode newNode;
           info(newNode);
           insert(root, newNode);
        }
        else if (choice == 2) {
    
    	   cout << "Please select the search option of your choice:" << endl;
    	   cout << "  1. Display all flight records." << endl;
    	   cout << "  2. Display all departing flights from a city." << endl;
    	   cout << "  3. Display all open flights." << endl;
    	   cout << "  4. Go back to the main menu." << endl;
    	   cin >> searchChoice;
    	   cout << endl;
    
           if (searchChoice == 1) {
                dataNode *tree;
                retrieveAll(tree);
           }
           else if (searchChoice == 2) {
                dataNode *tree;
                retrieveCity(tree);
           }
           else if (searchChoice == 3) {
                dataNode *tree;
                retrieveOpen(tree);
           }
        }
        
        else if (choice == 3)
             break;
             
        else {
        
             cout << "That is an invalid option" << endl;
             void menu();
        }
    }
}

int main () {

        binaryTree binTree;
        binTree.menu();

return 0;
}