Корневое дерево G — это связный ациклический граф со специальным узлом, который называется корнем дерева, и каждое ребро прямо или косвенно происходит от корня.
Упорядоченное корневое дерево — это корневое дерево, в котором упорядочены дочерние элементы каждой внутренней вершины. Если каждая внутренняя вершина корневого дерева имеет не более m дочерних элементов, она называется m-арным деревом. Если каждая внутренняя вершина корневого дерева имеет ровно m детей, она называется полным m-арным деревом. Если m=2, корневое дерево называется бинарным деревом.
Обход бинарного дерева Обход бинарного дерева Для работы с древовидными структурами имеется множество алгоритмов, и многие из них используют одну и ту же идею, а именно идею прохождения или обхода дерева. Обход дерева подразумевает такой порядок работы с его узлами, для которого каждый из них посещается точно один раз. Для обхода бинарного дерева могут быть использованы три способа, определяемых рекурсивно. Прямой обход. Прямой обход.
Обратный обход. Обратный обход. 1. пройти в обратном порядке левое поддерево 2. пройти в обратном порядке правое поддерево 3. попасть в корень Симметричный обход. Симметричный обход. 1. пройти в симметричном порядке левое поддерево 2. попасть в корень 3. пройти в симметричном порядке правое поддерево Задача. Вычисление значения выражения, заданного деревом. Задача. Вычисление значения выражения, заданного деревом. В качестве примера рассмотрим выражение ((2+3)*(7-4))/3. Порядок вычисления выражения можно изобразить в виде дерева
Do'stlaringiz bilan baham: |
