1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
/*
* cNode.h
*
* Created on: Jan 25, 2017
* Author: jonas
*/
#ifndef SRC_CNODE_H_
#define SRC_CNODE_H_
#include "cData.h"
#include <list>
#include <iostream>
using namespace std;
class cNode;
struct sSubTree
{
cNode *nextBigger;
cNode *nextSmaller;
};
class cNode {
public:
cNode();
virtual ~cNode();
virtual cData getDataObject() = 0;
/*
* returns dataObject
*/
virtual void insert(cData* _data, cNode** _me) = 0;
/*
* Inserts *cData into tree
* cNode** required to change pointer in the caller's pointer to next element
*/
virtual void insert(cNode* _data, cNode** _me) = 0;
/*
* Overloading Function to be able to insert complete subtrees
*/
virtual void remove(cData* _data, sSubTree* _subtree, cNode** _me) = 0;
/*
* Removes *cData from tree. Its subtree is stored in sSubTree*. cNode** refers to pointer to pointer to self to be able to change reference
*/
virtual cData* search(string _data) = 0;
/*
* Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result)
*/
virtual cData* getById(unsigned int _id, unsigned int& _cntr) = 0;
/*
* searches for obejct ID (-> inorder)
* int: wanted id
* int&: id counter
*/
virtual void getSortet(list<cData>* _list) = 0;
/*
* saves inorder list to *_list
*/
virtual unsigned int getSubtreeSize() = 0;
/*
* returns size of subtree
*/
virtual unsigned int getDepth(unsigned int _deppth) = 0;
/*
* returns maximum depth under node
* unsigned int: depth of parent
*/
virtual void draw(int _depth) = 0;
/*
*draws tree in ASCII
*/
virtual sSubTree getSubTree() = 0;
/*
* Returns subtree of this Node, nextSmaller and nextBigger are set to new Endnodes
*/
virtual cNode *getFirstNode(cNode** _me) = 0;
/*
* 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();
void insert(cData*, cNode**);
void insert(cNode*, cNode**);
void remove(cData*, sSubTree*, cNode**);
cData* search(string);
cData* getById(unsigned int, unsigned int&);
void getSortet(list<cData>* _list);
void draw(int _depth);
unsigned int getSubtreeSize();
unsigned int getDepth(unsigned int);
sSubTree getSubTree();
cNode *getFirstNode(cNode**);
private:
cNode *nextSmaller, *nextBigger;
cData *data;
};
class cEndnode:public cNode
{
public:
//TODO Optimize! there are 2^(n+1) endnodes in a tree wich each take 4B!
cEndnode();
~cEndnode();
cData getDataObject();
void insert(cData*, cNode** );
void insert(cNode*, cNode**);
void remove(cData*, sSubTree*, cNode**);
cData* search(string);
cData* getById(unsigned int, unsigned int&);
void getSortet(list<cData>* _list);
unsigned int getSubtreeSize();
unsigned int getDepth(unsigned int);
void draw(int _depth);
sSubTree getSubTree();
cNode *getFirstNode(cNode**);
bool isEndnode();
private:
};
#endif /* SRC_CNODE_H_ */
|