2

如果这看起来像是一个随机问题，我很抱歉，但我有一个包含超过 100,000 个名称/值对的数据库（如果你愿意，可以称它们为高分），存储在 AVL 风格的平衡二叉搜索树中。大多数时候，为了列出分数，我使用中序遍历或逆序遍历来打印 BST，但今天我遇到了以随机（或伪随机）顺序打印树的需求。是否有一些公认的或最佳的方式来做到这一点：只访问每个节点一次，但以不可预测的方式？

PS——我考虑过广度优先遍历，但由于它总是以同样的方式发生，它并不是真正随机的。必须有一些聪明的方法，或者一些理想的面试答案，因为这似乎是一个普遍的问题；除了将节点标记为已访问或创建外部跟踪数据结构之外，我还没有想出任何真正聪明的方法。

4

1 回答 1

1

我不知道为什么这个问题的答案不仅仅是采用 BST，将其线性化，然后打印出来。我想您在这里担心的是线性化这样的数据结构可能会占用大量内存。如果是这种情况，您总是可以挑选出树的碎片，将它们线性化，然后跳来跳去。随机遍历指针并希望能够正常工作的排序是一个坏主意：你总是会在寻找最后一个节点时搞砸。如果你有一棵完整的二叉树，你总是可以提出数字并从根开始（本质上，你可以从树的完整性属性中免费获得线性化）。

编辑：

我没有得到应有的了解，因为我最近发现了这篇文章，虽然它是基于功能实现的，但它可能对你有用。我还没有全部阅读，所以我不知道它是如何迭代所有内容的，但是如果你只是想得到一个节点，那么你可以使用这个..

http://okmij.org/ftp/Algorithms.html#random-tree-node

于 2012-05-17T03:38:50.953 回答