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

Question

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

3

大家下午好，

我在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上找到）。我将其修改为具有自动添加到左侧或右侧子树的add函数，因此不必像此示例一样指定Root.Left.Left.Left等来创建树。

如果有人能帮助我纠正递归树创建代码，使其适用于n深度的树，我会非常感激。我对C#相对较新，因此如果以上内容有任何模糊之处，请谅解。

- user648132

不是与您的问题相关，但是您应该使用 StringBuilder 而不是像您现在这样连接字符串。 - svick

此外，这种使用 List<T> 的方式非常低效。 - svick

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- svick · Accepted Answer

在进行递归调用时，不应依赖全局变量（通常情况下，变量的作用域应尽可能狭窄，没有理由让 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);
}