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

if ( ! strchr("0123456789", Tree->data[i++]) ) 
return 0;
// если не нашли цифру, выход 
return 1; 
} 
Сама процедура вычисления выражения выглядит так: 
+
a
0
а)
p
*
a
0
б)
p

---

IV. Динамические структуры данных
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
30
void Calculate(PNode Tree) 
{
int num1, num2, result = 0; 
 
if ( ! Tree ||
// если нельзя вычислить, выход 
! IsNumber(Tree->left) || 
! IsNumber(Tree->right) ) return; 
 
num1 = atoi(Tree->left->data);
// получить данные от сыновей 
num2 = atoi(Tree->right->data);
 
switch ( Tree->data[0] ) {
// выполнить операцию

case '+': result = num1 + num2; break; 
case '-': result = num1 - num2; break; 
case '*': result = num1 * num2; break; 
case '/': result = num1 / num2; break; 
} 
delete Tree->left;
// удалить ненужные поддеревья 
delete Tree->right; 
sprintf(Tree->data, "%d", result); 
Tree->left = NULL;
Tree->right = NULL; 
} 
 
Дерево игр 
Одно из применений деревьев - игры с компьютером. Рассмотрим самый простой пример 
– игру в крестики-нолики на поле 3 на 3.
Программа должны анализировать позицию и находить лучший ход. Для этого нужно оп-
ределить оценочную функцию, которая получая позицию на доске и указание, чем играет иг-
рок (крестики или нолики) возвращает число – оценку позиции. Чем она выше, тем более вы-
годна эта позиция для игрока. Примером такой функции может служить сумма строк, столбцов 
и диагоналей, которые может занять игрок минус такая же сумма для его противника.
Однако, в этой ситуации программа не ведет просчет вперед и не оценивает позиции, ко-
торые могут возникнуть из текущей. Это недостаточно для предсказания исхода игры. Хотя для 
крестиков-ноликов можно перебрать все варианты и найти выигрышную позицию, большинст-
во игр слишком сложно, чтобы допускать полный перебор. 
Выбор хода может быть существенно улучшен, если просматривать на несколько ходов 
вперед. Уровнем просмотра называется число будущих рассматриваемых ходов. Начиная с 
любой позиции можно построить дерево возможных позиций, получающихся после каждого 
хода игры. Для крестиков-ноликов ниже приведено дерево с уровнем просмотра 3 для того слу-
чая, когда крестики сделали первый ход в центр доски.