Бинарные деревья

Определение:

Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.


Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.

Узел дерева, не имеющий потомков, называется листом.

Схематичное изображение бинарного дерева:
Бинарное дерево

Бинарное дерево может представлять собой пустое множество, и может выродиться в список. Вырожденное бинарное дерево:
Вырожденное бинарное дерево


Операции над бинарными деревьями

Бинарное дерево должно реализовывать следующие операции:
  1. ?нициализация бинарного дерева:
    текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.

  2. Помещение в бинарное дерево элемента:
    для нового элемента в бинарном дереве создается соответствующий узел, указатели на потомков которого пусты (поиск позиции для такого узла начинается с корня и проходит согласно правилам, определяющим структуру бинарного дерева).

  3. Получение значения текущего элемента

  4. Поиск заданного элемента:
    если искомый элемент находится в дереве, то возвращается указатель на него, в противном случае возвращается nil, сигнализирующий о неуспехе поиска значения

  5. Удаление узла из дерева

  6. Уничтожение бинарного дерева

ComentariiReinoieste comentariile

Logare

Utilizator:
Parola:
Retine-ma
Inregistrare