如果这看起来像是一个随机问题,我很抱歉,但我有一个包含超过 100,000 个名称/值对的数据库(如果你愿意,可以称它们为高分),存储在 AVL 风格的平衡二叉搜索树中。大多数时候,为了列出分数,我使用中序遍历或逆序遍历来打印 BST,但今天我遇到了以随机(或伪随机)顺序打印树的需求。是否有一些公认的或最佳的方式来做到这一点:只访问每个节点一次,但以不可预测的方式?
PS——我考虑过广度优先遍历,但由于它总是以同样的方式发生,它并不是真正随机的。必须有一些聪明的方法,或者一些理想的面试答案,因为这似乎是一个普遍的问题;除了将节点标记为已访问或创建外部跟踪数据结构之外,我还没有想出任何真正聪明的方法。