-3

我正在尝试在 Ruby 中实现一个函数来检查二叉树 2 是否是二叉树 1 的子树。这就是我目前所拥有的——它似乎可以工作，但我不确定它的可扩展性如何。这是 O(2^k) 时间吗？如果是这样，任何想法如何优化它？我假设 tree1 和 tree2 属于具有属性数据、左和右的节点类。

def containsTree(tree1, tree2)
    if tree2.nil?
        return true
    if tree1.nil?
        return false
    if tree1.data == tree2.data
        containsTree(tree1.left, tree2.left) && containsTree(tree1.right, tree2.right)
    else
        containsTree(tree1.left, tree2) || containsTree(tree1.right, tree2)
    end
end
4

1 回答 1

1

似乎您可以编写一些东西来遍历tree1寻找其数据与根节点数据相同的节点tree2。当你找到这样一个节点时，从那个节点开始并行遍历子树tree2，检查每个节点是否匹配。您应该同时到达两棵树的尽头。

当然，可以有很多节点tree1的数据与 的根节点匹配tree2。

该算法看起来像这样（不是在 Ruby 中）：

// this method looks for nodes in tree1 that match the root node of tree2
traverse(node, tree2root)
{
    if (node == null) return
    if node.data == tree2root.data
        if check_trees(node, tree2root)
            print "tree2 is a subtree"
    traverse(node.left, tree2root)
    traverse(node.right, tree2root)
}

check_trees(tree1, tree2)
{
    if (tree1 == null && tree2 == null)
        return true
    if (tree1 == null || tree2 == null)
        return false
    if (tree1.data != tree2.data)
        return false
    if (!check_trees(tree1.left, tree2.left))
        return false
    return check_trees(tree1.right, tree2.right)
}

你可以这样称呼它：

traverse(tree1, tree2)

traverse如果您希望在找到匹配项后停止该方法，则需要在该方法上添加提前退出。

在一般情况下，这并不是非常有效，但如果没有太多节点tree1的数据与tree2.

于 2013-10-02T16:33:13.927 回答