Двоичное дерево: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Метки: с мобильного устройства из мобильной версии
уточнение
Строка 1: Строка 1:
'''Двои́чное де́рево''' — иерархическая [[структура данных]], в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным [[Дерево (теория графов)|ориентированным деревом]].<ref>{{Cite web|url=http://kvodo.ru/binary-tree.html|title=Двоичное дерево.|publisher=kvodo.ru|accessdate=2019-03-01}}</ref>
'''Двои́чное де́рево''' — иерархическая [[структура данных]], в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным [[Дерево (теория графов)|ориентированным деревом]].<ref>{{Cite web|url=http://kvodo.ru/binary-tree.html|title=Двоичное дерево.|publisher=kvodo.ru|accessdate=2019-03-01}}</ref>


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


== Рекурсивное определение ==
== Рекурсивное определение ==
Строка 19: Строка 19:
(e
(e
(c
(c
(a nil nil)
(a null null)
nil
null
)
)
(g
(g
nil
null
(k nil nil)
(k null null)
)
)
)
)
(s
(s
(p (o nil nil) (s nil nil) )
(p (o null null) (s null null) )
(y nil nil)
(y null null)
)
)
)
)
Строка 48: Строка 48:
* [[Дерево Фибоначчи]]
* [[Дерево Фибоначчи]]
* [[Суффиксное дерево]]
* [[Суффиксное дерево]]

<br />


== Примечания ==
== Примечания ==
{{примечания}}
<references />


== Ссылки ==
== Ссылки ==

{{Навигация}}
{{Навигация}}


Версия от 12:38, 13 апреля 2021

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

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

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

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

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

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

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

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

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

Применение

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

Примечания

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

Ссылки

Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Двоичное_дерево&oldid=113575406