如果这看起来像是一个随机问题，我很抱歉，但我有一个包含超过 100,000 个名称/值对的数据库(如果你愿意，可以称它们为高分)存储在平衡二叉搜索树中，AVL 风格。大多数时候，为了列出分数，我使用中序遍历或逆序遍历打印 BST，但今天我遇到了以随机(或伪随机)顺序打印树的需要。是否有一些可接受的或最佳的方式来做到这一点:只访问每个节点一次，但以一种不可预测的方式？
PS -- 我考虑过广度优先遍历，但由于它总是以相同的方式发生，所以它并不是真正随机的。必须有一些聪明的方法，或者一些理想的面试答案，因为这似乎是一个普遍的问题；除了将节点标记为已访问或创建外部跟踪数据结构之外，我还没有想出任何真正聪明的办法。
最佳答案
我不知道为什么这个问题的答案不只是采用 BST，对其进行线性化，然后将其打印出来。我想您在这里担心的是，线性化这样的数据结构可能会占用大量内存。如果是这种情况，您总是可以挑选出树的片段，将它们线性化，然后四处跳跃。随机遍历指针并希望排序能够很好地工作是一个坏主意:您总是会在寻找最后一个节点时陷入困境。如果你有一个完整二叉树，你总是可以想出数字并从根开始(基本上，你可以从树的完整性属性中免费获得线性化)。
编辑:
我可能不太了解，因为我最近发现了这篇文章，尽管它是基于功能实现的，但它可能对您有用。我还没有全部阅读，所以我不知道它是如何迭代所有内容的，但如果你只是想取出一个节点，那么你可以使用这个..
关于c - 以随机顺序打印平衡 BST 的最佳方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10629482/