Interested Article - Двоичное дерево

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

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

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

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

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

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

Например, показанное справа на рис. 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 .

Применение

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

Примечания

  1. kvodo.ru. Дата обращения: 1 марта 2019. 2 марта 2019 года.
  2. . Дата обращения: 1 марта 2019. 2 марта 2019 года.
  3. . algolist.manual.ru. Дата обращения: 1 марта 2019. 14 июля 2019 года.

Ссылки

Источник —

Same as Двоичное дерево