Mavzu: 13 Dinamik dasturlash. Kriptoalgoritmlari. Algoritmlarni loyihalash Algorithm Design


Download 1.24 Mb.
bet7/16
Sana15.06.2023
Hajmi1.24 Mb.
#1482872
1   2   3   4   5   6   7   8   9   10   ...   16
Bog'liq
13 mavzu Dinamik dasturlash. Kriptoalgoritmlarii

Корневое дерево G — это связный ациклический граф со специальным узлом, который называется корнем дерева, и каждое ребро прямо или косвенно происходит от корня.
Упорядоченное корневое дерево — это корневое дерево, в котором упорядочены дочерние элементы каждой внутренней вершины. Если каждая внутренняя вершина корневого дерева имеет не более m дочерних элементов, она называется m-арным деревом. Если каждая внутренняя вершина корневого дерева имеет ровно m детей, она называется полным m-арным деревом. Если m=2, корневое дерево называется бинарным деревом.

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

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

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

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

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

Прямой обход.

Прямой обход.

1. попасть в корень

2. пройти в прямом порядке левое поддерево

3. пройти в прямом порядке правое поддерево

Обратный обход.

Обратный обход.

1. пройти в обратном порядке левое поддерево

2. пройти в обратном порядке правое поддерево

3. попасть в корень

Симметричный обход.

Симметричный обход.

1. пройти в симметричном порядке левое поддерево

2. попасть в корень

3. пройти в симметричном порядке правое поддерево

Задача. Вычисление значения выражения, заданного деревом.

Задача. Вычисление значения выражения, заданного деревом.

В качестве примера рассмотрим выражение ((2+3)*(7-4))/3. Порядок вычисления выражения можно изобразить в виде дерева


Download 1.24 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10   ...   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling