C++

Question

下面是我用来 1) 从文本文件中提取数字并将它们保存到数组中的代码； 2）使用数组作为“输入”并将数组中的数字导入二叉树； 3) 通过二叉树查找用户输入的值，如果找到，输出“Value Found”，如果没有找到，输出“Value not found”。

代码运行良好。但我在最后一部分苦苦挣扎。我必须让程序输出在二叉树中找到（或找不到）每个值所花费的比较次数。

#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;
    }
}

目前，Retrieve 函数只能显示是否找到了值。但是，我也需要它来打印出找到该值所需的比较次数。

比如文本文件中包含“123 15 392 88 731”五个数字，我输入数字“88”进行查找，程序应该进行3次比较，找到二叉树中的数字。我想让程序打印出类似“It take 3 compares”的内容。

如果我输入数字“999”。 “999”在二叉树中不存在，但程序还是进行了 3 次比较才得出这个结论，所以程序应该打印出“It take 3 compares”。我试图在 Retrieve 函数中添加一个 for 循环，但不知何故它没有成功......任何提示将不胜感激！

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;
        }

}

Answer 2

对于初学者来说，考虑到结构节点构造函数的定义，可以简化函数插入。

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 函数不应输出任何内容。它应 return 一个布尔值，true 或 false。函数的调用者根据函数的 return 值决定输出什么信息。该功能可以通过以下方式实现

//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。

确实如此。第一次比较根节点的值为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;
    }
}

在这种情况下，函数的递归调用次数（不是比较次数）确实等于 3。

使用这种方法，您可以计算函数多次调用的比较总数。

C++ - 如何计算程序在二叉树中找到一个值所花费的比较次数

C++ - How to count how many compares it took the program to find a value in the binary tree

binary-tree

binary-search-tree