java - 二叉树 - 随机生成器

Question

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

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

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

Answer 1

除非您的目标是通过向其添加节点来构建二叉树，并且在某个点卡住索引和节点之间的映射，否则您的问题并没有真正的意义，以便 future 树的添加(在冰点之后)不会改变该映射。

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

如果您不想在树中的任何地方添加节点，而是想在某个地方添加节点，以便原始节点仍具有相同的索引，那么您需要做的就是沿着树的右子节点向下移动，直到您点击没有右 child 的节点。在您发布的示例中，这将是节点 10:

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

在要卡住的位置标记该节点。然后，当您添加新节点时，必须将新节点添加为标记节点的右 child ——或者如果标记节点有右 child R(因为您已经添加冷冻后的一个)，任何地方都是 R 的后代。在有序遍历中，以这种方式添加的新节点将始终成功出现在卡住点的节点。因此之前添加的节点的索引不会受到影响。

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