diff options
-rw-r--r-- | tree/src/cNode.cpp | 23 | ||||
-rw-r--r-- | tree/src/cNode.h | 13 | ||||
-rw-r--r-- | tree/src/cTree.cpp | 18 | ||||
-rw-r--r-- | tree/src/cTree.h | 37 | ||||
-rw-r--r-- | tree/src/main.cpp | 4 |
5 files changed, 94 insertions, 1 deletions
diff --git a/tree/src/cNode.cpp b/tree/src/cNode.cpp index 8340367..ae012cf 100644 --- a/tree/src/cNode.cpp +++ b/tree/src/cNode.cpp @@ -83,6 +83,21 @@ void cDatanode::draw(int _depth) nextBigger->draw(_depth + 1); } + +unsigned int cDatanode::getDepth(unsigned int _depth) +{ + unsigned int depth1, depth2; + + depth1 = nextSmaller->getDepth(_depth + 1); + depth2 = nextBigger->getDepth(_depth + 1); + + return depth1 < depth2 ? depth2:depth1; //return bigger depth +} + +unsigned int cDatanode::getSubtreeSize() +{ + return nextSmaller->getSubtreeSize() + nextBigger->getSubtreeSize() + 1; +} // //============================================================================================================================== // @@ -125,7 +140,15 @@ void cEndnode::draw(int _depth) cout << "|-$\n"; } +unsigned int cEndnode::getSubtreeSize() +{ + return 0; +} +unsigned int cEndnode::getDepth(unsigned int _depth) +{ + return _depth; +} diff --git a/tree/src/cNode.h b/tree/src/cNode.h index 561e094..97b6c81 100644 --- a/tree/src/cNode.h +++ b/tree/src/cNode.h @@ -40,6 +40,14 @@ public: /* * gets sortet list */ + virtual unsigned int getSubtreeSize() = 0; + /* + * returns size of tree under node + */ + virtual unsigned int getDepth(unsigned int) = 0; + /* + * returns maximum depth under node + */ virtual void draw(int _depth) = 0; }; @@ -71,6 +79,8 @@ public: * Copy all cData Instances into _list */ void draw(int _depth); + unsigned int getSubtreeSize(); + unsigned int getDepth(unsigned int); private: cNode *nextSmaller, *nextBigger; cData *data; @@ -101,6 +111,9 @@ public: */ void getSortet(list<cData>* _list); + unsigned int getSubtreeSize(); + unsigned int getDepth(unsigned int); + void draw(int _depth); private: }; diff --git a/tree/src/cTree.cpp b/tree/src/cTree.cpp index 6b6cfa4..9f39f79 100644 --- a/tree/src/cTree.cpp +++ b/tree/src/cTree.cpp @@ -97,6 +97,24 @@ void cTree::sort() insertList(&sortetList); } +unsigned int cTree::size() +{ + return root->getSubtreeSize(); +} + +unsigned int cTree::depth() +{ + return root->getDepth(0); +} + +unsigned int cTree::gradeOfUnbalance() +{ + double minDepth = log2(size()); + unsigned int iDepth = depth(); + + return (iDepth / minDepth) - 1; //-1 so 100% = 0 +} + diff --git a/tree/src/cTree.h b/tree/src/cTree.h index cff7dcd..bb342a2 100644 --- a/tree/src/cTree.h +++ b/tree/src/cTree.h @@ -11,6 +11,7 @@ #include "cNode.h" #include <string> #include <list> +#include <math.h> using namespace std; @@ -19,13 +20,47 @@ public: cTree(); ~cTree(); void insert(cData*); + /* + * inserts element into tree + */ void insert(string); + /* + * inserts string into tree + */ void insertList(list<cData>*); - void balance(); + /* + * inserts List into tree as balanced as possible + */ void getList(list<cData>*); + /* + * returns inorder list + */ void remove(cData*); + /* + * remove node from tree + */ void sort(); + /* + * balances tree + */ void clear(); + /* + * emptys the tree + */ + unsigned int size(); + /* + * returns overall size + */ + unsigned int depth(); + /* + * returns maximum depth + */ + unsigned int gradeOfUnbalance(); + /* + * returns number from 0 - 10 + * 0: Balanced + * 10: most unbalanced + */ cData* search(string); void draw(); diff --git a/tree/src/main.cpp b/tree/src/main.cpp index 0b9299a..5ee6501 100644 --- a/tree/src/main.cpp +++ b/tree/src/main.cpp @@ -19,9 +19,13 @@ int main (void) } a->draw(); + cout << a->size() << "/" << a->depth() << endl; + cout << a->gradeOfUnbalance() << endl; cout << "-------------------" << endl; a->sort(); a->draw(); + cout << a->size() << "/" << a->depth() << endl; + cout << a->gradeOfUnbalance() << endl; delete a; |