Iv. Динамические структуры данных

PNode MakeTree (char Expr[], int first, int last) 
{ 
int MinPrt, i, k, prt; 
PNode Tree = new Node;
// создать в памяти новую вершину 
if ( first == last ) {
// конечная вершина: число или

Tree->data = Expr[first];
// переменная 

---

IV. Динамические структуры данных
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
26
Tree->left = NULL; 
Tree->right = NULL; 
return Tree; 
} 
MinPrt = 100; 
for ( i = first; i <= last; i ++ ) { 
prt = Priority ( Expr[i] ); 
if ( prt <= MinPrt ) { 
// ищем последнюю операцию
MinPrt = prt;
// с наименьшим приоритетом 
k = i; 
} 
 } 
Tree->data = Expr[k];
// внутренняя вершина (операция) 
Tree->left = MakeTree (Expr,first,k-1); 
// рекурсивно строим 
Tree->right = MakeTree (Expr,k+1,last);
// поддеревья 
return Tree; 
} 
Теперь обход этого дерева разными способами дает различные формы представления соответ-
ствующего арифметического выражения. 
 Вычисление выражения по дереву 
Пусть для некоторого арифметического выражения построено дерево и известен его адрес 
Tree. Напишем функцию, которая возвращает целое число – результат вычисления этого вы-
ражения. Учтем, что деление выполняется нацело (остаток отбрасывается). 
int CalcTree (PNode Tree) 
{ 
int num1, num2; 
if ( ! Tree->left )
// если нет потомков, 
return Tree->data - '0';
// вернули число 
num1 = CalcTree(Tree->left);