WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом.[1]

Для практических целей обычно используют два подвида двоичных деревьев — двоичное дерево поиска и двоичная куча.

Рекурсивное определение

Существует следующее рекурсивное определение двоичного дерева (см. БНФ):

<дерево> ::= ( <данные> <дерево> <дерево> ) | nil .

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или конечным (терминальным) узлом.[2]

Например, показанное справа на рис. 1 дерево согласно этой грамматике можно было бы записать так:

 (m 
    (e 
        (c 
            (a nil nil)
            nil
        )
        (g 
            nil
            (k nil nil)
        )
     )
     (s
        (p (o nil nil) (s nil nil) )
        (y nil nil)
     )
 )
Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.

Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины m = (data, left, right) есть два потомка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.[3]

Применение

Многие полезные структуры данных основаны на двоичном дереве:


Примечания

  1. ↑ Двоичное дерево.. kvodo.ru. Проверено 1 марта 2019.
  2. ↑ Дерево. Проверено 1 марта 2019.
  3. ↑ Двоичные деревья поиска: начальные сведения. algolist.manual.ru. Проверено 1 марта 2019.

Ссылки

commons: Двоичное дерево на Викискладе

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

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

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии