2

好的，所以我正在尝试对二叉搜索树进行级别顺序遍历，但它不起作用。下面的代码对我来说很有意义，但这可能是因为我一直在研究它，并且我确信它应该可以工作。

void BST<T>::levelByLevel(ostream &out) { 
 Queue<BinNodePointer> q; 
 BinNodePointer subtreeRoot; 

 if(myRoot == NULL) 
  return; 
 q.enqueue(myRoot); 
 while(!q.empty()) {
  subtreeRoot = q.front(); 
  out << subtreeRoot->data << " "; 
  q.dequeue(); 

  if(subtreeRoot->left != NULL) 
   q.enqueue(subtreeRoot->left); 
  if(subtreeRoot->right != NULL) 
   q.enqueue(subtreeRoot->right); 
 } 
}

也许你们可以指出我做错了什么，因为虽然我理解二叉搜索树的概念，但我并不是 100% 了解所有细节。

4

1 回答 1

1

结果没有错。

你能解释一下你是如何到达 24,12,18 的吗？

我假设您首先在根级别插入 12，然后插入 24，最终作为根 12 的右节点，然后插入 18，最终作为 24 的左节点 - 因为 18 比根 12 大，所以向右，然后 18小于 24，因此它作为 24 的右节点插入

所以：

12


12
  \
  24

12
  \
  24
 /
18

因此，您有 3 个级别，级别 1 (12)、级别 2 (24)、级别 3 (18)，因此当您的算法插入时，级别遍历 12、24、18。

于 2010-05-02T23:22:35.773 回答