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，最终以root 12的右节点结尾，然后插入18的左节点24的左节点 - 因为18更大，然后root 12，那么向右，然后18个少于24，因此将其插入为24的右节点

所以：

12


12
  \
  24

12
  \
  24
 /
18

因此，您有3个级别，第1（12）级，第2（24）级，第3（18）级，因此遍历遍历12,24,18，因为您的算法正在插入。