BST级别遍历

好吧，所以我正在尝试对二叉查找树进行级别遍历并且它不工作。下面的代码对我来说很合理，但这可能是因为我一直在看它，并且我确信它应该可以工作。BST级别遍历

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

来源

2010-05-02 Dalton Conley

那么你会得到什么结果？你期望什么？ – stefanB 2010-05-02 23:00:46

好吧，如果我进入这样的事情到树：12 24 18 .. 水平遍历的输出为：12 24 18 ..这是不正确的。我期待的输出是24 12 18 – 2010-05-02 23:08:19

是'BST <>'AVL？如果不是，那么你的期望是错误的。这个输入会产生一个有三个级别的树。如果树按左右排序排序，那么你应该得到这样一棵树：root是12，左边的孩子是24，右边的孩子是NULL; 24的左边孩子是NULL，24的右边孩子是18. – wilhelmtell 2010-05-02 23:16:12

结果没有问题。

你能解释一下你怎么在24,12,18到达？

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

所以，正确的节点：

所以，你有3个级别，级别1（12），2级（24），级别3（ 18），所以级别遍历12,24,18作为您的算法插入。

来源

2010-05-02 23:22:35 stefanB

啊谢谢你！它更有意义..事实上，如果我只想把它抽出来，我可能会得出同样的结论。我的问题是，它来自实验室手册，我已经总结出树的显示不正确。 – 2010-05-02 23:42:07

回答

相关问题