Как найти количество вершин в дереве – Сайт, где вы сможете решить свои вопросы

Пример. Напишем предикат, подсчитывающий общее количество вершин дерева. У него будет два параметра. Первый (входной) параметр – дерево, второй (выходной) – количество вершин в дереве.

Как всегда, пользуемся рекурсией. Базис: в пустом дереве количество вершин равно нулю. Шаг рекурсии: чтобы посчитать количество вершин дерева, нужно посчитать количество вершин в левом и правом поддереве, сложить полученные числа и добавить к результату единицу (посчитать корень дерева ).

Пишем:

tree_length (empty,0). /* В пустом дереве
                  нет вершин */
tree_length(tr(_,L,R),N):-
        tree_length (L,N1), 
            /* N1 - число вершин 
             левого поддерева */
        tree_length (R,N2), 
            /* N2 - число вершин 
             правого поддерева */
        N=N1+N2+1. /* число вершин 
              исходного дерева 
              получается сложением 
              N1, N2 и единицы */

Пример. Решим еще одну подобную задачу. Разработаем предикат, подсчитывающий не общее количество вершин дерева, а только количество листьев, т.е. вершин, не имеющих сыновей. Предикат будет иметь два параметра. Входной – исходное дерево, выходной – количество листьев дерева, находящегося в первом параметре.

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

Запишем:

tree_leaves(empty,0). /* в пустом дереве
                  листьев нет */
tree_leaves(tr(_,empty,empty),1):-!. 
          /* в дереве с одним корнем - 
            один лист */
tree_leaves(tr(_,L,R),N):-
        tree_leaves(L,N1), 
          /* N1 - количество листьев 
            в левом поддереве */
        tree_leaves(R,N2), 
          /* N2 - количество листьев 
            в правом поддереве */
        N=N1+N2.

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

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

На Прологе это записывается следующим образом:

tree_sum (empty,0). /* В пустом дереве
                  вершин нет */
tree_sum(tr(X,L,R),N):-
       tree_sum (L,N1), 
           /* N1 - сумма элементов 
            левого поддерева */
       tree_sum (R,N2), 
           /* N2 - сумма элементов 
            правого поддерева */
       N=N1+N2+X. /* складываем N1, N2 
             и корневое значение */

Пример. Создадим предикат, позволяющий вычислить высоту дерева. Напомним, что высота дерева – это наибольшая длина пути от корня дерева до его листа. Предикат будет иметь два параметра. Первый (входной) – дерево, второй (выходной) – высота дерева, помещенного в первый параметр.

Базис рекурсии будет основан на том, что высота пустого дерева равна нулю. Шаг рекурсии – на том, что для подсчета высоты всего дерева нужно найти высоты левого и правого поддеревьев, взять их максимум и добавить единицу (учесть уровень, на котором находится корень дерева ). Предикат max (или max2 ), вычисляющий максимум из двух элементов, был разработан нами еще в третьей лекции. Мы воспользуемся им при вычислении высоты дерева.

Получается следующее.

tree_height(empty,0). /* Высота пустого 
          дерева равна нулю */
tree_height(tr(_,L,R),D) :- 
        tree_height(L,D1), 
         /* D1 - высота левого 
               поддерева */ 
        tree_height(R,D2), 
         /* D2 - высота правого
               поддерева */
        max(D1,D2,D_M), 
         /* D_M - максимум из высот 
          левого и правого поддеревьев */
        D=D_M+1. 
         /* D - высота дерева получается 
          путем увеличения числа D_M 
          на единицу*/

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

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

Модифицированный предикат будет выглядеть следующим образом:

tree_member2(X,tr(X,_,_)):-!. /* X - корень
                   дерева */
tree_member2(X,tr(K,L,_)):-
        X<K,!,
        tree_member2(X,L). 
           /* X - принадлежит 
            левому поддереву */
tree_member2(X,tr(K,_,R)):-
        X>K,!,
        tree_member2(X,R). 
           /* X - принадлежит 
            правому поддереву */

Источник

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

Дерево — это связный ациклический граф.^[1] Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.

Лес — множество деревьев.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.^[2]

Связанные определения[править | править код]

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

Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги).

Узел ветвления — неконцевой узел.

Дерево с отмеченной вершиной называется корневым деревом.

Уровень узла — длина пути от корня до узла. Можно определить рекурсивно:

уровень корня дерева $T$ равен 0;
уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева $T$ , содержащего данный узел.

Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

Несводимым называется дерево, в котором нет вершин степени 2.

Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
Центроид — вершина, при удалении которой размеры получившихся компонент связности не превышают ${displaystyle {dfrac {n}{2}}}$ (половины размера исходного дерева)

Двоичное дерево[править | править код]

Простое бинарное дерево размера 9 и высоты 3, с корнем значения 2. Это дерево не сбалансировано и не отсортировано.

Термин двоичное дерево (применяется так же термин бинарное дерево) имеет несколько значений:

Неориентированное дерево, в котором степени вершин не превосходят 3.
Ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.
Абстрактная структура данных, используемая в программировании. На двоичном дереве основаны такие структуры данных, как двоичное дерево поиска, двоичная куча, красно-чёрное дерево, АВЛ-дерево, фибоначчиева куча и др.

N-арные деревья[править | править код]

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

N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

Свойства[править | править код]

Подсчёт деревьев[править | править код]

$T(z)=sum _{n=1}^{infty }T_{n}z^{n}$

для числа $T_{n}$ неизоморфных корневых деревьев с $n$ вершинами удовлетворяет функциональному уравнению

$T(z)=zexp sum _{r=1}^{infty }{frac {1}{r}}T(z^{r})$ .

Производящая функция

$t(z)=sum _{n=1}^{infty }t_{n}z^{n}$

для числа $t_{n}$ неизоморфных деревьев с $n$ вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

$t(z)=T(z)-{frac {1}{2}}left(T^{2}(z)-T(z^{2})right).$

При $nto infty$ верна следующая асимптотика

$t_{n}sim Calpha ^{n}/n^{5/2}$

где $C$ и $alpha$ определённые константы, $C=0,534948...$ , $alpha =2,95576...$ .

Кодирование деревьев[править | править код]

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

См. также[править | править код]

Глоссарий теории графов
Лес непересекающихся множеств
Список структур данных (деревья)

Примечания[править | править код]

↑ § 13. Определение дерева // Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.. — М.: Наука, Физматлит, 1990. — С. 53. — 384 с. — 22 000 экз. — ISBN 5-02-013992-0.
↑ Альфс Берзтисс. Глава 3. Теория графов. 3.6. Деревья // Структуры данных = A. T. Berztiss. Data structures. Theory and practice. — М.: Статистика, 1974. — С. 131. — 10 500 экз.
↑ Дискретная математика: алгоритмы. Формула Кэли. Дата обращения: 29 октября 2009. Архивировано из оригинала 14 июня 2009 года.

Литература[править | править код]

Дональд Кнут. Искусство программирования, том = The Art of Computer Programming, vol. 1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — Т. 1. Основные алгоритмы. — 720 с. — ISBN 0-201-89683-4.
Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — 336 с.
Харари Ф. Теория графов. — М.: Мир, 1973. — 302 с.

Источник

Основные
определения

Дерево
– связный граф без циклов. Лес
(или ациклический
граф) – неограф без циклов. Компонентами
леса являются деревья.

Теорема 14.1.
Для неографа G
с n
вершинами без петель следующие условия
эквивалентны:

G
– дерево;
G
– связной граф, содержащий n
– 1
ребро;
G
– ациклический граф, содержащий n
– 1
ребро;
Любые две
несовпадающие вершины графа G
соединяет единственная цепь;
G
– ациклический граф, такой, что если в
него добавить одно ребро, то в нем
появится ровно один цикл.

Теорема 14.2.
Неограф G
является лесом тогда и только тогда,
когда коранг графа v(G)=0.

Висячая вершина
в дереве – вершина степени 1. Висячие
вершины называются листьями,
все остальные – внутренними
вершинами.

Если в дереве особо
выделена одна вершина, называемая
корнем,
то такое дерево называется корневым,
иначе – свободным.

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

Вершины дерева,
удаленные на расстояние k
(в числе дуг) от корня, образуют k-й
ярус (уровень) дерева. Наибольшее значение
k
называется высотой
дерева.

Если из какой-либо
вершины корневого дерева выходят дуги,
то вершины на концах этих дуг называют
сыновьями
(в английской литературе – дочери
(daughter)).

Центроид дерева

Ветвь
к вершине v
дерева – это максимальный подграф,
содержащий v
в качестве висячей вершины. Вес
вершиныk
– наибольший размер ее ветвей. Центроид
(или центр масс) дерева C
– множество вершин с наименьшим весом:
C
= {v|
c(v)
=
}.

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

Свободное дерево
порядка n
с двумя центроидами имеет четное
количество вершин, а вес каждого центроида
равен n/2.

Теорема 14.3
(Жордана).
Каждое дерево имеет центроид, состоящий
из одной или двух смежных вершин.

Пример 14.1.
Найти наименьший вес вершин дерева,
изображенного на рис. 14.1, и его центроид.

Рис. 14.1

Решение.
Очевидно, что вес каждой висячей вершины
дерева порядка n
равен n
– 1. Висячие вершины не могут составить
центроид дерева, поэтому исключим из
рассмотрения вершины 1, 2, 4, 6, 12, 13 и 16. Для
всех остальных вершин найдем их вес,
вычисляя длину (размер) их ветвей.

Число ветвей
вершины равно ее степени. Вершины 3, 5 и
8 имеют по две ветви, размеры которых
равны 1 и 14. К вершине 7 подходят четыре
ветви размером 1, 2, 2 и 10. Таким образом,
ее вес
.
Аналогично вычисляются веса других
вершин:,,.
Минимальный вес вершин равен 8,
следовательно, центроид дерева образуют
две вершины с таким весом: 11 и 15.

Десятичная
кодировка

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

Существует множество
способов кодировки деревьев. Рассмотрим
одну из простейших кодировок помеченных
деревьев с выделенным корнем – десятичную.

Кодируя дерево,
придерживаемся следующих правил.

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

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

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

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

. (14.1)

Рис. 14.2

Если корень
поместить в любой из висячих вершин, то
код
такого дерева будет выражаться большим
числом. Более того, существует зависимость.
Аналогично рассматриваются и цепи (рис.
14.3). Цепи обозначаются как.

Рис. 14.3

В звездах только
два варианта расположения корня с
различными десятичными кодировками. В
цепи же число вариантов кодировок в
зависимости от положения корня растет
с увеличением n.
Рассмотрим самый простой вариант,
расположив корень в концевой вершине
(листе). Для
получим двоичную кодировку 10 и десятичную
2, для– 1100 и 12, для– 111000 и 56, для– 11110000 и 240. Общая формула для десятичной
кодировки цепи с корнем в концевой
вершине имеет вид

. (14.2)

Пример
14.2. Записать
десятичный код дерева, изображенного
на рис. 14.4, с корнем в вершине 3.

Рис. 14.4

Решение.
На основании правила кодировки, двигаясь
по дереву, проставим в код единицы и
нули. При движении из корня 3 к вершине
7 проходим четыре ребра. В код записываем
четыре единицы: 1111. Возвращаясь от
вершины 7 к вершине 2 (до ближайшей
развилки), проходим три ребра. Записываем
в код три нуля: 000. От вершины 2 к 5 и далее
к 8 (меньший номер): 11; от 8 назад к 5 и от
5 к 9: 01; от 9 к корню 3: 000.

И, наконец, от 3 к
6 и обратно: 10. В итоге, собирая все вместе,
получим двоичный код дерева:

1 111 000 110 100 010.

Разбивая число
на тройки, переводим полученное двоичное
представление в восьмеричное. Получаем
.
Затем переводим это число в десятичное:.

Соседние файлы в предмете Дискретная математика

Источник

Связанные определения[править | править код]

Двоичное дерево[править | править код]

N-арные деревья[править | править код]

Свойства[править | править код]

Подсчёт деревьев[править | править код]

Кодирование деревьев[править | править код]

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

Вам также может понравиться

Как найти работу техничкой

Как найти хорошего гастроэнтеролога в омске

Как лайт нашел тетрадь смерти

Добавить комментарий Отменить ответ