Programming Forums > Application Development > C++

Seif · Jan 28th, 2006, 6:43 PM

hi all, am new to the forums, but by being a uni student no doubt I'll be here a lot more from now on, and I'll try to help others when i can (when i learn it for myself hehe).

anyways i am just learning c++, and i have my first assignment which requires an index such as a binary tree with the following struct:

(Toggle Plain Text)

struct indexNode  { char  regNumber[10];
					int     recordNumber;
					indexNode* leftSide, *rightSide;
					};

now I am required to save the index tree to a file when im finished and reload it when the program is started up again.

i save the tree using inorder traverse by doing the following:

(Toggle Plain Text)

void saveIndex(indexNode* aNode) 
	{
		if(aNode !=NULL)	
		{
			saveIndex(aNode->leftSide); 
			ofstream outputIndex;		
			outputIndex.open("index.txt", ios::out);	

			strcpy(newNode.regNumber,aNode->regNumber);
			newNode.recordNumber = aNode->recordNumber;

			outputIndex.write(reinterpret_cast<const char*> (&newNode), sizeof(indexNode));
			outputIndex.close();			
			saveIndex(aNode->rightSide);	
		}
		cout << " ####Index Saved ####" << endl;
	}

now the problem i am having is loading the tree. i would like to do the similar traversal but i cant quite get my head around which order and how i can load the file producing the exact same tree.

also, although the tree is sorted, i havent yet found a way of balancing the tree. As all methods such as AVL and red black seem to use class's of which i havent yet learned, i was wondering if there is any method i can do just by altering my indexNode struct, and creating a few functions.

thanks for your time.

DaWei · Jan 28th, 2006, 7:29 PM

Plenty of tree manipulations have been done without classes. Why don't you just inspect the methods of a few you find here and there? As far as reading the tree back in, why not just read in the values and reconstruct it with insertions? If you save it with an in-order traversal, it should even be simple to reconstruct it in balanced fashion.

Seif · Jan 29th, 2006, 7:13 AM

Hi thanks for the reply. Do you have any example methods you could show me? unfortunately, the only method i can find in my books seem quite daunting using classes and not having any luck at all searching for methods online. I am working on my own at the moment, but i think im goin about it all wrong. basically the following code performs when a node is added in a sorted order on the tree. I've added an extra field *Parent to my indexNode struct, and want it to recursively check backwards the subroot of each node until it reachs main root. however im not sure if im doing this correctly, and there seems to be something wrong with the code as it keeps crashing.

(Toggle Plain Text)

void insert(indexNode* currentNode)
	{
		while(currentNode->Parent != NULL)
		{
			while(currentNode != NULL)
			{
				lheight++;
				insert(currentNode->leftSide);
			}
	
			while(currentNode !=NULL)
			{
				rheight++;
				insert(currentNode->rightSide);
			}
	
			if(lheight - rheight > 1)
			{
				rotateright();
				cout << "There is an Imbalance" << endl;
			}

			if(lheight = rheight < -1)
			{
				rotateleft();
				cout << "there is an imbalance" << endl;
			}
			else
			{
				cout << "tree remains balanced" << endl;
			}
			lheight = 0;
			rheight = 0;
			insert(currentNode->Parent);
		}
	}

for the saving and loading the tree, i was just reconstructing the tree using a simple add node function, and saving the tree in post-order traversal, but thought it would be more efficient if i could load the tree just by using traveral.

DaWei · Jan 29th, 2006, 8:06 AM

I'll look at your code in detail a little later today, and maybe have some general comments. However, for the moment, I'll tell you that anytime you are using NULL pointers you are very prone to crashes, particularly if they are part of a chain. When you enter INSERT, for instance, you're checking the parent node and the current node for NULL, but what's happening in the rotate functions is unseen.

Keeping a parent node is something I've done for excising nodes in heaps, but even there one can do the work without, it's just a tad more difficult.

Seif · Jan 29th, 2006, 10:20 AM

hi yeah. i havent implemented the rotations part yet, as im not 100% sure if i have this part right yet. also im not sure how to get the code to recognize if the rotation needed is a single or double.

. I've deleted most of what im working on today partly in frustration, but want to get the foundations of my program sorted first. Getting the tree to load and save.

some reason my load tree is getting stuck in a permenant loop:

(Toggle Plain Text)

void loadIndex()
{

	ifstream index;

	index.open("index.txt", ios::in);
	index.read(reinterpret_cast<char*> (&addNode), sizeof(indexNode));
	
	while (!index.eof())
	{
		indexNode *newNode;
		newNode = new indexNode;

		newNode->leftSide=NULL;
		newNode->rightSide=NULL;
		strcpy(newNode->regNumber, newvehicle.regNumber);
		count++;
		newNode->recordNumber = count;
                addnode(newNode);

		index.read(reinterpret_cast<char*> (&addnode), sizeof(indexNode));
	}
	index.close();
}

i have no idea why this is happening as im sure it worked fine before. its meant to read data from file and turn it into a new node to be added to the tree, but the while(!index.eof()) doesnt seem to want to exit.

Seif · Jan 29th, 2006, 4:31 PM

lol ignore that, is sorted.... didnt notice i put addnode with lowercase n at end lol. think im gonna give it a rest today as i think I'm doing more harm than good.

for the NULL pointers, what would you suggest? should i set them all to point to data item or a blank node?.

i've been looking at various methods of balancing, and thought i may give the Andersson method a try.

DaWei · Jan 29th, 2006, 7:24 PM

No, they need to be NULL to indicate they're unusable. Just check them before you dereference them. It's easy to pull a pointer, see that it's not NULL (in other words, valid) and then dereference one of its child pointers, forgetting to check the child. Example:

(Toggle Plain Text)

if (myPtr != NULL) data = myPtr->leftChild->data;

If leftChild is NULL, your code is off in the weeds puking in its cuff.

Jan 28th, 2006, 6:43 PM	#1
Seif Hobbyist Programmer Join Date: Jan 2006 Location: UK Posts: 215 Rep Power: 3	saving and loading a binary search tree hi all, am new to the forums, but by being a uni student no doubt I'll be here a lot more from now on, and I'll try to help others when i can (when i learn it for myself hehe). anyways i am just learning c++, and i have my first assignment which requires an index such as a binary tree with the following struct: (Toggle Plain Text) struct indexNode { char regNumber[10]; int recordNumber; indexNode* leftSide, rightSide; }; struct indexNode { char regNumber[10]; int recordNumber; indexNode leftSide, rightSide; }; now I am required to save the index tree to a file when im finished and reload it when the program is started up again. i save the tree using inorder traverse by doing the following: (Toggle Plain Text) void saveIndex(indexNode aNode) { if(aNode !=NULL) { saveIndex(aNode->leftSide); ofstream outputIndex; outputIndex.open("index.txt", ios::out); strcpy(newNode.regNumber,aNode->regNumber); newNode.recordNumber = aNode->recordNumber; outputIndex.write(reinterpret_cast<const char> (&newNode), sizeof(indexNode)); outputIndex.close(); saveIndex(aNode->rightSide); } cout << " ####Index Saved ####" << endl; } void saveIndex(indexNode aNode) { if(aNode !=NULL) { saveIndex(aNode->leftSide); ofstream outputIndex; outputIndex.open("index.txt", ios::out); strcpy(newNode.regNumber,aNode->regNumber); newNode.recordNumber = aNode->recordNumber; outputIndex.write(reinterpret_cast<const char*> (&newNode), sizeof(indexNode)); outputIndex.close(); saveIndex(aNode->rightSide); } cout << " ####Index Saved ####" << endl; } now the problem i am having is loading the tree. i would like to do the similar traversal but i cant quite get my head around which order and how i can load the file producing the exact same tree. also, although the tree is sorted, i havent yet found a way of balancing the tree. As all methods such as AVL and red black seem to use class's of which i havent yet learned, i was wondering if there is any method i can do just by altering my indexNode struct, and creating a few functions. thanks for your time.

Jan 28th, 2006, 7:29 PM	#2
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Plenty of tree manipulations have been done without classes. Why don't you just inspect the methods of a few you find here and there? As far as reading the tree back in, why not just read in the values and reconstruct it with insertions? If you save it with an in-order traversal, it should even be simple to reconstruct it in balanced fashion. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Jan 29th, 2006, 7:13 AM	#3
Seif Hobbyist Programmer Join Date: Jan 2006 Location: UK Posts: 215 Rep Power: 3	Hi thanks for the reply. Do you have any example methods you could show me? unfortunately, the only method i can find in my books seem quite daunting using classes and not having any luck at all searching for methods online. I am working on my own at the moment, but i think im goin about it all wrong. basically the following code performs when a node is added in a sorted order on the tree. I've added an extra field Parent to my indexNode struct, and want it to recursively check backwards the subroot of each node until it reachs main root. however im not sure if im doing this correctly, and there seems to be something wrong with the code as it keeps crashing. (Toggle Plain Text) void insert(indexNode currentNode) { while(currentNode->Parent != NULL) { while(currentNode != NULL) { lheight++; insert(currentNode->leftSide); } while(currentNode !=NULL) { rheight++; insert(currentNode->rightSide); } if(lheight - rheight > 1) { rotateright(); cout << "There is an Imbalance" << endl; } if(lheight = rheight < -1) { rotateleft(); cout << "there is an imbalance" << endl; } else { cout << "tree remains balanced" << endl; } lheight = 0; rheight = 0; insert(currentNode->Parent); } } void insert(indexNode* currentNode) { while(currentNode->Parent != NULL) { while(currentNode != NULL) { lheight++; insert(currentNode->leftSide); } while(currentNode !=NULL) { rheight++; insert(currentNode->rightSide); } if(lheight - rheight > 1) { rotateright(); cout << "There is an Imbalance" << endl; } if(lheight = rheight < -1) { rotateleft(); cout << "there is an imbalance" << endl; } else { cout << "tree remains balanced" << endl; } lheight = 0; rheight = 0; insert(currentNode->Parent); } } for the saving and loading the tree, i was just reconstructing the tree using a simple add node function, and saving the tree in post-order traversal, but thought it would be more efficient if i could load the tree just by using traveral.

Jan 29th, 2006, 8:06 AM	#4
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	I'll look at your code in detail a little later today, and maybe have some general comments. However, for the moment, I'll tell you that anytime you are using NULL pointers you are very prone to crashes, particularly if they are part of a chain. When you enter INSERT, for instance, you're checking the parent node and the current node for NULL, but what's happening in the rotate functions is unseen. Keeping a parent node is something I've done for excising nodes in heaps, but even there one can do the work without, it's just a tad more difficult. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Jan 29th, 2006, 10:20 AM	#5
Seif Hobbyist Programmer Join Date: Jan 2006 Location: UK Posts: 215 Rep Power: 3	hi yeah. i havent implemented the rotations part yet, as im not 100% sure if i have this part right yet. also im not sure how to get the code to recognize if the rotation needed is a single or double. . I've deleted most of what im working on today partly in frustration, but want to get the foundations of my program sorted first. Getting the tree to load and save. some reason my load tree is getting stuck in a permenant loop: (Toggle Plain Text) void loadIndex() { ifstream index; index.open("index.txt", ios::in); index.read(reinterpret_cast<char> (&addNode), sizeof(indexNode)); while (!index.eof()) { indexNode newNode; newNode = new indexNode; newNode->leftSide=NULL; newNode->rightSide=NULL; strcpy(newNode->regNumber, newvehicle.regNumber); count++; newNode->recordNumber = count; addnode(newNode); index.read(reinterpret_cast<char> (&addnode), sizeof(indexNode)); } index.close(); } void loadIndex() { ifstream index; index.open("index.txt", ios::in); index.read(reinterpret_cast<char> (&addNode), sizeof(indexNode)); while (!index.eof()) { indexNode newNode; newNode = new indexNode; newNode->leftSide=NULL; newNode->rightSide=NULL; strcpy(newNode->regNumber, newvehicle.regNumber); count++; newNode->recordNumber = count; addnode(newNode); index.read(reinterpret_cast<char> (&addnode), sizeof(indexNode)); } index.close(); } i have no idea why this is happening as im sure it worked fine before. its meant to read data from file and turn it into a new node to be added to the tree, but the while(!index.eof()) doesnt seem to want to exit.

Jan 29th, 2006, 4:31 PM	#6
Seif Hobbyist Programmer Join Date: Jan 2006 Location: UK Posts: 215 Rep Power: 3	lol ignore that, is sorted.... didnt notice i put addnode with lowercase n at end lol. think im gonna give it a rest today as i think I'm doing more harm than good. for the NULL pointers, what would you suggest? should i set them all to point to data item or a blank node?. i've been looking at various methods of balancing, and thought i may give the Andersson method a try.

Jan 29th, 2006, 7:24 PM	#7
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	No, they need to be NULL to indicate they're unusable. Just check them before you dereference them. It's easy to pull a pointer, see that it's not NULL (in other words, valid) and then dereference one of its child pointers, forgetting to check the child. Example: (Toggle Plain Text) if (myPtr != NULL) data = myPtr->leftChild->data; if (myPtr != NULL) data = myPtr->leftChild->data; If leftChild is NULL, your code is off in the weeds puking in its cuff. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C++

saving and loading a binary search tree