Logare

Utilizator:
Parola:

Inregistrare

Ultimele noutăţi

25 de ani de la fondare
În ziua de 21 noiembrie la ora 12 00 în sala de festivităţi sunt invitaţi toţi doritorii la sărbătoarea "25 de ani de la fondarea colegiului". Aşteptăm cu drag toţi absolvenţii colegiului, colegi de ramură, oaspeţi şi părinţi...

Бинарные деревья
Inapoi la lista cursurilor

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

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


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

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

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

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


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

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

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

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

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

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

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

ComentariiReinoieste comentariile

Logare

Utilizator:
Parola:
Retine-ma
Inregistrare
Twitter   facebook facebook Mail.ru