c++ - C++-如何计算比较程序在二进制树中查找值所花费的次数

Question

下面是我用于以下代码:1)从文本文件中提取数字并将其保存到数组中； 2)使用数组作为“输入”，并将数组中的数字导入到二叉树中； 3)在二叉树中搜索以找到用户输入的值，如果找到，则输出“找到的值”，如果找不到，则输出“找不到值”。

该代码工作得很好。但是我在最后一部分上苦苦挣扎。我必须使程序输出查找(或找不到)二叉树中的每个值所需的比较次数。

#include<iostream>
#include  <fstream>
#include <string>

using namespace std;

//define the struct of a binary tree

typedef struct node
{
    int value;
    node * pLeft;
    node * pRight;
    node(int val = 0)
    {
        value = val;
        pRight = NULL;
        pLeft = NULL;
    }
}node;


//decide insertion location for each value imported from the array
void insert(node*& pRoot, int val)
{
    if (pRoot == NULL)
    {
        //insertion place found
        pRoot = new node;
        pRoot->pRight = NULL;
        pRoot->pLeft = NULL;
        pRoot->value = val;
    }
    else if (val < pRoot->value)
        insert(pRoot->pLeft, val);
    else
        insert(pRoot->pRight, val);
}

//pass in value from arrary to the binary tree
node * getBST(int * arr, int size)
{
    node * pRoot = NULL;
    for (int i = 0; i < size; i++)
        insert(pRoot, arr[i]);
    return pRoot;
}

//look through the binary tree to find the user-input value 
void Retrieve(node* pRoot, int value)
{
        if (pRoot == NULL)
        {
            bool found = false;
            cout << "Value not found" << endl;
        }
        else if (value < pRoot->value)
        {
            Retrieve(pRoot->pLeft, value);
        }
        else if (value > pRoot->value)
        {
            Retrieve(pRoot->pRight, value);
        }
        else
        {
            value = pRoot->value;
            bool found = true;
            cout << "Value found" << endl;
        }

}

int main()
{
    ifstream file("5 Random Numbers.txt");
    if (file.is_open())                    //open the file
    {
        int arr[5];

        for (int i = 0; i < 5; ++i)     //put numbers in the file into the array
        {
            file >> arr[i];
        }

        node * pRoot = getBST(arr, 5);   //convert array to binary tree; 5 is the size   

        for (int i = 0;i < 3; ++i)     //ask user to enter 3 numbers, then search these numbers in the binary tree
        {
            int userValue;
            cout << "Enter an integer to search: ";
            cin >> userValue;
            Retrieve(pRoot, userValue);
        }


        cout << endl;

        return 0;
    }
}

现在，“检索”功能只能显示是否找到了它的值。但是，我还是需要它打印出找到值(value)所需的比较次数。

例如，如果文本文件包含五个数字“123 15 392 88 731”，而我输入数字“88”进行搜索，则应该将程序3进行比较才能在二进制树中找到该数字。我希望程序打印出类似“花了3个比较”的内容。

如果输入数字“999”。二叉树中不存在“999”，但仍然需要程序进行3次比较才能得出结论，因此程序应打印出“进行3次比较”。
我尝试将for循环添加到Retrieve函数中，但是以某种方式无法解决问题……任何提示都将不胜感激!

Answer 1

在函数中添加depth参数，并在树的每个级别上对其进行递增。

void Retrieve(node* pRoot, int value, int depth)
{
        if (pRoot == NULL)
        {
            bool found = false;
            cout << "Value not found" << endl;
        }
        else if (value < pRoot->value)
        {
            Retrieve(pRoot->pLeft, value, ++depth);
        }
        else if (value > pRoot->value)
        {
            Retrieve(pRoot->pRight, value, ++depth);
        }
        else
        {
            value = pRoot->value;
            bool found = true;
            cout << "Value found" << depth << endl;
        }

}