二進制搜索樹的寬度優先搜索

我想爲二叉搜索樹製作寬度優先的搜索函數，但我似乎無法使其工作。任何指針將不勝感激！二進制搜索樹的寬度優先搜索

template <class T> 
bool BST<T>::displayBfs(T searchKey, BST<T> *node) 
{ 
    BST<T> *tmp = node; 
    queue <int> queue; 
    queue.push(node->mData); 

    if (node == NULL) 
    { 
     return false;  
    } 

    while (!queue.empty()) 
    { 
     queue.pop(); 
     if (tmp->mData == searchKey) 
      return true; 
     else 
     { 
      if(tmp->mLeft != NULL) 
       queue.push(tmp->mLeft->mData); 
      if(tmp->mRight != NULL) 
       queue.push(tmp->mRight->mData); 
     } 
    } 
    return false; 
}

來源

2012-10-24 nym_kalahi

哪裏定義了'tmp'？ – codaddict

任何症狀？它是編譯還是運行時錯誤？ – Lazin

對不起，我忘了我意外刪除了那條線。現在定義tmp。這是一個運行時錯誤。它只是陷入循環。 –

由於BST<T>節點有自己的孩子的信息，你必須把它們放在隊列中，而不是值，你在做什麼。其他的事情是，你在彈出它之前沒有從queue獲得元素。最後，由於std::queue我假設你正在使用，所以你必須給你的隊列提供其他名字。

嘗試重寫您的BFS是這樣的：

template <class T> 
bool BST<T>::displayBfs(T searchKey, BST<T> *node) 
{ 
    if (node == NULL) return false; 

    queue<BST<T>*> q; 
    q.push(node); 

    while (!q.empty()) 
    { 
     BST<T>* tmp = q.front(); 
     q.pop(); 

     if (tmp->mData == searchKey) 
      return true; 
     else 
     { 
      if(tmp->mLeft != NULL) 
       q.push(tmp->mLeft); 
      if(tmp->mRight != NULL) 
       q.push(tmp->mRight); 
     } 
    } 
    return false; 
}

來源

2012-10-24 05:45:42

謝謝你，男人。我想我現在明白了！ –

我會的。我必須等幾分鐘。 –

幾件事情：

爲node == NULL測試應該來訪問節點之前：

if (node == NULL) 
    return false;  
queue.push(node);

而且您的隊列應該是的節點類型，您應該將隊列中的節點插入隊列中：

隊列*>隊列;

最後你不是訪問dequed元素，你需要在調用pop之前使用隊列類的front方法訪問front元素。

來源

2012-10-24 05:48:47 codaddict

二進制搜索樹的寬度優先搜索

回答

相關問題