summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--tree/src/cNode.cpp16
-rw-r--r--tree/src/cNode.h50
-rw-r--r--tree/src/cTree.cpp35
-rw-r--r--tree/src/main.cpp21
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<cData>* _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<cData>* _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<cData>* _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)
{