align="justify">. Починаючи з кореня і слідуючи за певною ланцюжку покажчиків, що містяться в елементах, можна здійснити доступ до будь-якого елементу структури. p align="justify">. На кожен елемент, крім кореня, є єдина посилання, тобто кожен елемент адресується єдиним покажчиком. p align="justify"> Наше вираз: X = (c/4 - d)/(a ​​* a - 1) представляється у вигляді наступного графа на рис. 2:
В
Рис. 2 - Вираз, представлене у вигляді дерева
Існує кілька способів подання абстрактної деревовидної структури. Ми розглянемо такі способи подання:
. За допомогою засобів динамічного розміщення компонентів і вказівки їх за допомогою посилань. Отже, дерево на рис.1 складається з компонент такого типу: node = record
op: char;, right: ^ node;
end;
. За допомогою масиву :: array [1 .. 11] of
record: char;, right: integer;
end;
Існує три способи обходу дерев:
. Зверху вниз: R, A, B;
. Зліва направо: A, R, B;
. Знизу вгору: A, B, R.
Перетворення дерева в бінарне (двійкове) дерево
Будь-яке m-арное дерево можна зберігати у вигляді двійкового дерева. Алгоритм перетворення m-арного дерева в бінарне полягає в наступному:
. Перший нащадок вершини розміщується по вертикалі вниз, а його брати - по горизонталі. Цю операцію повторюють для кожної окремо взятої вершини. p align="justify">. Отримане дерево розвертають на 45 В° і отримують дерево, для кожної вершини якого справа знаходяться брати, а ліворуч нащадки.
Розглянемо запропонований алгоритм на прикладі:
При послідовному розміщенні дерева один з покажчиків відсутня. При фамільному розміщенні відсутня правий покажчик. При цьому брати, якщо вони є, завжди знаходяться поруч. Замість правого покажчика введемо логічний ознака: рівний true, якщо у вершини є праве піддерево і false - ні. Для зберігання дерева можна скористатися масивом. p align="justify"> Лістинг програми
{$ M 65500, 0, 100000} MathExpr; {програма обчислює математичний вираз, будує дерево}
Uses crt; tr = ^ rec; = record: string; {Інформаційне поле}: boolean; {Прапор символу}
zn: real; {Значення змінної}: boolean; {Допоміжний прапор}, r: tr; {Покажчики на нащадка}; root, el: tr; {вершина й вузли дерева}: string; { допоміжна змінна}, j: byte; {}, y: integer; {координати для виведення дерева}: byte; {допоміжна змінна}: char; {}: integer; {для процедури VAL}
{процедура перетворення арифметичного вираження в бінарне дерево}
{про...
