summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--tree/src/cNode.cpp23
-rw-r--r--tree/src/cNode.h13
-rw-r--r--tree/src/cTree.cpp18
-rw-r--r--tree/src/cTree.h37
-rw-r--r--tree/src/main.cpp4
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;