345 lines
11 KiB
C++
345 lines
11 KiB
C++
//##################################################################
|
|
// PROGRAMMERINGSUPPGIFT 2
|
|
// DATASTRUKTURER OCH ALGORITMER
|
|
// AVL TRÄD
|
|
//==================================================================
|
|
// TREE.CPP
|
|
// Filen innehåller funktioner för trädet
|
|
// Christian Ohlsson
|
|
// Karlstad 980927
|
|
//==================================================================
|
|
|
|
#include "header.hpp"
|
|
|
|
//##################################################################
|
|
// SKAPAR ETT TRÄD & SÄTTER NODE TILL NULL
|
|
//==================================================================
|
|
treeClass::treeClass():node(NULL)
|
|
{
|
|
}
|
|
//##################################################################
|
|
// DESTROYTREE
|
|
// traverserar genom trädet rekursivt
|
|
// och raderar hela trädet
|
|
// pre: att det finns ett träd
|
|
// post: samtliga noder i trädet är borttagna
|
|
// calls: destroyTree (rekursivt)
|
|
//==================================================================
|
|
void treeClass::destroyTree(ptrType &node)
|
|
{
|
|
if(node->left != NULL)
|
|
destroyTree(node->left);
|
|
if(node->right != NULL)
|
|
destroyTree(node->right);
|
|
delete node;
|
|
node = NULL;
|
|
}
|
|
//##################################################################
|
|
// SKAPAR EN NOD
|
|
// pre: TRUE
|
|
// post: en ny nod har skapats
|
|
//==================================================================
|
|
treeNode::treeNode(nameType oneName,numberType oneNumber,
|
|
ptrType L, ptrType R, int H) : left(L),right(R),height(H)
|
|
{
|
|
strcpy(name, oneName);
|
|
strcpy(number,oneNumber);
|
|
}
|
|
//##################################################################
|
|
// SÖKER EFTER ETT ELEMENT I TRÄDET
|
|
// pre: att trädet inte är tomt
|
|
// post: NULL om noden inte fanns
|
|
// post: sökta noden om den fanns med
|
|
// calls: seek (rekursivt)
|
|
//==================================================================
|
|
ptrType treeClass::seek(ptrType node, nameType oneName)
|
|
{
|
|
ptrType treeNodeFound;
|
|
if(node == NULL)
|
|
treeNodeFound = NULL;
|
|
else if (strcmp(node->name, oneName) == 0)
|
|
treeNodeFound = node;
|
|
else if (strcmp(node->name, oneName) > 0)
|
|
treeNodeFound = seek(node->left, oneName);
|
|
else
|
|
treeNodeFound = seek(node->right, oneName);
|
|
return treeNodeFound;
|
|
}
|
|
//##################################################################
|
|
// KOLLAR OM DET FINNS NODER I TRÄDET
|
|
// pre: TRUE
|
|
// post: TRUE om trädet är tomt
|
|
// post: FALSE om det finns noder i trädet
|
|
//==================================================================
|
|
bool treeClass::isEmpty()
|
|
{
|
|
if (node==NULL)
|
|
return TRUE;
|
|
return FALSE;
|
|
}
|
|
//##################################################################
|
|
// SKRIVER UT TRÄDET I INORDER
|
|
// pre: att trädet inte är tomt
|
|
// post: trädet har skrivits ut i bokstavsordning
|
|
// calls: inOrder (rekursivt)
|
|
//==================================================================
|
|
void treeClass::inOrder(ptrType treeNode)
|
|
{
|
|
if(treeNode) {
|
|
inOrder(treeNode->left);
|
|
cout << setw(NAMESIZE)
|
|
<< treeNode->name
|
|
<< setw(NAMESIZE)
|
|
<< treeNode->number
|
|
<< setw(NAMESIZE)
|
|
<< treeNode->height << endl;
|
|
inOrder(treeNode->right);
|
|
}
|
|
}
|
|
//##################################################################
|
|
// SÄTTER IN EN NOD I TRÄDET
|
|
// pre: att personen inte redan finns
|
|
// post: trädet har fått en ny nod insatt
|
|
// på rätt plats.
|
|
// calls: insert (rekursivt)
|
|
//==================================================================
|
|
void treeClass::insert(ptrType &node,nameType oneName,numberType number, int height)
|
|
{
|
|
if(node==NULL)
|
|
node=new treeNode(oneName,number,NULL,NULL,height);
|
|
else if(strcmp(oneName, node->name) < 0)
|
|
insert(node->left,oneName,number,height);
|
|
else
|
|
insert(node->right,oneName,number,height);
|
|
}
|
|
//##################################################################
|
|
// SÖKER SIG FRAM TILL NODEN SOM SKALL TAS BORT
|
|
// pre: att det finns ett träd
|
|
// pre: att noden finns
|
|
// post: noden har hittats
|
|
// calls: delRoot, del (rekursivt)
|
|
//==================================================================
|
|
void treeClass::del(ptrType &node, nameType oneName)
|
|
{
|
|
if(strcmp(oneName,node->name) == 0)
|
|
delRoot(node);
|
|
else if(strcmp(oneName,node->name) < 0)
|
|
del(node->left, oneName);
|
|
else
|
|
del(node->right,oneName);
|
|
}
|
|
//##################################################################
|
|
// TAR BORT EN NODEN OM DEN INT HAR TVÅ BARN
|
|
// pre: att det finns ett träd
|
|
// pre: att noden finns
|
|
// post: noden har tagits ur trädet och
|
|
// de andra noderna sitter nu rätt placerade
|
|
// calls: delLeft
|
|
//==================================================================
|
|
void treeClass::delRoot(ptrType &node)
|
|
{
|
|
ptrType delPtr;
|
|
nameType nyItem;
|
|
numberType nyNumber;
|
|
|
|
if(node != NULL) {
|
|
if((node->left == NULL) && (node->right == NULL)) {
|
|
delete node;
|
|
node = NULL;
|
|
}
|
|
else if(node->left == NULL) {
|
|
delPtr = node;
|
|
node = node->right;
|
|
delPtr->right = NULL;
|
|
delete delPtr;
|
|
}
|
|
else if(node->right == NULL) {
|
|
delPtr = node;
|
|
node = node->left;
|
|
delPtr->left = NULL;
|
|
delete delPtr;
|
|
}
|
|
else {
|
|
delLeft(node->right, nyItem, nyNumber);
|
|
strcpy(node->name, nyItem);
|
|
strcpy(node->number, nyNumber);
|
|
}
|
|
}
|
|
}
|
|
//##################################################################
|
|
// TAR BORT EN NOD TILL VÄNSTER
|
|
// pre: att det finns ett träd
|
|
// pre: att noden finns
|
|
// post: noden har tagits ur trädet och
|
|
// de andra noderna sitter nu rätt placerade
|
|
// calls: delLeft (rekursivt)
|
|
//==================================================================
|
|
void treeClass::delLeft(ptrType &node, nameType oneName, numberType oneNumber)
|
|
{
|
|
if((node != NULL) && (node->left == NULL)) {
|
|
strcpy(oneName, node->name);
|
|
strcpy(oneNumber, node->number);
|
|
ptrType delPtr = node;
|
|
node = node->right;
|
|
delPtr->right = NULL;
|
|
delete delPtr;
|
|
}
|
|
else
|
|
delLeft(node->left, oneName, oneNumber);
|
|
}
|
|
//##################################################################
|
|
// ROTATI0N
|
|
// roterar trädet så att det blir ett AVL träd
|
|
// pre: att det finns ett träd
|
|
// post: trädets alla noder sitter balanserade
|
|
// calls: rotation (rekursivt), balance,
|
|
// singleLeft, singleRight, doubleRL, doubleLR
|
|
//==================================================================
|
|
void treeClass::rotation(ptrType &node)
|
|
{
|
|
if(node) {
|
|
rotation(node->left);
|
|
rotation(node->right);
|
|
if(balance(node) == 2) {
|
|
if(balance(node->right) >= 1)
|
|
singleLeft(node);
|
|
else if(balance(node->right) <= -1)
|
|
doubleRL(node);
|
|
}
|
|
else if(balance(node) == -2) {
|
|
if(balance(node->left) >= 1)
|
|
doubleLR(node);
|
|
else if(balance(node->left) <= -1)
|
|
singleRight(node);
|
|
}
|
|
}
|
|
}
|
|
//##################################################################
|
|
// BALANSERAR TRÄDET
|
|
// returnerar högerbarnets höjd minus vänsterbarnets
|
|
// pre: att trädet inte är tomt
|
|
// post: höjddifferansen är returnerad
|
|
// calls: none
|
|
//==================================================================
|
|
int treeClass::balance(ptrType &node) //eg root
|
|
{
|
|
int leftValue, rightValue;
|
|
if(node->left == NULL)
|
|
leftValue = -1;
|
|
else
|
|
leftValue = node->left->height;
|
|
if(node->right == NULL)
|
|
rightValue = -1;
|
|
else
|
|
rightValue = node->right->height;
|
|
return (rightValue - leftValue);
|
|
}
|
|
//##################################################################
|
|
// SINGLE LEFT ROTATION
|
|
// roterar åt vänster
|
|
// pre: att det finns ett träd
|
|
// post: trädet är vänsterroterat
|
|
// calls: none
|
|
//==================================================================
|
|
void treeClass::singleLeft(ptrType &node)
|
|
{
|
|
ptrType oldNode = node;
|
|
node = node->right;
|
|
oldNode->right = node->left;
|
|
node->left = oldNode;
|
|
}
|
|
//##################################################################
|
|
// SINGLE RIGHT ROTATION
|
|
// roterar åt höger
|
|
// pre: att det finns ett träd
|
|
// post: trädet är högerroterat
|
|
// calls: none
|
|
//==================================================================
|
|
void treeClass::singleRight(ptrType &node)
|
|
{
|
|
ptrType oldNode = node;
|
|
node = node->left;
|
|
oldNode->left = node->right;
|
|
node->right = oldNode;
|
|
}
|
|
//##################################################################
|
|
// DOUBLE RIGHT-LEFT ROTATION
|
|
// Utför en dubbel höger-vänster rotation
|
|
// pre: att det finns ett träd
|
|
// post: trädet är höger-vänster roterat
|
|
// calls: singleRight, singleLeft
|
|
//==================================================================
|
|
void treeClass::doubleRL(ptrType &node)
|
|
{
|
|
singleRight(node->right);
|
|
singleLeft(node);
|
|
}
|
|
//##################################################################
|
|
// DOUBLE LEFT-RIGHT ROTATION
|
|
// Utför en dubbel vänster-höger rotation
|
|
// pre: att det finns ett träd
|
|
// post: trädet är vänster-höger roterat
|
|
// calls: singleLeft, singleRight
|
|
//==================================================================
|
|
void treeClass::doubleLR(ptrType &node)
|
|
{
|
|
singleLeft(node->left);
|
|
singleRight(node);
|
|
}
|
|
//##################################################################
|
|
// SÄTTER ALLA HÖJDER I TRÄDET I POSTORDER
|
|
// pre: att trädet inte är tomt
|
|
// post: noderna i trädet har alla rätt höjd
|
|
// calls: setHeight (rekursivt), maxHeight
|
|
//==================================================================
|
|
void treeClass::setHeight(ptrType &node)
|
|
{
|
|
if(node) {
|
|
setHeight(node->left);
|
|
setHeight(node->right);
|
|
node->height = maxHeight(node) +1;
|
|
}
|
|
}
|
|
//##################################################################
|
|
// FINNER MAXIMAL HÖJD EN NOD BEFINNER SIG PÅ
|
|
// pre: att trädet inte är tomt
|
|
// post: maxhöjden har returnerats
|
|
// calls: inget
|
|
//==================================================================
|
|
int treeClass::maxHeight(ptrType &node)
|
|
{
|
|
int max;
|
|
if(node->left && node->right) {
|
|
max = node->left->height;
|
|
if(node->right->height > max)
|
|
return (node->right->height);
|
|
else
|
|
return max;
|
|
}
|
|
else if(node->left)
|
|
return (node->left->height);
|
|
else if(node->right)
|
|
return (node->right->height);
|
|
else
|
|
return (-1);
|
|
}
|
|
//##################################################################
|
|
// SPARAR TRÄDET PÅ FIL
|
|
// läser av nodens namn och nummer i alla noder i
|
|
// preorder och skriver de på filen.
|
|
// pre: att det finns ett träd
|
|
// post: trädet har sparats på fil
|
|
// calls: save (rekursivt)
|
|
//==================================================================
|
|
void treeClass::save(ptrType node, fstream &fil)
|
|
{
|
|
if(node) {
|
|
fil.write((char*)&node->name,sizeof(node->name));
|
|
fil.write((char*)&node->number,sizeof(node->number));
|
|
save(node->left,fil);
|
|
save(node->right,fil);
|
|
}
|
|
}
|
|
|
|
|