如何在 C# 中将一个 SortedSet 的形状与另一个进行比较

Question

我正在尝试比较一个 SortedSet 在 SortedSet 列表的某个索引处的形状（按形状，我指的是二叉树的形状）与同一列表中所有其他 SortedSet 的形状。我试图查找比较二叉树的方法，但我不知道如何使用 SortedSets 来代替。（递归也把我搞糊涂了！）

    //Checks shape of the trees
    public static bool compareShape(List<SortedSet<int>> trees, SortedSet<int> currentTree)
    {
        //COMPARE SHAPE WITH REST OF LIST
        for (int i = 0; i < trees.Count(); i++)
        {
            // Empty trees are equal
            if (trees[i] == null && currentTree == null)
            {
                return true;
            }

            // Empty tree is not equal to a non-empty one
            if ((trees[i] == null && currentTree != null) || (trees[i] != null && currentTree == null))
            {
                return false;
            }

            // otherwise check recursively
            return compareShape(trees[i].left(), currentTree.left()) && compareShape(trees[i].right(), currentTree.right());
        }

    }
}

'for' 循环中的代码灵感来自 this 其他关于比较二叉树的问题。对不起，如果这有点难以理解。如果能得到任何帮助，我将不胜感激。

Answer 1

这是使用假想二叉树-class 进行形状比较方法的示例实现。

递归函数在尽可能简单并且不包含任何额外逻辑的情况下效果最好。在您的算法中，您试图包含数组循环并因此变得过于复杂。

public abstract class BinaryTree<T>
{
    public T Data { get; set; }
    public BinaryTree<T> Left { get; set; }
    public BinaryTree<T> Right { get; set; }
}

/// <summary>
/// Checks shape of the trees
/// </summary>
public static bool CompareTreeShapes(BinaryTree<int> tree1, BinaryTree<int> tree2)
{
    // Empty trees are equal
    if (tree1 == null && tree2 == null)
    {
        return true;
    }
    // Empty tree is not equal to a non-empty one
    if ((tree1 == null) != (tree2 == null))
    {
        return false;
    }
    // Otherwise check recursively both parts: left and right
    return CompareTreeShapes(tree1.Left, tree2.Left) && CompareTreeShapes(tree1.Right, tree2.Right);
}

现在当您拥有 CompareTreeShapes 函数时，您可以开始在更复杂的算法中使用它。

如何在 C# 中将一个 SortedSet 的形状与另一个进行比较

How to compare the shape of one SortedSet to another in C#

c#

binary-tree

compare

sortedset