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 回答