typedef Node *PNode;

int data[] = { 21, 8, 9, 11, 15, 19, 20, 21, 7 };
PNode Tree;
n = sizeof(data) / sizeof(int) - 1;
Tree = MakeTree (data, 0, n);

PNode MakeTree (int data[], int &from, int n)
{
PNode Tree;
int n1, n2;
if ( n == 0 ) return NULL;
Tree = new Node;
Tree->Key = data[from++];
n1 = n / 2;
n2 = n - n1 - 1;
Tree->Left = MakeTree(data, from, n1);
Tree->Right = MakeTree(data, from, n2);
return Tree;
}

Для примера ниже дана рекурсивная процедура просмотра дерева слева направо. Обратите
внимание, что поскольку дерево является рекурсивной структурой данных, при работе с ним
естественно широко применять рекурсию.
void PrintLKP(PNode Tree)
{
if ( ! Tree ) return;
PrintLKP(Tree->Left);
printf("%d ", Tree->Key);
PrintLKP(Tree->Right);
}

сортировка

void AddToTree (PNode &Tree, int data)
{
if ( ! Tree ) {
Tree = new Node;
Tree->Key = data;
Tree-> Left = NULL;
Tree->Right = NULL;
return;
}
if ( data < Tree->Key )
AddToTree ( Tree->Left, data );
else AddToTree ( Tree->Right, data );
}

поиск

PNode Search (PNode Tree, int what)
{
if ( ! Tree ) return NULL;
if ( what == Tree->Key ) return Tree;
if ( what < Tree->Key )
return Search ( Tree->Left, what );
else return Search ( Tree->Right, what );
}

Чтобы написать программу на Си, надо определить функцию, возвращающую приоритет
операции, которая ей передана. Определим приоритет 1 для сложения и вычитания и приоритет
2 для умножения и деления.
int Priority ( char c )
{
switch ( c ) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return 100;
}
Приведенная ниже программа строит требуемое дерево, используя эту функцию. Обратите
внимание, что при сравнении приоритета текущей операции с минимальным предыдущим
используется условие <=. За счет этого мы ищем именно последнюю операцию с минимальным
приоритетом, то есть, операцию, которая будет выполняться самой последней. Если бы мы
использовали знак <, то нашли бы первую операцию с наименьшим приоритетом и дерево
было бы построено неверно.
это не операция, пропускаем
Программирование на языке Си
К. Поляков, 1995-2002
23
PNode MakeTree (char Term[][10], int first, int last)
{
int MinPrt, i, k, prt;
PNode Tree = new Node;
if ( from == to ) {
strcpy (Tree->Data, Term[first]);
Tree->Left = NULL;
Tree->Right = NULL;
return Tree;
}
MinPrt = 100;
for ( i = first; i <= last; i ++ ) {
prt = Priority ( Term[i][0] );
if ( prt <= MinPrt ) {
MinPrt = prt;
k = i;
}
}
strcpy (Tree->Data, Term[k]);
Tree->Left = MakeTree(Term,first,k-1);
Tree->Right = MakeTree(Term,k+1,last);
return Tree;
}
Теперь обход этого дерева разными способами дает различные формы представления
соответствующего арифметического выражения.

Немного усложним задачу и разрешим использовать в выражении скобки одного вида
(допустим, круглые). Тогда при поиске в заданном диапазоне операции с минимальным
приоритетом не надо брать во внимание выражения в скобках (они выделены на рисунке).
a + ((b + c) * 5 + 3) * 7
Самый простой способ добиться этого эффекта – ввести счетчик открытых скобок nest. В
начале он равен нулю, с каждой найденной открывающей скобкой будем увеличивать его на 1, а
с каждой закрывающей - уменьшать на 1. Рассматриваются только те операции, которые
найдены при nest=0, то есть расположены вне скобок.
Если же ни одной такой операции не найдено, то мы имеем выражение, ограниченной
скобками, поэтому надо вызвать процедуру рекурсивно для диапазона from+1..last-1
(напомним, что мы предполагаем, что выражение корректно). Для сокращения записи показаны
только те части процедуры, которые изменяются:
создать конечную вершину- число
или переменную
искать ПОСЛЕДНЮЮ операцию с
наименьшим приоритетом (<=)
создать внутреннюю
вершину - знак операции
рекурсивно построить
поддеревья
выделить память под новую вершину
IV. Динамические структуры данных
К. Поляков, 1995-2002
24
PNode MakeTree (char Term[][10], int first, int last)
{
char c;
int MinPrt, i, k, prt;
int nest = 0;
PNode Tree = new Node;
...
MinPrt = 100;
for ( i = first; i <= last; i ++ ) {
c = Term[i][0];
if ( c == '(' ) { nest ++; continue; }
if ( c == ')' ) { nest --; continue; }
if ( nest > 0 ) continue;
prt = Priority ( c );
if ( prt <= MinPrt ) {
MinPrt = prt;
k = i;
}
}
if ( MinPrt == 100 &&
Term[first][0]== '(' && Term[last][0]==')' )
return MakeTree(Term, first+1, last-1);
...
return Tree;
}