C++：使用遞歸搜索函數更新二叉搜索樹？

我正在製作一個存儲int和字符串code的類型爲MechPart的項目的二叉搜索樹。 MechParts是通過從文本文件中讀取並存儲它們的數據而生成的。一個名爲MonthlyUpdate.txt的單獨文本文件用於讀取樹中的MechParts列表，然後更新它們的數量。例如：C++：使用遞歸搜索函數更新二叉搜索樹？

MechPart A0001的數量= 12

MonthlyUpdate.txt說A0001的數量= 6

運行的是發現樹A0001的更新功能

與更新的數量進行更換值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作爲參數，然後返回MechPart。我一直在通過GDB調試器運行代碼。我有它顯示currentQuantity.get_quantity()來驗證返回的MechPart的數量是正確的，但我由於某種原因得到非常大的數字。令我困惑的是，在構造函數MechPart中，它賦值爲0到quantity。

最終updateFromFile()函數給我一個分段錯誤，所以這裏有些東西是非常錯誤的，但我現在還不能解決這個問題。

來源

2015-11-05 Cameron O' Reilly

當您遞歸搜索時，您需要返回找到的節點。你只爲一個'if-else'塊做這件事。在其他情況下，您將放棄返回值。 –

有點苛刻。我對此很陌生。 –

@a_pradhan我不確定你的意思。該函數不斷調用自身，並傳入不同的節點，直到它到達正確的節點，然後返回其數據（在本例中爲MechPart）。 –

遞歸函數需要將它們的遞歸調用返回給它們的調用者以使它們正常工作。看看遞歸的經典階乘的例子：

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

正如其他人所指出的那樣，你quantitySearch函數只返回q_ptr->data()但從未返回從遞歸調用quantitySearch返回值。我會在那裏開始，我強烈建議在遞歸函數中添加cout語句以獲得「底層」中發生的事情的完整畫面。

來源

2015-11-05 08:16:15 jsherman256

C++：使用遞歸搜索函數更新二叉搜索樹？

回答

相關問題