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

Question

我在 Internet 上搜索了所有内容，以了解如何检查一棵树是否是另一棵树的子集。对于子集，我的意思是如果第一棵树的所有元素都出现在第二棵树中，issubset 函数应该返回 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

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

因为你有二叉搜索树，你可以假设一个函数 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 m) 否则)，算法是 O(n log m) 其中 n是tree1的节点数，m是tree2

的节点数