Added useful functions

+cTree::size()
+cTree::depth()
+cTree::gradeOfUnbalance()
+cNode::getSubtreeSize()
+cNode::getDepth()

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;