判断第一棵树是否是第二棵树的子集

Question

我在互联网上查了所有的资料，想知道如何检查一棵树是否是另一棵树的子集。通过子集，我的意思是如果第一棵树的所有元素都出现在第二棵树中，issubset 函数应该 return 1 0 否则。请注意，根据元素的插入顺序，具有相同元素集的两棵树可能具有非常不同的形状。将以下示例作为树：

Elements of the first tree
             4
           /  \
         2     6
        / \   / \
       1   2  5  7 


Elements of the second Tree
            6
          /   \
         4     7
        /  \
       2    5
      / \
     1   2

以下代码遍历树然后检查值：

int issubset(nodeT **tree1, nodeT **tree2) {

    if( *tree2 == NULL)
        return TRUE;
    if(*tree1 == NULL)
        return FALSE;

    if(are_identical(&(*tree1),&(*tree2)))
        return TRUE;

    return issubset(&(*tree1)->pLeft, &(*tree2)) || issubset(&(*tree2)->pRight, &(*tree2));
}

int are_identical(nodeT **tree1, nodeT **tree2) {
    nodeT **temp;
    int iFound = 0, i, r;   
    if( *tree2 == NULL)
        return TRUE;

    if( (*tree1) ==NULL && (*tree2) ==NULL) {
        return FALSE;
    }

    if( (*tree1)->iValue != (*tree2)->iValue) {
        if(iFound = 0)
            return TRUE;

        i = issubset(&(*tree1)->pLeft, &(*tree2));
        if( i ==0) {
            r = issubset(&(*tree1)->pRight, &(*tree2));
            return r;
        }

        return i;
    }   

    return((*tree1)->iValue == (*tree2)->iValue && are_identical(&(*tree1)->pLeft, &(*tree2)->pLeft) && 
           are_identical(&(*tree1)->pRight, &(*tree2)->pRight) );
}

在运行我的代码和给定示例之后，我的输出返回第一棵树不是第二棵树的子集，而实际上它是一个子集。

Answer 1

二叉搜索树支持对元素进行高效的排序迭代。以非降序维护每棵树的元素的迭代器。重复以下直到确定结果：

如果第一个迭代器没有更多元素，return TRUE.
如果第二个迭代器没有更多元素，return FALSE.
如果第一个迭代器的当前元素小于第二个迭代器的当前元素，return FALSE.
如果第一个迭代器的当前元素等于第二个迭代器的当前元素，则更新两个迭代器。
如果第一棵树的当前元素大于第二棵树的当前元素，则更新第二个迭代器。（您可以通过跳过一些元素来优化它。）

基本实现是最坏情况O(n + m)，其中n和m是两棵树各自的大小。通过提到的优化，如果较大的树是平衡的，您还可以通过 O(n log m) 对其进行约束，如果第二棵树比第一棵大得多，这将很有用。（无论树是否平衡，O(n + m) 界限仍然适用。）

Answer 2

我不确定我是否理解你的问题，但我仍然会尝试给你我的答案。根据您的示例，我假设您正在使用二叉搜索树。但我不知道你使用的是哪种二叉树，我会假设一个通用方案。我想如果这棵树有点平衡，那么也许你可以获得更好的算法。

因为你有二叉搜索树，你可以假设一个函数 search(root, key) 它 return 是指向包含 key 的节点的有效指针，如果找到这个节点或 NULL 否则。

此外，我假设您知道每棵树的节点数。所以你可以 return 0 如果 tree1 的节点比 tree 少。否则处理方法如下：

int tree1_contained_in_tree2(node * tree1, node * tree2)
{
  if (tree1 == NULL) // am I visiting a empty tree?
    return 1;

  // so I am sure tree1 is not NULL ==> I search the contained key in tree2
  if (search(tree2, tree1->key) == NULL)
    return 0; // tree1->key does not belong to tree2

  // here tree1->key belongs to tree1 so, I test with the subtrees of root
  return tree1_contained_in_tree2(tree1->left, tree2) && 
         tree1_contained_in_tree2(tree1->right, tree2);    
}

我更喜欢使用指向节点的简单指针而不是双指针。我认为你可以根据你的方法调整我的方法。

算法是O(n log m)如果tree2是平衡的（O(n m)否则）其中n是tree1和[=22的节点数=]节点数tree2

判断第一棵树是否是第二棵树的子集

Find if the first tree is a subset of the second tree

c

tree

binary-tree

subtree