Деревья выражения как бинарные деревья

Question

У меня простой вопрос.

Почему все деревья выражений смоделированы как "двоичные деревья", а не как "N-деревья"?

Есть ли причина, по которой выражение не может быть смоделировано с использованием N-арного дерева?

Answer 1

Есть несколько веских причин, по которым деревья выражений часто бывают двоичными:

1. Наиболее распространенные деревья выражений представляют арифметические операции (+, -, *, /) или логические предикаты (AND, OR, NOT, XOR). Есть все двоичные (и унарные) операции, поэтому двоичные деревья имеют смысл. Вы можете иметь, например, н-ар +, но это только усложняет вещи без уважительной причины.

2. С более теоретической точки зрения, если у вас есть n-арное дерево, вы можете представить его, используя эквивалентное двоичное дерево, не теряя ничего. Используя n-ary + Например, следующие деревья (один n-арный и один двоичный) можно считать одинаковыми:

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

С другой стороны, есть библиотеки, которые используют n-арные деревья выражений, где они имеют смысл. Например, деревья выражений C# (из System.Linq.Expressions namespace) использовать n-арные деревья для выражения вызова. Итак, выражение f(a, b, c) будет представлен как InvocationExpression это выглядит так:

  f
 /|\
a b c

Answer 2

Почему все деревья выражений смоделированы как "двоичные деревья", а не как "N-деревья"?

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

Есть ли причина, по которой выражение не может быть смоделировано с использованием N-арного дерева?

Они есть.