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
|
#ifndef BINARY_TREE_HPP
#define BINARY_TREE_HPP
#include <cstdio>
#include <iostream>
template<typename T>
class BinaryTree;
template<typename T>
class Node;
// class that descibes a node in the tree
template<typename T>
class Node {
friend BinaryTree<T>;
public:
// create an empty node with no next and only adding the item
Node(const T& it, const T& height) : item(it), next_left(NULL),
next_right(NULL), height(height), depth(0), bf(0) {
}
// create a new node with next nodes
Node(const T& it, Node<T> *n_left, Node<T> n_right)
: item(it), next_left(n_left), next_right(n_right) {
}
// nothing needed in destructor
~Node() {
std::cout << "This is the Node destructor" << std::endl;
}
// overloading the operators for ease of use
friend bool operator==(const Node<T>& n1, const Node<T>& n2) {
return n1.item == n2.item;
}
friend bool operator!=(const Node<T>& n1, const Node<T>& n2) {
return !(n1 == n2);
}
friend bool operator<(const Node<T>& n1, const Node<T>& n2) {
return n1.item < n2.item;
}
friend bool operator>(const Node<T>& n1, const Node<T>& n2) {
return n1.item > n2.item;
}
friend bool operator<=(const Node<T>& n1, const Node<T>& n2) {
return !(n1.item > n2.item);
}
friend bool operator>=(const Node<T>& n1, const Node<T>& n2) {
return !(n1.item < n2.item);
}
friend std::ostream& operator<<(std::ostream& out, const Node<T>& n) {
out << n.item;
return out;
}
protected:
private:
// item stored in the tree
T item;
// pointers to the next elements in the tree
Node<T> *next_left, *next_right;
// distance from node to leaf
unsigned int height;
// distance from node to root
unsigned int depth;
// height of the right subtree - height of the left subtree
signed int bf;
};
// tree of all the nodes
template<typename T>
class BinaryTree {
typedef Node<T> *node_ptr;
public:
// empty tree node which will then be created when adding elements
BinaryTree() : root_node(NULL), tree_height(0) {
}
~BinaryTree() {
std::cout << "This is the Binary Tree destructor" << std::endl;
delete_nodes(root_node);
}
// adds an element to the tree
void push_back(const T& element) {
// create new node with element
node_ptr new_node = new Node<T>(element, tree_height);
if(root_node == NULL) {
root_node = new_node;
} else {
// make current node
node_ptr curr_node = root_node;
bool found = false;
// go to node that has to be added
while(!found) {
if(*new_node < *curr_node) {
if(curr_node->next_left != NULL) {
curr_node = curr_node->next_left;
} else {
found = true;
curr_node->next_left = new_node;
}
} else {
if(curr_node->next_right != NULL) {
curr_node = curr_node->next_right;
} else {
found = true;
curr_node->next_right = new_node;
}
}
}
}
}
void set_height_depth(node_ptr node) {
if(node != NULL) {
}
}
void delete_nodes(node_ptr node) {
if(node != NULL) {
this->delete_nodes(node->next_left);
this->delete_nodes(node->next_right);
std::cout << "deleting node: " << *node << std::endl;
delete node;
}
}
void print_tree() {
print_tree(root_node);
}
void print_tree(node_ptr node) {
if(node != NULL) {
print_tree(node->next_left);
std::cout << *node << std::endl;
print_tree(node->next_right);
}
}
private:
// root of the tree
node_ptr root_node;
// height of the whole tree
unsigned int tree_height;
};
#endif
|
