二叉树节点位置和辅助字典

Question

背景

我有一个关于在树中定位节点的问题。

我有一个简单的二叉树。每个节点中都有一段数据。让我们说它看起来像这样：

  a

 / \

b   c

其中a=root, b=root.left,c=root.right

树不是手动创建的。假设我收到一个添加new_data到节点 c的请求。

我很困惑如何知道 c 在没有明确写的情况下在哪里root.right.data=new_data。

我的第一个想法是创建某种类型的辅助字典，其中包含对节点位置的引用，例如：

helper = {

    'a'= root,

    'b'= root.left,

    'c'= root.right

}

这样当我收到请求时，我就可以去找帮手说一些大意：

helper.get('c').data=new_data

问题

我在正确的球场吗？重复地递归搜索整个树似乎有点多 - 当树改变其节点结构时，这个助手可能会偶尔更新。

当我递归地爬取树时，我对如何为每个节点实际返回我的位置感到困惑。我怎样才能创建这个助手？

Answer 1

如果你有节点 c 的引用，你可以直接使用它，就像这样c.data=new_data。否则，如果你得到的是一个字符串，那么：你的树是排序的，还是可以排序的？（即它是BST吗？）如果是，请使用它。如果不是，那么您可以使用树/节点的任何其他属性来修剪搜索吗？（即您有一些信息来限制搜索位置）。如果是这样，请使用它。如果您不知道是否可以使用它，则应在问题中指定数据具有的任何属性。如果节点可以在任何地方，那么您几乎必须搜索整个树（因为您想要的节点可以在任何地方）。如果是这样的话，树结构是否有目的？也许哈希表可能有用。（您可以在获得树后对其进行索引）顺便提一句。请注意，搜索树的大小应该是 O(n)，这取决于您是否过多。