二叉树 - 随机生成器

Question

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

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

现在我有一个随机生成器,它将生成1到树大小的数字(在这种情况下为10).根据由随机数发生器我不得不从树上返回节点生成的随机值(假设,给出7发电机,所以我回到了7点(价值11),做序遍历).明天我再向树中添加4个节点.如何保持一致性？与此同时,返回树中的相同节点作为随机值.inorder遍历将创建一个不同的数组,索引的值将发生变化.

Answer 1

除非您的目标是通过向其添加节点来构建二叉树,并在某个点冻结索引和节点之间的映射,否则您的问题确实没有意义,因此将来添加到树中(在冻结点之后)不要改变那种映射.

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

如果您不想在树中的任何位置添加节点,而是想在一个地方添加节点,以便原始节点仍然具有相同的索引,那么您需要做的就是沿着树的右边的子节点向下,直到您点击一个节点为止没有合适的孩子.在您发布的示例中,这将是节点10:

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

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

如果这些都不是您想要的,您需要提供更多关于您需要的说明.