-
Notifications
You must be signed in to change notification settings - Fork 1
/
tree_lib.h
156 lines (109 loc) · 4.08 KB
/
tree_lib.h
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
#include <iostream>
#include <vector>
using namespace std;
// Note: The terms "leaf" and "node" are used a lot in this and are the same thing
// ^ this is because I changed the class name from Node to Leaf
class Leaf {
public:
// Just made it able to acctually hold a peice of data
string data;
// Right & left child leafs
Leaf *left = NULL;
Leaf *right = NULL;
// default value
// value: basically a header or name of the node in this
// ^ you don't want to edit this or some weird stuff might happen
int value;
// very simple leaf initialization
Leaf (int val) {
this->value = val;
}
void del() {
delete left;
delete right;
delete this;
}
};
class Tree {
public:
// "nodes" is the root node or leaf
Leaf *nodes;
int node_count=1;
//Initializes the root node
Tree (int root_value) {
this->nodes = new Leaf(root_value);
}
// gets a leaf by its value/header
// you can edit the leaf through this too, because I am using pointers too much, oh well
Leaf *get_leaf(int value) {
// current_node: used for sorting through the nodes/leafs
Leaf *current_node = this->nodes;
// loops through the leafs and moves from leaf to leaf in the correct order
for (int pos=0; pos<this->node_count; pos++) {
// if the current nodes value/header is equal to the value/header we are looking for, return the node
if (current_node->value==value) {
return current_node;
}
// Set current node to this leafs left child node if current leafs val < search header/val
else if (current_node->value < value) {
current_node = current_node->left;
// If the left node is null, break, we couldn't find the node with the correct value/header
if (current_node==NULL) break;
}
// Set current node to this leafs right child node if current leafs val > search header/val
else if (current_node->value > value) {
current_node = current_node->right;
// If the right node is null, break, we couldn't find the node with the correct value/header
if (current_node==NULL) break;
}
}
// delete the pointer
delete ¤t_node;
// leaf couldn't be found
return NULL;
}
// adds a leaf/node to the tree
// less comments in this section because a lot of it is explained by the get_node function
void add_leaf(Leaf *new_node) {
// current_node: used for sorting through the leafs/nodes
Leaf *current_node = this->nodes;
// node_count: gotta keep track of how many nodes there are!
this->node_count+=1;
for(int i=0;i<this->node_count;i++) {
if (current_node->value < new_node->value) {
// if the current nodes left child leaf is NULL than replace it with the new node
if (current_node->left==NULL) {
current_node->left = new_node;
break;
}
current_node = current_node->left;
}
else if (current_node->value > new_node->value) {
// if the current nodes left child leaf is NULL than replace it with the new node
if (current_node->right==NULL) {
current_node->right = new_node;
break;
}
current_node = current_node->right;
}
}
// clears pointer from mem
delete ¤t_node;
}
// gets a leaf and deletes it, very simple
void delete_leaf(int value) {
this->get_leaf(value)->del();
}
// clears all nodes/leafs except the root
void clear() {
int val = this->nodes->value;
delete nodes;
nodes = new Leaf(val);
}
// delets the tree as a whole
void del() {
// clears the current Tree from memory
delete nodes;
delete this;
}
};