c-查找第一棵树是否是第二棵树的子集

Question

我查看了互联网上的所有内容，以了解如何检查一棵树是否是另一棵树的子集。所谓子集，我的意思是，如果第一棵树的所有元素都出现在第二棵树中，那么issubset函数应该是return 1否则为CCD_ 3。请注意，根据元素的插入顺序，具有相同元素集的两个树可能具有非常不同的形状。以树形式给出以下示例：

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

我不确定我是否理解你的问题，但我仍然试图给你我的答案。从您的例子中，我假设您使用的是二进制搜索树。但我不知道你用的是什么样的二叉树，我假设是一个通用的方案。我想如果树是平衡的，那么也许你可以得到一个更好的算法。

由于您有二进制搜索树，因此可以假设函数search(root, key)，如果找到了包含key的节点，则返回一个指向该节点的有效指针，否则返回NULL。

此外，我假设您知道每棵树的节点数。因此，如果tree1的节点数少于tree，则可以返回0。否则，方法如下：

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);    
}

我更喜欢使用指向节点的简单指针，而不是双指针。我想你可以使我的方法适应你的。

如果tree2是平衡的，则算法为O(n log m)（否则为O(n m)），其中n是tree1的节点数，m是tree2 的节点数

Answer 2

二进制搜索树支持对元素进行高效的排序迭代。以不递减的顺序在每棵树的元素上维护一个迭代器。重复以下操作，直到确定结果：

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

基本实现是最坏情况O(n + m)，其中n和m分别是两个树的大小。通过上述优化，如果较大的树是平衡的，则可以通过O(n log m)将其额外绑定，如果第二棵树比第一棵树大得多，则这很有用。（无论树是否平衡，O(n + m)边界仍然适用。）