0

假设我们有一棵二叉树，如下所示：在此处输入图像描述

我正在寻找一种算法来找到 A 的所有等价物。我得到了一个包含这棵树中元素的数组。规则是，如果一个节点的所有子节点都存在于数组中，则相当于该节点在数组中。比如我们数组中有B和C，就相当于有一个A。所以在上面的数组中，F+G=C，C+B=A，所以[B,F,G]也是等价于 A。同样 [DEFG] 也等价于 A。

我可以递归调用类似 checkSubstitute(node) 的东西：

if node in array
return true
else:
    for child in nodeChildren
        if ((child not in array) && (child == terminalNode))
            return false
        else
        return checkSubstitute(child)

这个逻辑有意义吗？另外，如何使用上述算法存储所有等效数组？

提前致谢！！

4

2 回答 2

3

您提供的方法无法正常工作，因为您总是在 for 循环的第一次迭代期间返回一个值。假设你有一个数组 [D]。然后 checkSubstitute(B) 返回 True，而它应该返回 False。

与其使用 for 循环，不如对两个孩子进行两次显式调用更容易。这假设每个节点都有零个或两个子节点。如果一个节点可以有一个子节点，则需要进行一些额外的空值检查。

#returns true if Node n exists in NodeList seq, or if its equivalent exists in seq.
function exists(n, seq):
    if n in seq:
        return True
    if not n.hasChildren:
        return False
    return exists(n.leftChild, seq) and exists(n.rightChild, seq)

获得所有等效数组只需要一些组合学。

#gets all possible equivalents for the given node. This includes itself.
#An equivalent is a list of nodes, so this method returns a list of lists of nodes.
function getPossibleEquivalents(node):
    ret = new List()
    baseCase = new List()
    baseCase.append(node)
    ret.append(baseCase)
    if not node.hasChildren:
        return ret  
    for each leftEquivalent in getPossibleEquivalents(node.leftChild):
        for each rightEquivalent in getPossibleEquivalents(node.rightChild):
            ret.append(leftEquivalent + rightEquivalent)
    return ret

编辑：您可以通过嵌套 N 个 for 循环来扩展具有恰好 0 或 N 个子节点的树的 getPossibleEquivalents：

for each child0Equivalent in getPossibleEquivalents(node.child[0]):
    for each child1Equivalent in getPossibleEquivalents(node.child[1]):
        for each child2Equivalent in getPossibleEquivalents(node.child[2]):
            for each child3Equivalent in getPossibleEquivalents(node.child[3]):
                for each child4Equivalent in getPossibleEquivalents(node.child[4]):
                    ret.append(child0Equivalent + child1Equivalent + child2Equivalent + child3Equivalent + child4Equivalent + child5Equivalent)

如果您想编写一个可以处理具有任意数量的孩子的树的单个函数，您需要获取每个孩子的每个可能等价物的笛卡尔积。有些语言已经为您实现了笛卡尔积。例如，在 python 中：

from itertools import product

def getPossibleEquivalents(node):
    ret = [node]
    if len(node.children) == 0: return ret
    for equivalentTuple in product(map(getPossibleEquivalents, node.children)):
        possibleEquivalent = reduce(lambda x,y: x+y, equivalentTuple)
        ret.append(possibleEquivalent)
    return ret
于 2012-06-11T20:30:21.377 回答
0

这个逻辑可以很好地生成所有等效的表示，但是有一些重复，如果你愿意，你可以检查和更正。（我将遵循一些关于复制内容的 python 约定）

假设您想要 [B,C] 中的所有可能表示对于此数组中的每个节点，您可以将其替换为其子节点，也可以保持原样。所以递归的总体思路是这样的：

find_equivalent(representation, node){
        // representation is a list which is a valid equivalent representation.
        child = list_of_children_of_node;
        Temp = representation[:]
        for each c in child: Temp.insert(child)


        find_equivalent(representation, next(node,representation))
        N = next(node,Temp)
        Temp.delete(node)
        Li.append(Temp)
        find_equivalent(Temp, N)
        // Here next function takes a list and a node and returns the next element from the list after node.

上面的 Li 是一个表示的全局数组，您需要在添加每个表示时为每个表示调用函数 find_equivalent。

于 2012-06-11T20:32:31.233 回答