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