Главная » Java, Структуры данных и алгоритмы » Дерево Терминология и основные свойства

0

Дерево (tree) Т — это набор узлов (node), хранящих элементы, состоящие в отношениях «отцы и дети», со следующими свойствами:

•                       Гимеет особый узел г, называемый корнем данного древа (root of Т)\

•                       каждый узел v этого Г, отличный от г, имеет родительский узел и.

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

Если узел и является родителем (parent) узла v, то можно говорить, что v является дочерним (child) узлом и. Два узла, выступающие дочерними элементами по отношению к одному и тому же родителю, будут называться сестрами/братьями (siblings). Узлы, содержащие в себе один и более дочерних элементов, называются составными (internal), а не имеющие их — простыми (external). Простые узлы также известны как листья (leaves). Ответвление (subtree) от дерева, корнем которого является узел v, само является деревом, состоящим из потомков (descendent) v, включая сам узел v. Предком (ancestor) узла может быть либо родительский узел, либо предок родителя этого узла. И наоборот, можно сказать, что v является потомком узла w, если и является предком v. К примеру, на рис. 6.2 «Отдел сбыта» выступает предком «Европы», а «Европа» — потомком «Отдела сбыта».

Пример 6.1. Отношения наследования между классами в Java-npo- граммах построены в виде дерева. Класс java.lang.Object является исходным классом (предком) для всех остальных классов.

Пример 6.2. В большинстве операционных систем файлы организованы иерархически в виде вложенных директорий[13] (называемых также папками) и представляются пользователю в форме дерева (рис. 6.3). Если быть более точным, то составные узлы дерева ассоциируются с директориями, а простые — с обычными файлами. В операционной системе UNIX корень дерева вполне закономерно называется «корневой директорией» и представляется символом «/.». Корневая директория является исходной директорией (предком) для всех директорий и файлов в файловой системе UNIX.

Дерево является упорядоченным (ordered), если дочерние элементы каждого из узлов упорядочены, то есть каждый из элементов можно определить как первый, второй, третий и т.д. Такой способ расположения определяется принципом использования и обычно отображается на схеме дерева путем размещения «братьев» слева направо, в зависимости от их линейных отношений. Упорядоченные деревья обычно указывают на линейный тип отношений между дочерними элементами, расставляя их в списке согласно определенным требованиям.

Пример 6.3. Структурированный элемент (например, книга) имеет иерархическую древовидную структуру, в которой составными узлами выступают главы, разделы и подразделы, а простыми узлами — параграфы, таблицы, рисунки, раздел библиографии и тому подобное (см. рис. 6.4). Корень дерева представлен самой книгой. В принципе, это дерево можно еще более

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

Рис. 6.3. Представление раздела файловой системы. Заметьте, что ответвление • cs016/ содержит 10 узлов

 

Бинарным деревом (binary tree) называется упорядоченное дерево, в котором каждый из узлов имеет максимум два дочерних элемента. Бинарное дерево считается правильным (proper), если каждый узел не содержит ни одного или содержит два дочерних элемента. Таким образом, в правильном бинарном дереве каждый составной узел имеет двё дочерних элемента. Дочерние элементы в таких узлах имеют маркировку «правый» и «левый» (left child и right child). И выстраиваются эти элементы таким образом, что левый стоит перед правым. Ответвление, берущее начало из левого или правого элемента составного узла v, будет называться соответственно левым или правым ответвлением (left subtree и right subtree) узла v. В книге любое бинарнре дерево будем считать правильным, если не имеется особой оговорки. Естественно, даже неправильное бинарное дерево остается деревом в обычном понимании при условии, что каждый составной узел имеет не более двух дочерних элементов.

Существует несколько способов применения структуры бинарных деревьев. В нижеприведенных примерах рассмотрены два из них.

Пример 6.4. Часто используемым способом применения бинарного дерева является представление с его помощью выходных структур, получаемых в результате ответов «да-нет» на общие вопросы. Каждый из составных узлов соответствует вопросу. Начиная с корня, переходим к правому или левому дочернему элементу в зависимости от выбранного ответа — да или нет. Подобная структура известна как «дерево решений», так как каждый простой узел v в этом дереве представляет собой решение, соответствующее ответам на вопросы, ассоциируемые с предками v, если они даны в том порядке, который ведет к v. Рис. 6.5 иллюстрирует

Рис. 6.5. Бинарное дерево решений с советами по инвестициям

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

Пример 6.5. Арифметическое выражение может быть представлено деревом, простые узлы которого соответствуют переменным (variable) или постоянным (constant), а составные узлы — одному из операторов «+», «-», «х» и «/» (рис. 6.6). Каждый из узлов дерева имеет ассоциируемое с ним значение.

•            Если узел простой, то его значение либо переменная, либо константа.

•          Если узел составной, то его значение определяется исходя из операции, выполненной над его дочерними элементами.

Такое дерево арифметического выражения является правильным бинарным деревом, поскольку каждый из операторов имеет ровно два операнда. Естественно, если разрешены унарные операции типа отрицаний (-), как в «-х», то бинарное дерево будет неправильным.

Рис. 6.6. Бинарное дерево, представляющее арифметическое выражение. В дереве представлено выражение ((((3 + 1) х 3) / (9 – 5) + 2)) – ((3 х (7 – 4)) + 6). Значение, ассоциируемое с составным узлом, отмеченным «/», равно 2

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии