Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Бинарное дерево
|
|
Важной разновидностью корневых деревьев является класс бинарных деревьев. В бинарных деревьях каждая вершина может иметь не более двух сыновей.
В рекурсивном определении бинарное дерево состоит из корня и двух бинарных поддеревьев – левого и правого, причем любое из них сожжет быть пустым, то есть 
.
Несмотря на иерархическую структуру бинарные деревья не являются подмножеством упорядоченных корневых деревьев.
Пример
a a a
b b b
различные бинарные деревья эквивалентное упорядоченное
Приведенные примеры двух бинарных деревьев различны по структуре. Корень первого из них имеет только левое поддерево. Корень второго из них имеет только правое поддерево.
В общем случае различие между корневым деревом и бинарным состоит в том, что каждая вершин корневого дерева может иметь произвольное число поддеревьев, в то время как вершина бинарного дерева может иметь 0, 1 или 2 поддерева. Кроме того, у бинарных деревьев существуют различия между правым и левым поддеревьями.
Несмотря на эти различия, бинарные деревья могут быть использованы для представления корневых деревьев.
Возможность такого представления устанавливает следующее естественное соответствие между корневыми и бинарными деревьями.
Левая ветвь каждой вершины соединяет его с первой вершиной следующего уровня, а правая с другими вершинами следующего уровня (со всеми братьями).
Пример
Преобразуем 4-х уровневое корневое дерево в бинарное
1 1
2 3 4 2 3 4
5 8 9
5 6 7 8 9 6 7
Организация данных с помощью бинарных деревьев позволяет сократить время обработки данных.
|
|