Бинарные деревья

Бинарное (двоичное) дерево - это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков.

Обход бинарного дерева

Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется обходом дерево.

Есть 3 вида обхода по дереву:

• Прямой (pre-order walr) - сначала посещается корень дерева и, затем в прямом порядке вершины поддерева 1 (BDE), далее вершины поддерева 2 (C) и т.д.;
• Симметричный - сначала в симметричном порядке посещаются вершины поддерева 1, далее корень поддерева, затем последовательно в симметричном порядке вершины поддеревьев.
• Обратный (post order walk) - от вершины поддерева 1 (BDE), далее последовательно в обратном порядке посещаются вершины поддеревьев.

Степени вершин бинарного дерева

Степень вершины - это количество ребер, инцидентных к этой вершине.

Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:

• информационное поле (ключ вершины);
• служебное поле;
• указатель на левое поддерево;
• указатель на правое поддерево.

По степени вершин бинарные деревья делятся:

• Строгие - вершины дерева имеют степень нуль (у листьев) или два (у внутренних узлов);
• Нестрогие - вершины дерева имеют степень нуль (у лисьтев), один или два (у узлов).
• Полные - в котором все уровни заполнены, кроме, возможно последнего, который заполняется слева направо;
• Неполные - дерево, в котором нарушен порядок заполнения или есть пропуски на уровнях.