0

我有一个用 ruby​​ 实现的树数据结构。我用它来表示解析树。

正如您所料，它的工作原理是拥有许多节点对象，每个对象都包含有用的值以及对其子节点的引用数组。

我编写了一个遍历树的方法，该方法非常简单，工作方式如下：

def depth_first_traversal(node, &block) 
    if(node.has_children?)
        depth_first_traversal(node.children[0], &block) 
        yield node 
        depth_first_traversal(node.children[1], &block)
    else
        yield node  
    end
end

问题是对于每棵树，我只明确地持有对根节点的引用。到目前为止，我一直在使用递归遍历来访问所有其他节点。

现在我需要更改树中节点的值，但我不知道该怎么做。我怎么能修改这个遍历，以便我可以修改树中的每个元素，而不是仅仅将它们的引用传递给&block?

--- 编辑： ---
为缺乏细节道歉，我试图让我的问题广泛而有用。

树中节点的“值”是节点对象的每个实例中的几个实例变量。让我们打电话给他们@value和@type。它们有 getter 和 setter 方法。

这棵树是一棵二叉树——但以后可能会改变。我也不认为这是我正在努力解决的问题的方面：

我的树显式创建了 Node @root。树中的所有其他节点都是在循环中创建的。所以一个典型的节点是可以访问的，例如作为“根的子节点的子节点”，并且不能以其他方式访问。

换句话说，搜索这种指针结构是我访问节点的唯一方法。如果 ruby​​ 仅按值传递，则产生的任何值（如在上述方法中）将是该对象的副本，而不是对象本身。

所以我很困惑我应该如何修改任何树中的值，而不仅仅是这个。

4

1 回答 1

0

如果我理解正确，你可能会做这样的事情：

def df_tree_map(node, &block)
    if(node.has_children?)
        df_tree_map(node.children[0], &block)
        node = yield node
        df_tree_map(node.children[1], &block)
    else
        node = yield node
    end
end

显然这将对树结构产生影响，但这可能是一个好处。不过，这里的关键点是你的块需要返回一个节点而不是任何旧的东西。例如，返回一个字符串不会像 Array#map 那样工作，因为一个节点天生就有子节点。

另一种解决方案是允许 map 函数修改节点的内容而不是结构。我在这里有点自由，因为您没有发布实例变量节点也可以访问，但它应该足够有意义：

def df_tree_map(node, &block)
    if(node.has_children?)
        df_tree_map(node.children[0], &block)
        node.contents = yield node.contents
        df_tree_map(node.children[1], &block)
    else
        node.contents = yield node.contents
    end
end

在这里，我不是将节点本身传递给块，而是传递内容。这样，树结构就不能被地图改变。看起来它可能与 Array#map 函数更一致，但它可能无法满足您的需求。

于 2012-12-08T00:58:25.480 回答