Двоичное дерево.

Двоичное дерево – вид связного ациклического (не имеющего циклов) графа, характерный тем, что у каждого из его узлов имеется не более двух потомков (связанных узлов, находящихся иерархически ниже).

Определения следующего абзаца не относятся непосредственно к двоичным деревьям, а скорее к деревьям вообще, поэтому тем, у кого не возникает проблем с понятиями можно перейти к следующему абзацу.

В двоичном дереве есть только один узел, у которого нет предка, он называется корнем. Конечные узлы – листья. Если у корня отсутствует предок, то у листьев – потомки. Все вершины помимо корня и листьев называются узлами ветвления. Длина пути от корня до узла определяет уровень этого самого узла. Уровень корня дерева всегда равен нулю, а уровень всех его потомков определяется удаленностью от него. Например, узлы F и L (рис. ниже) расположены на первом уровне, а U и B – на третьем.

Связный граф является деревом тогда и только тогда, когда PA=1, где P – количество вершин в графе, а A – количество ребер, поскольку в любом дереве с n вершинами, должно быть n-1 ребро. Это справедливо и для бинарного дерева, так как оно входит в класс деревьев. А увидеть отличительные признаки бинарного дерева, можно просто зная его определение. Достаточно взглянуть на рисунок 1, чтобы понять является ли изображенный на нем граф бинарным деревом.

Во-первых, он связный и не имеет ни одного цикла (следовательно, имеем дело с деревом), во-вторых из каждого узла исходит не больше двух ребер (если бы граф был неориентированным, то допускалось три исходящих ребра), что указывает на главный признак двоичного дерева. Но существует и немного другой способ проверить является ли дерево бинарным. Составим список, в левом столбце которого будут содержаться номера уровней, а в правом – число вершин, лежащих на каждом из них:

Уровень

Количество вершин

0

1

1

2

2

3

3

2

Обозначим уровень символом k, а количество вершин n, тогда для бинарного дерева будет справедливо равенство n2k, т. е. количество вершин на k-ом уровне не может иметь значение большее, чем степень двойки этого уровня. Для доказательства этого достаточно построить полное дерево, все уровни которого содержат максимально возможное для двоичного дерева количество вершин:

Продолжая построение, будем получать на каждом новом уровне число вершин равное k-ой степени двойки, а их общее количество вычисляется по формуле:Для рисунка 2 формула раскрывается так: 20+21+22+23=15.

Операция, при которой вершины дерева поочередно просматриваются и каждая только один раз, называется обходом дерева. Выделяют четыре основных метода обхода:

  • обход в ширину;
  • прямой обход;
  • обратный обход;
  • симметричный обход;

Обход в ширину – это поуровневая обработка узлов слева на право. Работа метода заключается в просмотре всех вершин, начиная с некоторой вершины на n-ом уровне.

Возьмем нулевой уровень за начальный (рис. 2), и, начиная с вершины K, будем методом обхода в ширину поочередно двигаться вниз, просматривая вершины в следующем порядке: K A X T N H Q F U P L B J V Y.

Обход в прямом порядке вначале предполагает обработку узлов предков, а потом их потомков, то есть сначала посещается вершина дерева, далее левое и правое поддеревья, именно в описанном порядке. Для нашего дерева последовательность прямого обхода такая: K A T F U N P L X H B J Q V Y.

Обход в обратном порядке противоположен прямому обходу. Первыми осматриваются потомки, а уже затем предки, иначе говоря, первоначально обращение идет к элементам нижних уровней левого поддерева, потом то же самое с элементами правого, и в конце осматривается корень. Обратный обход дерева с рисунка 2: F U T P L N A B J H V Y Q X K.

Обход в симметричном порядке заключается в посещении левого узла, перехода в корень и оттуда в правый узел. Все для того же дерева узлы будут осмотрены в следующем порядке: F T U A P N L K B H J X V Q Y.

На практике используются не просто бинарные деревья, а их частные случаи, например, такие как двоичное дерево поиска, АВЛ-дерево, двоичная куча и другие.

Рейтинг
( Пока оценок нет )
Загрузка ...