c# - 递归创建数学表达式二叉树

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;
}

我曾尝试以与生成字符串相同的方式创建一棵树，但无法使其以任何常识方式工作。我使用的是 binary tree class found on 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 )可能是有意义的，但这取决于您究竟想用它们做什么。

编辑:@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);
}