Рекурсивное создание математического выражения двоичного дерева

Question

Всем днем,

Я реализовал простое двоичное дерево в C #, я собираюсь использовать его для рекурсивного создания деревьев математических выражений.Но я сталкиваюсь с проблемами, так как прошли годы с тех пор, как мне приходилось делать рекурсивные вызовы, я изо всех сил стараюсь понять, почему следующее работает только для двоичных деревьев глубины 2, а не для деревьев большей глубины.

Конечно, если рекурсия была правильной, она должна иметь возможность строить деревья на глубину n.Вот код:

Node<T> f;
Node<T> t;
Node<T> subRoot;
Node<T> root;

////Only works with trees of depth 2.

private Node<T> Tree(List<T> prefixBank, int maxDepth)
{
    if (prefixBank.Count != 0)
    {
        if (maxDepth == 0)
        {
            t = new Node<T>(prefixBank[0]);
            subRoot.Add(t);

            prefixBank.Remove(prefixBank[0]);
        }
        else
        {
            if (root == null)
            {
                root = new Node<T>(prefixBank[0]);
                prefixBank.Remove(prefixBank[0]);
                Tree(prefixBank, maxDepth - 1);
            }

            f = new Node<T>(prefixBank[0]);

            if (isOperator(f))
            {
                root.Add(f);
                prefixBank.Remove(prefixBank[0]);
                subRoot = f;
            }

            for (int i = 0; i < 2; i++)
            {
                Tree(prefixBank, maxDepth - 1);
            }
        }
    }
return f;
}

Приведенная выше функция принимает список символов, которые образуют префиксное математическое выражение (например, * + 3 4 - 5 6).Раздражающе я рекурсивно создаю выражение префикса, используя этот код:

string prefixExpression = String.Empty;

private string generateExpression(Random rand, GenerationMethod generationMethod, int maxDepth)
{
    if ((maxDepth == 0) || ((generationMethod == GenerationMethod.Grow) && (rand.NextDouble() < randomRate)))
    {
        operand.GenerateValue(Type.Terminal, rand);
        prefixExpression += " " + operand.Value;
    }
    else
    {
        operator.GenerateValue(Type.Function, rand);
        prefixExpression += " " + operator.GeneValue;

        //2 is the arity of the function right an arity checker function so that unary operators can be utilised
        for (int i = 0; i < 2; i++)
        {
            generateExpression(rand, generationMethod, maxDepth - 1);
        };
    }
    return prefixExpression;
}

Я пытался создать дерево таким же образом, как я сгенерировал строку, но не могу заставить его работать любым здравым смыслом.Я использую слегка модифицированную версию класса двоичного дерева, найденную в MSDN .Я изменил его, добавив функцию добавления, которая автоматически добавляется в левое или правое поддерево, поэтому мне не нужно указывать Root.Left.Left.Left и т. Д., Как в этом примере для создания дерева.

Если бы какое-либо тело могло помочь мне исправить мой рекурсивный код создания дерева, чтобы он работал для деревьев n глубины, я был бы очень признателен.Я относительно новичок в C #, поэтому я прошу прощения, если что-то выше немного схематично.

Answer 1

Вы не должны полагаться на глобальные переменные, когда делаете подобные рекурсивные вызовы (и в общем случае область действия ваших переменных должна быть как можно более узкой, кажется, нет никаких причин для f и t быть переменными уровня класса).Ваш код не имеет особого смысла для меня, но я предполагаю, что основная проблема заключается в том, что вы добавляете каждый узел непосредственно в корень.Я бы сделал это так:

public Node<T> Tree(Queue<T> prefixBank)
{
    var node = new Node<T>(prefixBank.Dequeue());

    if (isOperator(node))
    {
        for (int i = 0; i < 2; i++)
        {
            node.Add(Tree(prefixBank));
        }
    }

    return node;
}

Я не вижу особой причины, чтобы иметь там maxDepth, но если вы действительно этого хотите, это должно быть тривиально.

Кроме того, может иметь смысл иметь иерархию наследования узлов (например, NumberNode, OperatorNode), но это зависит от того, что именно вы хотите с ними делать.

EDIT : @Eric, не очень.Я могу использовать IEnumerator<T> вместо Queue<T> (что, теперь, когда я об этом думаю, в любом случае, вероятно, является лучшим выбором).И я должен отложить создание результата до конца, что также означает, что я должен изменить isOperator() для работы на T, а не Node<T>.

public Node<T> Tree(IEnumerable<T> prefixBank)
{
    return Tree(prefixBank.GetEnumerator());
}

public Node<T> Tree(IEnumerator<T> enumerator)
{
    enumerator.MoveNext();
    var value = enumerator.Current;

    var children = new List<Node<T>>(2);

    if (isOperator(value))
    {
        for (int i = 0; i < 2; i++)
        {
            children.Add(Tree(enumerator));
        }
    }

    return new Node<T>(value, children);
}