题
好的,所以我试图对二进制搜索树进行水平顺序遍历,并且它不起作用。下面的代码对我来说很有意义,但这可能是因为我一直在看它,并且我说服自己应该起作用。
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%的来龙去脉。
解决方案
结果没有错。
您能解释一下如何以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,因为您的算法正在插入。
不隶属于 StackOverflow