java - 作为二叉树的表达式树

Question

我有一个简单的问题。

为什么所有表达式树都建模为“二叉树”而不是“N 叉树”？

有什么原因导致表达式无法使用 N 叉树建模吗？

Answer 1

表达式树通常是二元的有一些很好的理由:

1. 最常见的表达式树表示算术运算(+、-、*、/)或逻辑运算谓词(AND、OR、NOT、XOR)。都有二元(和一元)运算，因此二叉树最有意义。例如，您可以使用n元+，但这只会让事情变得复杂而没有充分的理由。

2. 从更理论的角度来看，如果你有一个 n 叉树，你可以使用等效的二叉树来表示它，而不会丢失任何东西。使用 n 元 + 示例，可以将以下树(一个 n 元和一个二进制)视为相同:

     +       +
    /|\     / \
   a b c   +   c
          / \
         a   b
   

另一方面，有些库在有意义的地方使用 n 元表达式树。例如，C# 表达式树(来自 System.Linq.Expressions 命名空间)使用 n 元树作为调用表达式。因此，表达式 f(a, b, c) 将表示为 InvocationExpression，如下所示:

  f
 /|\
a b c