多元二叉搜索树

Question

我需要创建多棵树以便比较它们的形状并计算有多少不同的形状[=我得到了 63=] 棵树（相同的形式将被计为一种形式）。

输入将为：

trees（需要多少棵树（从1到50）layers（一棵树有多少个节点（从 1 到 20)

值（每棵树的值（从 1 到 1000000））

带图片输入：

5 3 3 8 2 4 2 5 2 6 10 3 7 6 10 8 4

必须有五棵树，每棵树有三个个节点。 [![在此处输入图片描述][1]][1]

前两棵树是一样的形状，其他的不一样

输出：4

输入示例：

2 2 1 2 2 1

所以必须有两棵棵树，每棵树有两个个节点。

答案是 2 因为可以有 2 种不同形式的树

另一个输入示例：

6 7 7 6 3 5 4 2 1 1 3 2 4 7 5 6 4 7 1 2 5 3 6 5 1 6 7 2 4 3 1 3 2 5 6 4 7 6 7 1 5 4 2 3

答案：6

我能够用该结构创建一棵树，但我不知道如何创建多个以及如何比较它们的形状

也许我不需要多棵树。也许我会创建一棵树，向其写入值，然后以某种方式“保存”其形状，清除它，然后向其写入下一棵树。

最好的方法是什么？

更新： 我怎样才能正确地释放分配的内存？（我知道 free() 但我不知道在这种情况下如何使用它）

Answer 1

Pseudo-code（评论太长）：

bool SameShape(node* tree1, node* tree2)
{
  if (isNull(tree1))
    if isNull(tree2))
      return true;
    else
      return false;
  else
    if (!isNull(tree2))
      return false;
  if (isNull(tree1->left) != isNull(tree2->left))
    return false;
  if (isNull(tree1->right) != isNull(tree2->right))
    return false;
  bool same = true;
  if (!isNull(tree1->left))
    same = SameShape(tree1->left, tree2->left);
  if (same && !isNull(tree1-right)
    same = SameShape(tree1-right, tree2->right);
  return same;
}

}

Answer 2

比较函数：

bool IdenticalTreeShape(struct node *tree1, struct node *tree2)
{
    if (!tree1 && !tree2) {
        return true;
    }
    if (  (!tree1)
        ||(!tree2)
        ||(!IdenticalTreeShape(tree1->left, tree2->left)
        ||(!IdenticalTreeShape(tree1->right, tree2->right) ) {
        return false;
    }
    
    return true;
}

现在，您需要保留找到的每个 uniq 形状，以查看新命题是否为 uniq。您可以通过多种方式做到这一点。

例如：

有一个数组arrayUniq，其中包含您要输入的树的数量。将整数 nbUniq 设置为 0。

在 arrayUniq[nbUniq]

中输入并创建树

比较从“0”到“nbUniq - 1”的所有树形与 arrayUniq[nbUniq]。如果 none 树相同，则增加 nbUniq。

完成:)

多元二叉搜索树

Multiple binary search tree

c

binary-search-tree