Для решения задачи естественно использовать прямой обход с тем, чтобы узел – отец создавался раньше, чем сыновья.
NODE *CopyBinTree(NODE *Root){
// функция имеет указатель на корень
// дерева – оригинала в качестве аргумента
// и возвращает указатель на корень дерева – копии
if(Root==NULL) return NULL;
// создадим корень в копии
NODE *RootCopy=new NODE;
// левый и правый сыновья в дереве – копии являются
// копиями левого и правого поддеревьев корня в оригинале
RootCopy->Llink=CopyBinTree(Root->Llink);
RootCopy->Rlink=CopyBinTree(Root->Rlink);
Return RootCopy;
}
Задача 2. Вычисление значения выражения, заданного деревом.
В качестве примера рассмотрим выражение ((2+3)*(7-4))/3. Порядок вычисления выражения можно изобразить в виде дерева на рис. 24.
Рис.24. Выражение в дереве
Узел дерева в поле данных содержит либо число, либо символ операции. Если узел содержит число, то это операнд, а если операцию, то значения левого и правого поддеревьев суть её операнды. Вычисление естественно выполнять в порядке концевого обхода, поскольку для того, чтобы выполнить операцию, надо знать её операнды. Структура узла имеет вид:
const int OPERATION=0; // признак: узел содержит операцию
const int NUMBER=1; // признак: узел содержит число
struct UZEL{
union {
