конструирането на дърво, като се има предвид, че е в ред, е достатъчно лесно. Но да кажем, че трябва да конструирате дърво въз основа на неговата предварителна поръчка (+ + y z + * x y z например).
Лесно е да се види, че + е коренът и как да продължите в лявото поддърво оттам. Но.. как да разберете кога трябва да "превключите" към дясното поддърво?
Обикновено inorder се счита за труден случай.
За предварителна поръчка ще имате просто граматика като тази.
expr ::= operator expr expr | var
Оператор е последван от точно два добре оформени израза. Това може да бъде анализирано лесно с помощта на рекурсия
Ако анализирате дърво и получите променлива, върнете променливата. Ако анализирате дърво и получите оператор, анализирайте двете следващи дървета като дясно/ляво поддървета.
