2018-01-08
1238
Древовидная структура характеризуется множеством узлов (nodes), происходящих от единственного начального узла, называемого корнем (root). На Рис. 3 корнем является узел А. В терминах генеалогического дерева узел можно считать родителем (parent), указывающим на 0, 1 или более узлов, называемых сыновьями (children). Например, узел В является родителем сыновей E и F. Родитель узла H - узел D. Дерево может представлять несколько поколений семьи. Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители – предками (ancestors) этого узла. Например, узлы E, F, I, J – потомки узла B. Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0 или более сыновей. Узел, не имеющий детей (E, G, H, I, J), называется листом (leaf).
Каждый узел дерева является корнем поддерева (subtree), которое определяется данным узлом и всеми потомками этого узла. Узел F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Это определение позволяет говорить, что узел A есть корень поддерева, которое само оказывается деревом.
Рис.3.
Переход от родительского узла к дочернему и к другим потомкам осуществляется вдоль пути (path). Например, на Рис. 4 путь от корня A к узлу F проходит от A к B и от B к F. Тот факт, что каждый некорневой узел имеет единственного родителя, гарантирует, что существует единственный путь из любого узла к его потомкам. Длина пути от корня к этому узлу есть уровень узла. Уровень корня равен 0. Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-го уровня и т.д. Например, на Рис. 4 узел F является узлом 2-го уровня с длиной пути 2.
Глубина (depth) дерева есть его максимальный уровень. Понятие глубины также может быть описано в терминах пути. Глубина дерева есть длина самого длинного пути от корня до узла. На Рис. 4 глубина дерева равна 3.
Рис.4. Уровень узла и длина пути
Бинарные деревья
Хотя деревья общего вида достаточно важны, мы сосредоточимся на ограниченном классе деревьев, где каждый родитель имеет не более двух сыновей (Рис. 5). Такие бинарные деревья (binary trees) имеют унифицированную структуру, допускающую разнообразные алгоритмы прохождения и эффективный доступ к элементам. Изучение бинарных деревьев дает возможность решать наиболее общие задачи, связанные с деревьями, поскольку любое дерево общего вида можно представить эквивалентным ему бинарным деревом.
У каждого узла бинарного дерева может быть 0, 1 или 2 сына. По отношению к узлу слева будем употреблять термин левый сын (left child), а по отношению к узлу справа – правый сын (right child). Наименования "левый" и "правый" относятся к графическому представлению дерева. Бинарное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, называемых левым и правым поддеревьями соответственно. Таким образом, процедуры обработки деревьев рекурсивны. Вот рекурсивное определение бинарного дерева:
Бинарное дерево - это такое множество узлов B, что
а) B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);
б) B разбивается на три непересекающихся подмножества:
· {R} корневой узел
· {L1, L2,..., Lm} левое поддерево R
· {R1, R2,..., Rm} правое поддерево R
На любом уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. Интуитивно плотность есть мера величины дерева (число узлов) по отношению к глубине дерева. На Рис. 5 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына. Вырожденное дерево эквивалентно связанному списку.
Рис.5. Бинарные деревья
Деревья с большой плотностью очень важны в качестве структур данных, так как они содержат пропорционально больше элементов вблизи корня, т.е. с более короткими путями от корня. Плотное дерево позволяет хранить большие коллекции данных и осуществлять эффективный доступ к элементам. Быстрый поиск – главное, что обусловливает использование деревьев для хранения данных.
Вырожденные деревья являются крайней мерой плотности. Другая крайность – законченные бинарные деревья (complete binary tree) глубины N, где каждый уровень 0...N - 1 имеет полный набор узлов, и все листья уровня N расположены слева. Законченное бинарное дерево, содержащее 2N узлов на уровне N, является полным. На Рис. 6 показаны законченное и полное бинарные деревья.
Законченные и полные бинарные деревья дают интересные математические факты. На нулевом уровне имеется 20 узлов, на первом — 21, на втором — 22 и т.д. На первых k-1 уровнях имеется 2k-1 узлов.
1 + 2 + 4 +... + 2k-1 = 2k-1На уровне k количество дополнительных узлов колеблется от 1 до 2k (полное). В полном дереве число узлов равно
1 + 2 + 4 +... + 2k-1 + 2k = 2k-1 - 1Число узлов законченного бинарного дерева удовлетворяет неравенству
2k < N < 2k-1 - 1 < 2k-1Решая его относительно k, имеем
k < log2 (N) < k+1Например, полное дерево глубины 3 имеет
24 - 1 = 15 узлов
Рис.6. Классификация бинарных деревьев
11. Обходы бинарных деревьев (КЛП - "Корень-Левое-Правое",ЛКП,ЛПК) с примерами программной реализации.
1. Обход бинарного дерева в прямом порядке:
а) Обработать корень (например, вывести в выходную последовательность его имя);
b) Обойти левое поддерево корня в прямом порядке;
c) Обойти правое поддерево корня в прямом порядке.
Обход приведённого бинарного дерева в прямом порядке даст: ABCDEFGH.
2. Обход бинарного дерева в обратном порядке:
a) Обойти левое поддерево корня в обратном порядке;
b) Обработать корень;
c) Обойти правое поддерево корня в обратном порядке.
Обход приведённого бинарного дерева в обратном порядке даст: CBEDAGFH.
3. Обход в бинарного дерева в концевом порядке:
а) Обойти левое поддерево корня в концевом порядке;
b) Обойти правое поддерево корня в концевом порядке.
c) Обработать корень;
Обход приведённого бинарного дерева в концевом порядке даст: CEDBGHFA.
Следует обратить внимание на то, что при обходе бинарного дерева в прямом порядке, любая его вершина, рассматриваемая как корень, посещается перед обходом поддеревьев этого корня, а при концевом порядке – после.
В случае же обратного обхода бинарного дерева, корень любого его поддерева (и самого этого дерева в целом) посещается непосредственно после обхода левого поддерева и перед обходом правого поддерева этого корня.
Помимо указанных трёх основных порядков обхода, на практике иногда применяется ещё один – поуровневый обход (обход вширину) бинарного дерева, при котором вершины бинарного дерева начиная с корня перечисляются последовательно слева направо, уровень за уровнем.
Для нашего примера указанный порядок обхода даст последовательность: ABFCDGHE.
Необходимые для программной обработки бинарных деревьев операции их ввода-вывода, требуют возможности строчного представления бинарных деревьев в форме последовательности знаков.
Одним из простых способов такого представления является скобочная запись бинарных деревьев, суть которой ясна из следующей кодировки бинарного дерева рис.1:
(((*С*) B ((*E*)D*)) A ((*G*)F(*H*)))
В приведённой выше записи, знаком '*’ обозначены пустые поддеревья, и для лучшей читабельности, добавлены лишние пробелы.
