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

Question

我有一个简单的问题。

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

是否有任何理由无法使用 N-ary 树对表达式进行建模？

Answer 1

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

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

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

Answer 2

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

他们不是。表达式树的内部节点是运算符，运算符可以是一元、二元或三元，至少，也许更多。

是否有任何理由无法使用 N-ary 树对表达式进行建模？

他们是。