Для начала функцию insert можно упростить с учетом определения конструктора узла struct.
void insert(node*& pRoot, int val)
{
if (pRoot == NULL)
{
//insertion place found
pRoot = new node( val );
}
else if ( value < pRoot->value)
insert(pRoot->pLeft, val);
else
insert(pRoot->pRight, val);
}
Функция Retrieve не должна ничего выводить. Он должен возвращать логическое значение true или false. Вызывающая функция решает, какое сообщение вывести на основе возвращаемого значения функции. Функция может быть реализована следующим образом:
//look through the binary tree to find the user-input value
bool Retrieve( const node* pRoot, int value, size_t &n )
{
if ( pRoot == NULL)
{
return false;
}
else if ( ++n, value < pRoot->value )
{
return Retrieve( pRoot->pLeft, value, n );
}
else if ( ++n, value > pRoot->value )
{
return Retrieve(pRoot->pRight, value, n );
}
else
{
return true;
}
}
Перед вызовом функции аргумент, соответствующий третьему параметру, должен быть установлен в ноль, если вы хотите подсчитать количество сравнений в одном вызове функции. ..
Вот демонстрационная программа.
#include <iostream>
struct node
{
int value;
node * pLeft;
node * pRight;
};
void insert( node* &pRoot, int value )
{
if ( pRoot == nullptr )
{
pRoot = new node { value, nullptr, nullptr };
}
else if ( value < pRoot->value )
{
insert( pRoot->pLeft, value );
}
else
{
insert( pRoot->pRight, value );
}
}
bool Retrieve( const node* pRoot, int value, size_t &n )
{
if ( pRoot == NULL)
{
return false;
}
else if ( ++n, value < pRoot->value )
{
return Retrieve( pRoot->pLeft, value, n );
}
else if ( ++n, value > pRoot->value )
{
return Retrieve(pRoot->pRight, value, n );
}
else
{
return true;
}
}
int main()
{
node *pRoot = nullptr;
int a[] = { 123, 15, 392, 88, 731 };
for ( const auto item : a ) insert( pRoot, item );
size_t n = 0;
int value = 88;
if ( Retrieve( pRoot, value, n ) )
{
std::cout << value << " is found after " << n << " comparisons\n";
}
else
{
std::cout << value << " is not found after " << n << " comparisons\n";
}
return 0;
}
Ее вывод
88 is found after 5 comparisons
Обратите внимание, что есть 5 сравнений, а не 3 как вы написали в вопросе.
Действительно. Первое сравнение со значением узла root, равным 123. Затем второе сравнение со значением левого узла со значением 15. В этом случае есть два сравнения, соответствующих количеству выполненных операторов if
else if ( ++n, value < pRoot->value )
{
return Retrieve( pRoot->pLeft, value, n );
}
else if ( ++n, value > pRoot->value )
{
return Retrieve(pRoot->pRight, value, n );
}
И затем, чтобы определить, что текущий узел содержит точно значение 88, снова выполняются два сравнения со значением текущего узла
else if ( ++n, value < pRoot->value )
{
return Retrieve( pRoot->pLeft, value, n );
}
else if ( ++n, value > pRoot->value )
{
return Retrieve(pRoot->pRight, value, n );
}
else
{
return true;
}
Таким образом, правильный ответ - 5 сравнения. Что касается числа 3, то это не количество сравнений. Это количество рекурсивных вызовов.
Если вы хотите посчитать количество рекурсивных вызовов функции вместо количества сравнений, то измените функцию следующим образом
bool Retrieve( const node* pRoot, int value, size_t &n )
{
++n;
if ( pRoot == NULL)
{
return false;
}
else if ( value < pRoot->value )
{
return Retrieve( pRoot->pLeft, value, n );
}
else if ( value > pRoot->value )
{
return Retrieve(pRoot->pRight, value, n );
}
else
{
return true;
}
}
In в этом случае действительно число рекурсивных вызовов функции (не количество сравнений) будет равно 3.
. Используя этот подход, вы можете, например, подсчитать общее количество сравнений для нескольких вызовов функция.