Рекурсивный поиск значения в двоичном дереве поиска Паскаля

Delphi , Синтаксис , Деревья

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

Прежде чем мы начнем, давайте определим типы данных, которые мы будем использовать для представления узлов дерева и списка. Определим типы данных text, list, nodeL, tree и nodeT:

program BinarySearchTree;

type
  text = string[30];
  list = ^nodeL;
  nodeL = record
    title: text;
    ISBN: text;
    next: list;
  end;
  tree = ^nodeT;
  nodeT = record
    cod: text;
    l: list;
    LC: tree;
    RC: tree;
  end;

Теперь, когда типы данных определены, давайте создадим функцию поиска, которая будет принимать значение для поиска и корень дерева в качестве аргументов и возвращать булево значение, указывающее, найдено ли значение в дереве или нет.

Вот как может выглядеть функция поиска:

function Search(value: text; node: tree): boolean;
begin
  if node = nil then
    exit(false);

  if value = node^.cod then
    exit(true);

  if value < node^.cod then
    exit(Search(value, node^.LC))
  else
    exit(Search(value, node^.RC))
end;

Функция Search работает следующим образом:

1. Если узел равен nil, то значение не найдено в дереве, и функция возвращает false.
2. Если значение, которое мы ищем, равно значению в текущем узле, то значение найдено, и функция возвращает true.
3. Если значение, которое мы ищем, меньше значения в текущем узле, то мы рекурсивно вызываем функцию Search для левого поддерева.
4. Если значение, которое мы ищем, больше значения в текущем узле, то мы рекурсивно вызываем функцию Search для правого поддерева.

Теперь, чтобы использовать функцию Search, нам нужно создать дерево и добавить в него элементы. Вот пример кода, который создает дерево и добавляет в него несколько элементов:

var
  root: tree;

begin
  root := nil;

  root := Add(root, 'B001');
  root := Add(root, 'B002');
  root := Add(root, 'B003');
  root := Add(root, 'B004');
  root := Add(root, 'B005');

  if Search('B003', root) then
    writeln('Found')
  else
    writeln('Not Found');
end;

Функция Add добавляет элемент в дерево и возвращает корень дерева. В данном примере мы добавляем пять элементов в дерево и выполняем поиск элемента с значением 'B003'. Если элемент найден, то выводится сообщение 'Found', в противном случае выводится сообщение 'Not Found'.

Примечание: Функция Add не показана в данном руководстве, но она необходима для добавления элементов в дерево. Ее можно реализовать, используя подход, аналогичный функции Search.

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

Создано по материалам из источника по ссылке.

В этом контексте рассматривается рекурсивный поиск значения в двоичном дереве поиска, реализованный на языке программирования Паскаль.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Деревья ::