Дерево при помощи классов

Реализация двоичного дерева поиска

В ссылочных реализациях структур данных данные хранятся в виде отдельных элементов, связанных между собой указателями. Элементы организованы либо в виде последовательности (списка), либо в виде дерева. Рассмотрим организацию ссылочной структуры данных на основе двоичного дерева поиска.

В двоичном дереве поиска хранятся элементы, которые можно сравнивать между собой при помощи операций «меньше» и «больше», например, это могут быть числа или строки.

Все элементы, которые хранятся в дереве — уникальные, то есть одно число не может быть записано в двух вершинах дерева. У каждой вершины дерева есть два поддерева — левое и правое (они могут быть и пустыми), причем в левом поддереве все элементы меньше значения, записанного в данной вершине, а в правом поддереве — больше.

Пример правильно построенного двоичного дерева поиска:

Благодаря такому представлению, все операции с деревом (поиск элемента, добавление элемента, удаление элемента) выполняются за время, пропорциональное высоте дерева, а не его размеру. Это позволяет (используя специальные алгоритмы балансировки дерева) реализовать эффективные структуры данных типа «множество», в которых все операции осуществляются за $O(\log n)$, где $n$ — количество элементов в множестве.

Объявление классов tree_elem и binary_tree

Для представления одной вершины (узла) двоичного дерева поиска создадим класс tree_elem . У элементов этого класса будут следующие поля:

m_data — данные (число), которые хранятся в этой вершине.

m_left — указатель на левого потомка данной вершины.

m_right — указатель на правого потомка данной вершины.

class tree_elem
public:
int m_data;
tree_elem * m_left;
tree_elem * m_right;
tree_elem(int val)
m_left = NULL; // В С++11 лучше использовать nullptr
m_right = NULL;
m_data = val;
>
>;

Конструктор для данного класса создает элемент, записывает в него переданные данные, левые и правые поддеревья инициализирует нулевыми указателями.

Рассмотрим описание класса binary_tree .

class binary_tree
private:
tree_elem * m_root;
int m_size;
void print_tree(tree_elem *);
void delete_tree(tree_elem *);

public:
binary_tree(int);
~binary_tree();
void print();
bool find(int);
void insert(int);
void erase(int);
int size();
>;

m_root — указатель на корень дерева.

m_size хранит в себе количество элементов в дереве.

Метод find() проверяет, содержится ли данный элемент в дереве, метод print() выводит все элементы поддерева, метод insert() добавляет новый элемент в дерево, метод erase() удаляет значение из дерева, метод size() возвращает значение.

Вспомогательные методы print_tree() и delete_tree() используются в рекурсивных алгоритмах обхода дерева и удаления дерева.

Конструктор

Конструктор класса binary_tree создает дерево из одного элемента. Для простоты будем считать, что в дереве всегда должен быть хотя бы один элемент.

Деструктор

Деструктор должен удалить все элементы дерева, для каждого из них вызвав оператор delete . Для этого реализована рекурсивная процедура delete_tree . Она рекурсивно вызывает себя для удаления левого поддерева, правого поддерева, затем удаляет сам элемент.

Сам деструктор просто вызывает рекурсивную процедуру delete_tree начиная от корня.

void binary_tree::delete_tree(tree_elem * curr)
if (curr)
delete_tree(curr->m_left);
delete_tree(curr->m_right);
delete curr;
>
>

Обход дерева

Обход дерева также реализуется рекурсивной процедурой — сначала зайдем в левое поддерево, потом в правое поддерево.

Метод print() рекурсивно обходит дерево и выводит его элементы в порядке возрастания.

void binary_tree::print()
print_tree(m_root);
cout >

void binary_tree::print_tree(tree_elem * curr)
if (curr) // Проверка на ненулевой указатель
print_tree(curr->m_left);
cout m_data print_tree(curr->m_right);
>
>

Поиск элемента в дереве

Метод find проверяет, содержится ли в дереве элемент со значением key и возвращает true или false . Поиск начинается от корня. Если key меньше того, что хранится в корне — спускаемся в левое поддерево, если больше — то в правое поддерево. Продолжаем до тех пор, пока не найдем нужный элемент, или не дойдем до пустого поддерева.

Добавление элемента в дерево

Метод добавления элемента в дерево аналогичен методу поиска элемента — ищется позиция, где может находиться данный элемент. Если элемент не найден, то нужно создать новый элемент дерева в том месте, где он должен находиться.

Удаление элемента из дерева

Удаление элемента из дерева — наиболее сложный из методов. Сначала найдем элемент, который нужно удалить (указатель curr ), указатель parent указывает на его предка.

Если у curr нет левого поддерева (условие curr->m_left == NULL ), то вместо curr можно подвесить его правое поддерево целиком, то есть элемент curr удаляется, а на его место становится его правое поддерево curr->m_right .

Аналогично, если у curr нет правого поддерева, то вместо него можно подвесить целиком левое поддерево.

Самый сложный случай — если у curr есть и левое, и правое поддерево. В этом случае на место элемента curr поставим наименьший элемент, который больше него. Для этого нужно спуститься в правое поддерево элемента curr , и в этом поддереве найти наименьший элемент — для этого будем двигаться указателем всегда в левого потомка текущего элемента, пока не найдем элемент, у которого нет левого потомка. Этот элемент можно удалить той же самой процедурой (т.к. у него нет левого потомка, то это простой случай удаления), а его значение записать на место элемента curr .

void binary_tree::erase(int key)
tree_elem * curr = m_root;
tree_elem * parent = NULL;
while (curr && curr->m_data != key)
parent = curr;
if (curr->m_data > key)
curr = curr->m_left;
>
else
curr = curr->m_right;
>
>
if (!curr)
return;
if (curr->m_left == NULL)
// Вместо curr подвешивается его правое поддерево
if (parent && parent->m_left == curr)
parent->m_left = curr->m_right;
if (parent && parent->m_right == curr)
parent->m_right = curr->m_right;
—m_size;
delete curr;
return;
>
if (curr->m_right == NULL)
// Вместо curr подвешивается его левое поддерево
if (parent && parent->m_left == curr)
parent->m_left = curr->m_left;
if (parent && parent->m_right == curr)
parent->m_right = curr->m_left;
—m_size;
delete curr;
return;
>
// У элемента есть два потомка, тогда на место элемента поставим
// наименьший элемент из его правого поддерева
tree_elem * replace = curr->m_right;
while (replace->m_left)
replace = replace->m_left;
int replace_value = replace->m_data;
erase(replace_value);
curr->m_data = replace_value;
>

Источник

Класс бинарное дерево

Здравствуйте.
Требуется написать англо-русский словарь на основе бинарного дерева. Не полностью понимаю, как будет выглядеть класс. Каждое слово должно быть элементом бинарного дерева, в котором будет ссылка на следующее, предыдущее слово и перевод, насколько понимаю, но тогда структура выстроится с линейный список.
Помогите описать класс, сам не могу разобраться.
Заранее спасибо.

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.

Создать шаблонный класс «бинарное дерево»
Создать шаблон класса «бинарное дерево». Использовать его для сортировки целых чисел и строк.

Описать класс, реализующий бинарное дерево
Здравствуйте! Возникли проблемы с реализацией одной программы . Описать класс, реализующий.

Нужно реализовать класс Бинарное дерево.
Нужно реализовать класс Бинарное дерево. Вот класс template <class T> class Tree < private.

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

#ifndef TREENODE_H #define TREENODE_H template typename T > class Tree; template typename T > class TreeNode { friend class Tree T >; public: TreeNode(); TreeNode(const T &); T get_data() const; private: T _data; TreeNode T > *_left; TreeNode T > *_right; }; template typename T > TreeNode T >::TreeNode(): _left(0), _right(0) { } template typename T > TreeNode T >::TreeNode(const T &data): _data(data), _left(0), _right(0) { } template typename T > T TreeNode T >::get_data() const { return _data; } #endif

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 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268

#ifndef TREE_H #define TREE_H #include "TreeNode.h" template typename T > class Tree { template typename Type > friend Type max(const Type &, const Type &); public: Tree(); ~Tree(); void insert(const T &); void remove(const T &); void pre_order() const; void in_order() const; void post_order() const; int depth() const; void print() const; private: TreeNode T > *_root; void insert_helper(TreeNode T > **, const T &); void remove_helper(TreeNode T > **, const T &); void pre_order_helper(TreeNode T > *) const; void in_order_helper(TreeNode T > *) const; void post_order_helper(TreeNode T > *) const; void delete_helper(TreeNode T > *); int depth_helper(TreeNode T > *) const; void print_helper(TreeNode T >*, int) const; }; template typename T > Tree T >::Tree(): _root(0) { } template typename T > Tree T >::~Tree() { delete_helper(_root); } template typename T > void Tree T >::delete_helper(TreeNode T > *node) { if (node != 0) { delete_helper(node->_left); delete_helper(node->_right); delete node; } } template typename T > void Tree T >::insert(const T &data) { insert_helper(&_root, data); } template typename T > void Tree T >::insert_helper(TreeNode T > **node, const T &data) { if (*node == 0) *node = new TreeNode T > (data); else { if ((*node)->_data > data) insert_helper(&((*node)->_left), data); else { if ((*node)->_data  data) insert_helper(&((*node)->_right), data); } } } template typename T > void Tree T >::remove(const T &data) { remove_helper(&_root, data); } template typename T > void Tree T >::remove_helper(TreeNode T > **node, const T &data) { if ((*node)->_data == data) { TreeNode T > *del_node = *node; if ((*node)->_left == 0 && (*node)->_right == 0) { *node = 0; delete del_node; } else { if ((*node)->_left == 0) { *node = (*node)->_right; delete del_node; } else { if ((*node)->_right == 0) { *node = (*node)->_left; delete del_node; } else { TreeNode T > *p = *node; TreeNode T > *i = (*node)->_left; while (i->_right != 0) { p = i; i = i->_right; } *node = i; p->_right = i->_left; i->_right = del_node->_right; i->_left = p; delete del_node; } } } } else { if ((*node)->_data > data) remove_helper(&((*node)->_left), data); else { if ((*node)->_data  data) remove_helper(&((*node)->_right), data); } } } template typename T > void Tree T >::pre_order() const { pre_order_helper(_root); } template typename T > void Tree T >::pre_order_helper(TreeNode T > *node) const { if (node != 0) { std::cout  ->_data  <" "; pre_order_helper(node->_left); pre_order_helper(node->_right); } } template typename T > void Tree T >::in_order() const { in_order_helper(_root); } template typename T > void Tree T >::in_order_helper(TreeNode T > *node) const { if (node != 0) { in_order_helper(node->_left); std::cout  ->_data  <" "; in_order_helper(node->_right); } } template typename T > void Tree T >::post_order() const { post_order_helper(_root); } template typename T > void Tree T >::post_order_helper(TreeNode T > *node) const { if (node != 0) { post_order_helper(node->_left); post_order_helper(node->_right); std::cout  ->_data  <" "; } } template typename T > int Tree T >::depth() const { return depth_helper(_root); } template typename T > int Tree T >::depth_helper(TreeNode T > *node) const { if (node->_left == 0 && node->_right == 0) return 1; else { if (node->_left == 0) return 1 + depth_helper(node->_right); else { if (node->_right == 0) return 1 + depth_helper(node->_left); else return 1 + max(depth_helper(node->_left), depth_helper(node->_right)); } } } template typename T > void Tree T >::print() const { print_helper(_root, 0); } template typename T > void Tree T >::print_helper(TreeNode T > *node, int spaces) const { while (node != 0) { print_helper(node->_right, spaces + 5); for (int i = 1; i  spaces; ++i) std::cout  <' '; std::cout  ->_data  ::endl; node = node->_left; spaces += 5; } } template typename Type > Type max(const Type &left, const Type &right) { return left > right ? left : right; } #endif

Источник