Поиск вершины

Выполнение операций с двоичными деревьями

Двоичные деревья

Двоичное дерево – дерево со степенью два.

Для построения дерева используется следующий типовой элемент:

код вершины

указатель на левого потомка

указатель на правого потомка

Наиболее широкое распространение получило двоичное упорядоченное дерево, оно имеет упорядоченность вершин.

Для каждой вершины выполняется правило: код текущей вершины больше всех вершин левого поддерева (ЛП) и меньше всех кодов вершин правого поддерева (ПП).

Пример:

Алгоритм поиска

k – код вершины;

р – указатель на текущую вершину;

х – код текущей вершины;

t – указатель на корень дерева.

1. p присвоить значение t.

2. Если р – пустой указатель, то вершина отсутствует, переход к п.5.

3. Значение кода текущей вершины сравнивается с искомым кодом:

а) k = x, вершина найдена, переход к п.5;

б) k < x, указатель на левое поддерево;

в) k > x, указатель на левое поддерево.

Пример

Дата добавления: 2014-01-15