Programutvecklingsmetodik/Binary_Search_Tree/huvud.cpp

//########################################################
//        LAB 4 I PUMA
//        CRILLE & ROBIN 980120
//        BINÄRT SÖK TRÄD
//========================================================

#ifndef _HEADER_
#define _HEADER_              //definiera _HEADER_
#include <iostream.h>         //för in och utmatning
#include <conio.h>            //för getch()
#include <assert.h>           //för assert()
#include <stddef.h>				//för definition av NULL
#include <string.h>        	//för säker inmatning
#include <stdlib.h>				//för atoi()
#include <fstream.h>				//för save & load

const int FALSE = 0;          //boolsk variabel
const int TRUE = !FALSE;      //boolsk variabel
const int BUFFERSIZE = 100;	//för säker inmatning
const int NAMESIZE = 8;		//för MS-DOS 6.0

typedef int bool;					//definierar boolsk variabel
typedef int dataType;			//sätter datatypen
struct treeNode;					//förvarnar datorn om en struct
typedef treeNode* ptrType;		//ger en pekartype till en struct
struct treeNode					//en nod i trädet
{
	dataType data;
	ptrType left;
	ptrType right;
	treeNode(dataType item, ptrType left, ptrType right);
};
#include "tree.cpp"				//inkluderar trädets funktioner
#endif								//avslutar _HEADER_ definition

//#####################################################
// SÄKER INMATNING
//		ser till att bara heltal matas in
//		returnerar värdet om ok, annars nytt försök
//=====================================================
int mataIn()
{
	char buffer[BUFFERSIZE];
	int f;
	do
	{
		cin >> buffer;
		if (strcmp(buffer,"0") == 0)
			return 0;
		else
		{
			f = atoi(buffer);
			if (f!=0)
				return f;
			else
				cout <<" Inget tal, försok igen: ";
		}
	}while (!f);
}
//########################################################
// SÄTTER IN EN NOD I TRÄD
//		calls: treeClass::insert
//		calls: mataIn
//========================================================
void _insert(treeClass &myTree)
{
	dataType item;
	cout <<" Vad vill du sätta in i trädet: ";
	item=mataIn();
	myTree.insert(myTree.root,item);
}
//########################################################
//	TAR BORT EN NOD UR TRÄD
// 	calls: treeClass::del
//		calls: treeClass::isEmpty
//		calls: mataIn
//========================================================
void _del(treeClass &myTree)
{
	if(!myTree.isEmpty())
	{
		dataType item;
		cout << " Vad vill du ta bort : ";
		item=mataIn();
		if(myTree.seek(myTree.root, item) != NULL)
		{
			myTree.del(myTree.root, item);
			return;
		}
		else
			cout << " Noden " << item << " finns inte. ";
	}
	else
		cout << " Du har inte gjort något träd ännu... ";
	getch();
}
//########################################################
//	SKRIVER UT I PREORDER
//		calls: treeClass::preOrder
//		calls: treeClass::isEmpty
//		calls: mataIn
//========================================================
void _preOrder(treeClass myTree)
{
	if(!myTree.isEmpty())
		myTree.preOrder(myTree.root);
	else
		cout << " Du har inte gjort något träd ännu... ";
	getch();
}
//########################################################
//	SKRIVER UT I INORDER
//		calls: treeClass::inOrder
//		calls: treeClass::isEmpty
//		calls: mataIn
//========================================================
void _inOrder(treeClass myTree)
{
	if(!myTree.isEmpty())
		myTree.inOrder(myTree.root);
	else
		cout << " Du har inte gjort något träd ännu... ";
	getch();
}
//########################################################
//	SKRIVER UT I POSTORDER
//		calls: treeClass::postOrder
//		calls: treeClass::isEmpty
//		calls: mataIn
//========================================================
void _postOrder(treeClass myTree)
{
	if(!myTree.isEmpty())
		myTree.postOrder(myTree.root);
	else
		cout << " Du har inte gjort något träd ännu... ";
	getch();
}
//########################################################
// SÖKER I TRÄDET
//		calls: treeClass::seek
//		calls: treeClass::isEmpty
//		calls: mataIn
//========================================================
void _seek(treeClass myTree)
{
	if(!myTree.isEmpty())
	{
		dataType item;
		cout << " Mata in sökta värdet: ";
		item=mataIn();
		if(myTree.seek(myTree.root, item) != NULL)
			cout << " Ja, noden  "<< item << " fanns med...";
		else
			cout << " Nej, noden "<< item << " fanns inte med...";
	}
	else
		cout << " Du har inte gjort något träd ännu... ";
	getch();
}
//########################################################
// SPARAR TRÄDET PÅ FIL
//		calls: treeClass::save
//		calls: treeClass::isEmpty
//========================================================
void _save(treeClass myTree)
{
	if(!myTree.isEmpty())
	{
		fstream fil;
		char filnamn[NAMESIZE];
		cout << " Ange filnamn att spara: ";
		cin >> filnamn;
		fil.open(filnamn,ios::out|ios::binary);
		myTree.save(myTree.root, fil);
		fil.close();
	}
	else
	{
		cout << " Du har inte gjort något träd ännu...";
		getch();
	}
}
//########################################################
// HÄMTAR ETT TRÄD FRÅN EN FIL
//		läser in värdet i varje nod i preorder
//		och sätter in det i trädet i preoder
//		calls treeClass::insert
//		calls: treeClass::isEmpty
//========================================================
void _load(treeClass &myTree)
{
	if(myTree.isEmpty())
	{
		fstream fil;
		dataType item;
		char filnamn[NAMESIZE];
		cout << " Ange filnamn att hämta: ";
		cin >> filnamn;
		fil.open(filnamn,ios::in|ios::binary);
		if(fil)
			while(fil.peek() != EOF)
			{
				fil.read((char*)&item,sizeof(item));
				myTree.insert(myTree.root, item);
			}
		else
		{
			cout << " Filen finns inte...";
			getch();
		}
		fil.close();
	}
	else
	{
		cout << " Det finns redan värden i trädet. \n"
			  << " Du måste ta bort samtliga noder \n"
			  << " eller starta om programmet före \n"
			  << " du kan hämta ett träd från fil \n";
		getch();
	}
}
//########################################################
//	MENY ITEMS
//		skriver ut menyn på skärmen
//========================================================
void meny()
{
	clrscr();
	cout << " \n  BINÄRT SÖK TRÄD "
		  << " \n  --------------- "
		  << " \n 1. Lägg till nod "
		  << " \n 2. Ta bort nod "
		  << " \n 3. Sök efter nod "
		  << " \n 4. Skriv ut i preorder "
		  << " \n 5. Skriv ut i inorder "
		  << " \n 6. Skriv ut i postorder "
		  << " \n 7. Spara trädet på fil "
		  << " \n 8. Hämta träd från fil "
		  << " \n 0. Avsluta ";
	gotoxy(2,14);				 //ställer markören under menyn
}
//########################################################
// MAIN FUNCTION
//		skapar trädet myTree av typen treeClass
//		calls: alla drivrutiner
//========================================================
void main()
{
	treeClass myTree;
	char val = TRUE;
	do
	{
		meny();
		cin >> val;
		switch (val)
		{
			case '1' : _insert(myTree);break;
			case '2' : _del(myTree);break;
			case '3' : _seek(myTree);break;
			case '4' : _preOrder(myTree);break;
			case '5' : _inOrder(myTree);break;
			case '6' : _postOrder(myTree);break;
			case '7' : _save(myTree);break;
			case '8' : _load(myTree);break;
			case '0' : cout << " Programmet avslutat";break;
			default  : cout << " Felaktigt val";
						  getch();
		}
	}while(val != '0');
}