c++ - BST 层次遍历

Question

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

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% 了解所有的来龙去脉。

Answer 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。