From ce3334f3d962ac2b64fcb47c7deb1fd9234d5ffa Mon Sep 17 00:00:00 2001 From: jonas Date: Wed, 8 Mar 2017 16:17:56 +0100 Subject: Fixed new Remove -cData *cData() : Added bool _empty to init empty data object +isEmpty() : true if init as empty -cEndnode *getDataObject() : now returns empty cData instead of NULL -cNode +isEndnode() : returns true for cEndnode, else false -cDatanode *insert() : now ignores Endnodes -cTree() *remove() : Fixed memory exception when subTree contained Endnode --- tree/src/cNode.cpp | 16 ++++++++++++---- tree/src/cNode.h | 50 +++++++++++++++++++++++--------------------------- tree/src/cTree.cpp | 35 +++++++++++++++++------------------ tree/src/main.cpp | 21 +++++++++++++++++++-- 4 files changed, 71 insertions(+), 51 deletions(-) diff --git a/tree/src/cNode.cpp b/tree/src/cNode.cpp index c8035f8..3b4eb19 100644 --- a/tree/src/cNode.cpp +++ b/tree/src/cNode.cpp @@ -9,6 +9,11 @@ cNode::cNode() {} cNode::~cNode(){} +bool cNode::isEndnode() +{ + return false; +} + // //===================================================================================================================== // @@ -44,7 +49,7 @@ void cDatanode::insert(cData* _data, cNode** _me) void cDatanode::insert(cNode* _data, cNode** _me) { - if( _data->getDataObject().isEmpty()) + if( _data->isEndnode()) return; //_data is endnode, return if (_data->getDataObject() > *data) @@ -145,10 +150,8 @@ cNode *cDatanode::getFirstNode(cNode** _me) { cNode* ret = nextSmaller->getFirstNode(&nextSmaller); if(ret) //Pointer not empty, return ret - { return ret; - } - else //Pointer is empty, Return me + else //Pointer is empty, This is the last Object in branch { cNode* tmp = *_me; *_me = new cEndnode(); @@ -228,6 +231,11 @@ cNode *cEndnode::getFirstNode(cNode** _me){ return NULL; } +bool cEndnode::isEndnode() +{ + return true; +} + diff --git a/tree/src/cNode.h b/tree/src/cNode.h index c39dc60..06b779c 100644 --- a/tree/src/cNode.h +++ b/tree/src/cNode.h @@ -79,41 +79,41 @@ public: /* * Returns Pointer to Inorder-First element in Tree */ + virtual bool isEndnode(); + /* + * Returns false for Endnode, else true + */ }; class cDatanode:public cNode { public: cDatanode(cData* _data); + ~cDatanode(); cData getDataObject(); - /* - * returns dataObject - */ + void insert(cData*, cNode**); - /* - * Inserts *cData into tree - */ + void insert(cNode*, cNode**); + void remove(cData*, sSubTree*, cNode**); - /* - * Removes *cData from tree - */ + cData* search(string); - /* - * Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result) - */ + cData* getById(unsigned int, unsigned int&); void getSortet(list* _list); - /* - * Copy all cData Instances into _list - */ + void draw(int _depth); + unsigned int getSubtreeSize(); + unsigned int getDepth(unsigned int); + sSubTree getSubTree(); + cNode *getFirstNode(cNode**); private: cNode *nextSmaller, *nextBigger; @@ -129,22 +129,15 @@ public: ~cEndnode(); cData getDataObject(); - /* - * returns dataObject - */ + void insert(cData*, cNode** ); - /* - * Inserts *cData into tree - */ + void insert(cNode*, cNode**); + void remove(cData*, sSubTree*, cNode**); - /* - * Removes *cData from tree - */ + cData* search(string); - /* - * Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result) - */ + cData* getById(unsigned int, unsigned int&); void getSortet(list* _list); @@ -158,6 +151,9 @@ public: sSubTree getSubTree(); cNode *getFirstNode(cNode**); + + bool isEndnode(); + private: }; diff --git a/tree/src/cTree.cpp b/tree/src/cTree.cpp index ef6556e..3631fc6 100644 --- a/tree/src/cTree.cpp +++ b/tree/src/cTree.cpp @@ -30,33 +30,32 @@ void cTree::insert(string _data) void cTree::remove(cData* _data) { + //Remove sSubTree subTree; root->remove(_data, &subTree, &root); - cout << "Remove Finished\n"; + //Re-Insert subtree if(subTree.nextBigger && subTree.nextSmaller) { - cNode* newRoot = subTree.nextSmaller->getFirstNode( &(subTree.nextSmaller)); - cout << "Got new root\n"; + cNode* newRoot = subTree.nextSmaller->getFirstNode( &(subTree.nextSmaller)); //returns zero - root->insert(newRoot, &root ); - cout << "Inserted new root\n"; + if(newRoot) //Only insert if nextSmaller is no Endnode + { + root->insert(newRoot, &root ); + } } - if (subTree.nextBigger) - { - root->insert(subTree.nextBigger, &root); - cout << "nextBigger inserted\n"; + if (subTree.nextBigger) { + if(!subTree.nextBigger->isEndnode()) //Inserting Endnodes is pointless + root->insert(subTree.nextBigger, &root); + else + delete subTree.nextBigger; //Delete pointless Endnode } - if(subTree.nextSmaller) - { - root->insert(subTree.nextSmaller, &root); - cout << "nextSmaller inserted\n"; + if(subTree.nextSmaller) { + if(!subTree.nextSmaller->isEndnode()) + root->insert(subTree.nextSmaller, &root); + else + delete subTree.nextSmaller; } - - //Insert remaining subtree - - - }//remove void cTree::getList(list* _list) diff --git a/tree/src/main.cpp b/tree/src/main.cpp index b5db0c5..88a17c7 100644 --- a/tree/src/main.cpp +++ b/tree/src/main.cpp @@ -14,10 +14,16 @@ using namespace std; cTree* a; +//Function Prototypes void fill(void); void stress(void); +void fillSmall(void); + +// +//MAIN +// int main (void) { a = new cTree(); @@ -53,11 +59,12 @@ int main (void) switch(iInputOption) { case 0: //fill + delete a; return 0; break; case 1: //fill cout << "Filling with Data....."; - fill(); + fillSmall(); cout << "OK\n"; break; case 2: //clear @@ -99,7 +106,7 @@ int main (void) delete a; return 0; -} +}//main void fill(void) { @@ -116,6 +123,16 @@ void fill(void) } } +void fillSmall(void) +{ + for(char c = 'a'; c<= 'z'; c++) + { + stringstream ss; + ss << c; + + a->insert(ss.str()); + } +} void stress(void) { -- cgit v1.2.3