Посещение узлов дерева

Для многих приложений требуется просто обойти узлы дерева, неважно в каком порядке. В этих случаях клиент волен выбрать любой алгоритм прохождения. В данном приложении функция CountLeaf проходит дерево с целью подсчета его листьев. При распознавании очередного листа происходит приращение параметра count.

//Эта функция использует обратный метод прохождения.

//При посещении узла проверяется, является ли он листовым

template CountLeaf (<TreeNode<T> *t, int& count)

{

// Использовать обратный метод прохождения

if (t != NULL)

{

CountLeaf(t->Left(), count); // пройти левое поддерево

CountLeaf(t->Right(), count); // пройти правое поддерево

// Проверить, является ли данный узел листом.

// Если да, то произвести приращение переменной count

if (t->Left() == NULL && t->Right() == NULL)

count++;

}

}

Функция Depth использует обратный метод прохождения для вычисления глубины бинарного дерева. В каждом узле вычисляется глубина его левого и правого поддеревьев. Итоговая глубина на единицу больше максимальной глубины поддеревьев.

// Эта функция использует обратный метод прохождения

// для вычисления глубины левого и правого поддеревьев

// узла и возвращает результирующее значение глубины,

// равное 1 + max(depthLeft, depthRight).

// Глубина пустого дерева равна -1

template <class T>

void Depth (TreeNode<T> *t)

{

int depthLeft, depthRight, depthval;

if (t == NULL)

depthval = -1;

else

{

depthLeft = Depth(t->Left());

depthRight = Depth(t->Right());

depthval = 1 + (depthLeft > depthRight depthLeft : depthRight);

}

return depthval;

}