Как сравнить форму одного SortedSet с другим в C #

Я пытаюсь сравнить форму (по форме, я имею в виду форму двоичного дерева) одного SortedSet по определенному индексу List of SortedSets со всеми остальными SortedSets в том же List. Я пытался найти способы сравнить двоичные деревья, но не знаю, как это сделать с помощью 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 основан на этом другом вопрос о сравнении двоичных деревьев. Извините, если это сложно понять. Буду признателен за любую помощь, которую я могу получить.


c# compare binary-tree sortedset
person Snaps56    schedule 27.01.2018    source источник
comment
Первый вопрос, который нужно задать: как реализовать BinaryTree с .NET. Рассматриваемый код не компилируется с System.Collections.Generic.SortedSet   -  person Risto M    schedule 27.01.2018
comment
Да. Код не компилируется, потому что он пытается выполнить рекурсию с неверными значениями для параметров compareShape. Я просто вставил то, что считал правильной идеей, но не уверен, что дальше.   -  person Snaps56    schedule 28.01.2018
comment
Я изучал возможность реализации двоичного дерева, но если бы я это сделал, мне пришлось бы переписать всю мою программу. Вместо этого я хочу посмотреть, смогу ли я закончить это тем, что у меня есть.   -  person Snaps56    schedule 28.01.2018
comment
Я сделал ответ, где, надеюсь, вы можете получить представление о функции рекурсивного сравнения. Я не включил ваш цикл for в рекурсивную функцию, потому что он слишком усложнил его. У вас может быть цикл for вне функции поиска. Надеюсь, это вам поможет.   -  person Risto M    schedule 28.01.2018

Ответы (1)


arrow_upward
0
arrow_downward

Вот пример реализации метода сравнения форм с воображаемым классом BinaryTree.

Рекурсивная функция работает лучше всего, когда она настолько проста, насколько это возможно, и когда нет никакой дополнительной логики. В свой алгоритм вы пытались включить цикл массива и из-за этого стали чрезмерно сложными.

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, вы можете начать использовать ее в более сложных алгоритмах.

person Risto M    schedule 28.01.2018