ifndef __BST define __BST include iostream Узел дерева template typena

 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
#ifndef __BST
#define __BST
#include <iostream>
/* Узел дерева. */
template <typename T>
struct TreeNode {
T _data;
TreeNode<T> * _parent, * _left, * _right;
TreeNode(T data) : _data(data), _parent(nullptr),
_left(nullptr), _right(nullptr) {}
TreeNode(T data, TreeNode<T> * parent) : _data(data),
_parent(parent), _left(nullptr), _right(nullptr) {}
TreeNode(T data, TreeNode<T> * left, TreeNode<T> * right) :
_data(data), _parent(nullptr), _left(left), _right(right) {}
TreeNode(T data, TreeNode<T> * parent, TreeNode<T> * left, TreeNode<T> * right) :
_data(data), _parent(parent), _left(left), _right(right) {}
};
/* Бинарное дерево поиска без повторений. */
template <typename T>
struct BinSearchTree {
TreeNode<T> * _root;
private:
/* Вспомогательная функция для функции insert. */
void insert(TreeNode<T> * current_node, TreeNode<T> * parent, T value) {
if (!current_node) {
current_node = new TreeNode<T>(value, parent);
return;
}
if (value < current_node->_data)
insert(current_node->_left, current_node, value);
else if (value > current_node->_data)
insert(current_node->_right, current_node, value);
}
/* Вспомогательная функция для функции print. */
void print(TreeNode<T> * node) {
if (!node)
return;
print(node->_left);
std::cout << node->_data << ' ';
print(node->_right);
}
public:
BinSearchTree() : _root(nullptr) {}
BinSearchTree(TreeNode<T> * root) : _root(root) {}
BinSearchTree(T data) : _root(new TreeNode<T>(data)) {}
/* Печатает содержимое дерева на экран по возрастанию (ЛКП).*/
void print() {
if (!_root)
return;
print(_root->_left);
std::cout << _root->_data << ' ';
print(_root->_right);
}
/* Вставляет элемент в БДП. */
void insert(T value) {
if (!_root) {
_root = new TreeNode<T>(value);
return;
}
if (value < _root->_data)
insert(_root->_left, _root, value);
else if (value > _root->_data)
insert(_root->_right, _root, value);
// std::cout << _root->_right;
}
};
#endif /* __BST */