二进制搜索树的宽度优先搜索

我想为二叉搜索树制作宽度优先的搜索函数，但我似乎无法使其工作。任何指针将不胜感激！二进制搜索树的宽度优先搜索

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

二进制搜索树的宽度优先搜索

回答

相关问题