Реализация двоичного дерева поиска
В ссылочных реализациях структур данных данные хранятся в виде отдельных элементов, связанных между собой указателями. Элементы организованы либо в виде последовательности (списка), либо в виде дерева. Рассмотрим организацию ссылочной структуры данных на основе двоичного дерева поиска.
В двоичном дереве поиска хранятся элементы, которые можно сравнивать между собой при помощи операций «меньше» и «больше», например, это могут быть числа или строки.
Все элементы, которые хранятся в дереве — уникальные, то есть одно число не может быть записано в двух вершинах дерева. У каждой вершины дерева есть два поддерева — левое и правое (они могут быть и пустыми), причем в левом поддереве все элементы меньше значения, записанного в данной вершине, а в правом поддереве — больше.
Пример правильно построенного двоичного дерева поиска:
Благодаря такому представлению, все операции с деревом (поиск элемента, добавление элемента, удаление элемента) выполняются за время, пропорциональное высоте дерева, а не его размеру. Это позволяет (используя специальные алгоритмы балансировки дерева) реализовать эффективные структуры данных типа «множество», в которых все операции осуществляются за $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;
>
Источник
Дерево
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .
Способ представления бинарного дерева:
Корень дерева расположен на уровне с минимальным значением.
Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .
Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
Остальные элементы – внутренние узлы (узлы ветвления).
Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.
Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .
Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
Имеется много задач, которые можно выполнять на дереве.
Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
Способы обхода дерева
Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.
Существует три способа обхода дерева:
- Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
- Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
- Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева
Узел дерева можно описать как структуру:
struct tnode <
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
При этом обход дерева в префиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
cout field; //Отображаем корень дерева
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в инфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
cout field; //Отображаем корень дерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в постфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
cout field; //Отображаем корень дерева
>
>
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
struct tnode * addnode( int x, tnode *tree) <
if (tree == NULL ) < // Если дерева нет, то формируем корень
tree = new tnode; // память под узел
tree->field = x; // поле данных
tree->left = NULL ;
tree->right = NULL ; // ветви инициализируем пустотой
> else if (x < tree->field) // условие добавление левого потомка
tree->left = addnode(x,tree->left);
else // условие добавление правого потомка
tree->right = addnode(x,tree->right);
return (tree);
>
Удаление поддерева
void freemem(tnode *tree) <
if (tree!= NULL ) <
freemem(tree->left);
freemem(tree->right);
delete tree;
>
>
Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.
Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно.
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.
В дереве каждый узел содержит:
- указатель на текст слова;
- счетчик числа встречаемости;
- указатель на левого потомка;
- указатель на правого потомка.
Рассмотрим выполнение программы на примере фразы
now is the time for all good men to come to the aid of their party
При этом дерево будет иметь следующий вид
#include
#include
#include
#include
//#include
#define MAX WORD 100
struct tnode < // узел дерева
char * word; // указатель на строку (слово)
int count; // число вхождений
struct tnode* left; // левый потомок
struct tnode* right; // правый потомок
>;
// Функция добавления узла к дереву
struct tnode* addtree( struct tnode* p, char * w) int cond;
if (p == NULL ) p = ( struct tnode*)malloc( sizeof ( struct tnode));
p->word = _strdup(w);
p->count = 1;
p->left = p->right = NULL ;
>
else if ((cond = strcmp(w, p->word)) == 0)
p->count++;
else if (cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
>
// Функция удаления поддерева
void freemem(tnode* tree) if (tree != NULL ) freemem(tree->left);
freemem(tree->right);
free(tree->word);
free(tree);
>
>
// Функция вывода дерева
void treeprint( struct tnode* p) if (p != NULL ) treeprint(p->left);
printf( «%d %s\n» , p->count, p->word);
treeprint(p->right);
>
>
int main() struct tnode* root;
char word[MAX WORD ];
root = NULL ;
do scanf_s( «%s» , word, MAX WORD );
if (isalpha(word[0]))
root = addtree(root, word);
> while (word[0] != ‘0’ ); // условие выхода – ввод символа ‘0’
treeprint(root);
freemem(root);
getchar();
getchar();
return 0;
>
Результат выполнения
Комментариев к записи: 19
Источник