Деревья выражений как двоичные деревья

Question

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

Почему все деревья выражений моделируются как «Двоичные деревья», а не как «N ary trees»?

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

Answer 1

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

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

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

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

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

f 
/|\ 
a b c 

Answer 2

Почему все деревья выражений моделируются как «Бинарные деревья», а не как «N ичных деревьев»?

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

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

Они есть.