二叉树-随机生成器

Question

假设我有一个像这样的二叉树-

       5               
      / \       
     /   \      
    /     \     
   /       \    
   2       8       
  / \     / \   
 /   \   /   \  
 1   3   6   9   
      \   \   \ 
      4   11   10 

现在我有一个随机生成器，它将生成一个介于1到树大小之间的数字(在本例中为10)。根据随机生成器生成的随机值，我必须返回树中的节点(假设生成器给定7，因此我返回第7个节点(值11)，执行顺序遍历)。明天我会向树中再添加4个节点。如何保持一致性？与中一样，对于随机值，将返回树中的相同节点。顺序遍历将创建一个不同的数组，索引值将发生变化。

Answer 1

除非您的目标是通过在二叉树中添加节点来构建二叉树，并在某个点冻结索引和节点之间的映射，这样以后添加到树中的内容(在冰点之后)不会更改该映射，否则您的问题就没有实际意义。

目前还不清楚您想要实现什么，但我可以看到几种可能性。如果您的意图是可以在树中的任何位置添加新节点，那么它们实际上不可能有任何合理地映射到它们的索引。在这种情况下，我只需在冰点创建一个映射(例如HashMap)，将索引映射到节点。使用顺序遍历遍历树，构建映射，并将其与树结构一起保存。使用映射来确定索引的节点，而不是遍历树。

如果您不想在树中的任何位置添加节点，而是希望在某个位置添加节点，以便原始节点仍然具有相同的索引，那么您所需要做的就是向下查找树的右子节点，直到遇到没有右子节点的节点。在您发布的示例中，这将是节点10

       5               
      / \       
     /   \      
    /     \     
   /       \    
   2       8       
  / \     / \   
 /   \   /   \  
 1   3   6   9   
      \   \   \ 
      4   11   10**

在要冻结的点处标记该节点。然后，当您添加新节点时，必须将新节点添加为标记节点的右子节点--或者如果标记的节点具有右子节点R (因为您已经在冻结后添加了一个)，则它将成为R的后代。以这种方式添加的新节点将在顺序遍历中始终成功，即出现在冰点处的节点。因此，先前添加的节点的索引不会受到影响。

如果这两个都不是您想要的，那么您需要提供更多关于您需要什么的说明。

Answer 2

一种选择是只添加任何新节点作为有序遍历中最后一个节点的右子节点。这将导致一个非常深的和不平衡的树；你没有要求一个平衡的树，所以这是可能的。