Антон Спрол - Думай как программист: креативный подход к созданию кода. С++ версия

конструкторы, деструктор и даже методы, которые позволили бы нам построить дерево, чтобы сосредоточиться на нашем
рекурсивном методе.
class binaryTree {
public:
X int leafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
};

Обратите внимание на то, что наша функция для подсчета листьев не принимает параметров X. С точки зрения интерфейса это
корректно. Рассмотрим образец вызова для ранее построенного
объекта binaryTree bt:
Решение задач с помощью рекурсии

195

int numLeaves = bt.leafCount();

В конце концов, если мы спрашиваем у дерева, сколько у него листьев, то какую информацию мы могли бы предоставить этому объекту, которую он еще о себе не знает? Так же, как это является правильным для интерфейса, это не является правильным для рекурсивной
реализации. Если не существует параметра, что же меняется от одного рекурсивного вызова к другому? В этом случае ничто не может измениться, кроме как благодаря глобальным переменным, использования которых, как говорилось ранее, следует избегать. Если ничего
не изменяется, то для прогресса или прекращения рекурсии нет возможности.
Чтобы обойти эту проблему, нужно сначала написать рекурсивную функцию, концептуализируя ее как функцию вне класса. Другими словами, мы напишем эту функцию для подсчета листьев в
двоичном дереве в том же стиле, который мы использовали при написании функции для нахождения наибольшего значения в двоичном дереве. Единственным параметром, который нам необходимо
передать, является указатель на нашу структуру узла.
Это дает нам еще одну возможность использовать БРИ. В чем заключается вопрос Q в данном случае? Сколько листьев в дереве? Применение общего плана рекурсивной обработки двоичных деревьев к
этой конкретной задаче приводит к следующей последовательности
шагов.
1.

Если корень дерева не имеет дочерних элементов, то дерево
имеет только один узел. Этот узел является листом по определению, поэтому возвратите 1. В противном случае...

2.

Сделайте рекурсивный вызов для подсчета листьев в левом поддереве.

3.

Сделайте рекурсивный вызов для подсчета листьев в правом поддереве.

4.

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

5.

Возвратите сумму значений, полученных на этапах 2 и 3.
Переведя этот план в код, мы получим следующее:

struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
int leafCount(treePtr rootPtr) {
if (rootPtr == NULL) return 0;
if (rootPtr->right == NULL && rootPtr->left == NULL)
return 1;
int leftCount = leafCount(rootPtr->left);
196

Глава 6

int rightCount = leafCount(rootPtr->right);
return leftCount + rightCount;
}

Как вы можете видеть, код представляет собой прямой перевод плана. Вопрос в том, как мы переходим от этой независимой функции к
тому, что мы можем использовать в классе? Именно здесь неосторожный программист может легко попасть в неприятности, посчитав, что
нам нужно использовать глобальную переменную или сделать корневой
указатель общедоступным. Нам не нужно этого делать; мы можем оставить все внутри класса. Трюк заключается в использовании функцииобертки. Сначала мы помещаем независимую функцию с параметром
treePtr в приватный раздел нашего класса. Затем мы пишем публичную
функцию, которая будет служить «функцией-оберткой» для приватной
функции. Поскольку публичная функция имеет доступ к приватному
элементу данных _root, она может передать его рекурсивной функции,
а затем возвратить клиенту результаты следующим образом:
class binaryTree {
public:
int publicLeafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
int privateLeafCount(treePtr rootPtr);
};
X int binaryTree::privateLeafCount(treePtr rootPtr) {
if (rootPtr == NULL) return 0;
if (rootPtr->right == NULL && rootPtr->left == NULL)
return 1;
int leftCount = privateLeafCount(rootPtr->left);
int rightCount = privateLeafCount(rootPtr->right);
return leftCount + rightCount;
}
Y int binaryTree::publicLeafCount() {
Z return privateLeafCount(_root);
}

Несмотря на то, что язык C++ позволяет обеим функциям иметь
одно и то же имя, для ясности я использовал разные имена, чтобы различать публичную и приватную функции для «подсчета листьев». Код
в функции privateLeafCount X точно повторяет код в нашей предыдущей, независимой функции leafCount. Функция-обертка publicLeafCount Y проста. Она вызывает функцию privateLeafCount, передавая
приватный элемент данных _root, и возвращает результат Z. По --">