C++：使用递归搜索功能更新二叉搜索树？

Question

我正在制作一个存储 MechPart 类型项目的二叉搜索树，它存储一个整数 quantity 和一个字符串 code。 MechPart 是通过读取文本文件并存储其数据生成的。名为 MonthlyUpdate.txt 的单独文本文件用于读取树中的 MechPart 列表，然后更新它们的数量。例如：

MechPart A0001's quantity = 12

MonthlyUpdate.txt says A0001's quantity = 6

Run an update function that finds A0001 in the tree

Replace it with the updated quantity value of 6 (12 - 6).

下面是执行此任务的两个函数：

    void DBInterface::updateFromFile(string f_Name) 
{
    ifstream file (f_Name.c_str());
    string line;

    MechPart tmp_mp;

    if (file.is_open())
    {
        std::getline(file, line);
        while (std::getline (file, line))
        {
            std::istringstream iss (line);
            int q=0;
            int pos=0;
            pos = line.find('\t',0); //find position of blank space
            string tmp_str = line.substr(0,pos); //create a substring
            string tmp_str1 = line.substr((pos+1), string::npos);
            stringstream ss (tmp_str1);
            ss >> q;

            tmp_mp.set_code(tmp_str); //set code
            tmp_mp.set_quantity(q);
            MechPart currentQuantity;
            currentQuantity = tree.quantitySearch(tree.getRoot(), tmp_mp);
            tmp_mp.set_quantity((currentQuantity.get_quantity()) + q);

            tree.update(tree.getRoot(), tmp_mp);
            cout << "Current node data: " << tmp_mp.get_code() << " | " << tmp_mp.get_quantity() << endl;


        }
    }

和BSTree.template：

template <typename Item>
Item BSTree<Item>::quantitySearch(BTNode<Item>* q_ptr, Item obj)
{
    if (q_ptr == NULL)
    {
    //POINTER IS NULL
    }
    else if (q_ptr->data() == obj)
    {
        return q_ptr->data();
    }

    else if (obj > q_ptr->data()) 
    { //WORK ON RIGHT SIDE
        quantitySearch(q_ptr->get_right(), obj);
    }
    else
    {
    //work on left side
        quantitySearch(q_ptr->get_left(), obj);

    }

}

搜索遍历树并找到与参数具有相同部件名称 code 的 MechPart，然后是 returns MechPart。我已经运行通过 GDB 调试器编写代码。我让它显示 currentQuantity.get_quantity() 以验证返回的 MechPart 的数量是否正确，但是由于某种原因我得到了非常大的数字。让我感到困惑的是，在 MechPart 构造函数中，它将值 0 分配给 quantity.

最终 updateFromFile() 函数给出了一个分段错误，所以这里有些地方很不对劲，但我还不能弄清楚是什么。

Answer 1

递归函数需要 return 它们的递归调用返回到它们的调用者才能正常工作。看递归的经典阶乘例子：

int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    else {
        return n*factorial(n-1);
    }
}

正如其他人指出的那样，您的 quantitySearch 函数仅 returns q_ptr->data() 但永远不会 returns 来自递归 [=] 的 return 值11=] 来电。我会从这里开始，强烈建议在递归函数中添加 cout 语句，以全面了解正在发生的事情 "under the hood"

C++：使用递归搜索功能更新二叉搜索树？

C++: Updating binary search tree using a recursive search function?

c++

templates

binary-search-tree