Построить арифметическое бинарное дерево

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

3.3.1. Определение. Представления бинарных деревьев

Бинарное (двоичное) дерево — особый вид дерева, в котором каждый узел имеет не более двух поддеревьев, причем в случае одного поддерева следует различать левое и правое поддерево. При изображении бинарных деревьев левого и правого сына различают по наклону соединительной линии (влево или вправо). На рис.3.4 показаны два различных бинарных дерева. Интересно отметить, что если рассматривать данные структуры как обычные упорядоченные деревья, то они являются полностью идентичными (в упорядоченном дереве единственный сын всегда первый, т. е. левый потомок). Это говорит о том, что бинарные деревья не являются частным случаем упорядоченого дерева, а представляют собой особый вид деревьев.

Рис.3.5. Два различных бинарных дерева

Приведем формальное рекурсивное определение бинарного дерева [8].

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

Обратим внимание на то, что бинарное дерево может быть пустым, в отличие от обычного дерева, которое всегда содержит хотя бы один узел (однако лес может быть пустым).

Бинарное дерево может быть представлено и в форме скобочного выражения. Аналогично обычному корневому дереву, для бинарного дерева также возможен различный порядок перечисления узлов в скобочном представлении. Например, левое скобочное представление непустого бинарного дерева рекурсивно определяется так:

Иногда при записи левое и правое поддерево разделяют запятыми, но чаще пробелом.

Левое или правое поддерево или оба вместе (для листьев) могут быть пустыми, при этом для пустых деревьев часто используется специальное обозначение . Чтобы сократить запись, в ней разрешается опустить правое поддерево, если оно пустое, а для листьев опустить оба пустых поддерева (но нельзя опускать пустое левое поддерево, иначе по такой записи нельзя будет правильно восстановить изображение бинарного дерева!). Так, деревьям, изображенным на рис.3.5, соответствуют различные левые скобочные записи в сокращенной форме:

Бинарные деревья, у которых все узлы, кроме листьев, имеют сторого по два сына, называются строго бинарными. Деревья, изображенные на рис. 3.5, не являются строго бинарными.

3.3.2. Математические свойства бинарных деревьев

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

На любом уровне n бинарное дерево может содержать от 1 до 2 n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. На рис. 3.6 дерево А содержит 8 узлов при высоте 3, в то время как дерево B содержит 5 узлов при высоте 4.

Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (e) и каждый внутренний узел имеет только одного сына. Вырожденное дерево можно считать аналогом линейного связного списка, его высота равна количеству узлов без единицы. Это максимально возможное значение для высоты бинарного дерева. В большинстве алгоритмов, использующих бинарные деревья, вырожденное дерево — наихудший случай при оценке производительности.

Рис.3.6. Бинарные деревья различной плотности

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

Наивысшей степенью плотности обладают полные бинарные деревья, которые имеют 2 k узов на каждом уровне k.

Рис.3.7. Полное и почти полное бинарные деревья

На рис. 3.7, а показано полное бинарное дерево высоты два. Обратим внимание на такие факты.

На нулевом уровне имеется 2 0 узлов, на первом — 2 1 , на втором — 2 2 и т.д. На первых k-1 уровнях количество узлов составляет

1 + 2 + 4 + . + 2 k-1 = 2 k -1

На уровне k количество узлов 2 k , т. е. ровно на один больше.

Из этого следует, что в полном бинарном дереве количество внутренних узлов на единицу меньше количества листьев. Зная количество листьев, легко определить и высоту h полного бинарного дерева:

h=log ₂ n, где n — количество листьев

h= log ₂ (N+1)-1, где N —количество узлов полного бинарного дерева.

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

Полные и почти полные бинарные деревья обладают еще одним интересным свойством — если их узлы нумеровать, начиная с единицы, сверху вниз и слева направо, то левому сыну всегда будет соответствовать код, в два раза больше кода его родителя, а правому сыну — код, на единицу больший, чем код код левого сына (рис.3.8). Номер корня всегда равен 1, его левый потомок получает номер 2, правый — номер 3. Левый потомок узла 2 получит номер 4, а правый — 5, левый потомок узла 3 получит номер 6, правый — 7 и т.д. Такая схема нумерации используется при представлении деревьев с помощью массивов. К этой теме мы еще вернемся.

Рис.3.8. Нумерация узлов полного или почти полного бинарного дерева

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

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

Источник

4.4.4. Представление выражений с помощью деревьев

С помощью деревьев можно представлять произвольные арифметические выражения. Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу — операция. В общем случае дерево при этом может оказаться не бинарным.

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

Рис.4.16. Представление арифметического выражения произвольного вида в виде дерева.

Рис. 4.17. Представление арифметического выражения в виде бинарного дерева

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

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

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

Рис.4.18. Вычисление арифметического выражения с помощью бинарного дерева

Рис. 4.19. Представление логического выражения в виде бинарного дерева

4.5. Представление сильноветвящихся деревьев

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

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

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

Рис.4.20. Представление сильноветвящихся деревьев в виде списков

4.6. Применение сильноветвящихся деревьев

Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе MS Dos корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью — непустым каталогам.

Рис.4.21. Представление логической структуры каталогов и файлов в виде сильноветвящегося дерева.

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

Для облегчения этой задачи сделаем списки потомков двунаправленными. Для этого достаточно ввести дополнительный указатель на предыдущий узел «last». С целью упрощения перемещения по дереву от листьев к корню введем дополнительный указатель на предок текущего узла «up». Общими с традиционными способами представления являются указатели на список потомков узла «down» и следующий узел «next».

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

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Построение бинарного дерева для простого арифметического выражения

NovozhilovAY/Arithmetic-Expression-Binary-Tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Построение бинарного дерева для простого арифметического выражения

Бинарное дерево является одним из вариантов хранения арифметического выражения. Листья такого дерева содержат операнды, а внутренние вершины и корень – знаки операций.

В разработанной программе введены следующие ограничения:

• В выражении могут присутствовать только однозначные целые числа
• Рассматриваются операции: +, — ,* , /
• Выражение не содержит скобок и унарных знаков (например, выражение -6+5, следует писать в виде 0-6+5).
• Предполагается, что выражение записано верно

About

Построение бинарного дерева для простого арифметического выражения

Источник