Этот код, по-видимому, реализует нотацию Reverse poli sh , то есть нотацию, в которой операторы следуют за своими операндами. Он читает выражение, записанное в RPN, и создает соответствующее двоичное дерево. Например, для дерева над формой RPN будет:
ABC+DE**F+*
Лог c довольно прост и основан на стеке, который содержит узлы дерева:
- Каждый раз, когда вы встречаете операнд (то есть букву), вы создаете новый листовой узел с операндом и кладете его sh в стек.
- Каждый раз, когда вы сталкиваетесь с оператором, вы создаете новый узел оператора, который заменяет два самых верхних узла из стека. Замененные узлы становятся дочерними узлами нового узла.
В конце концов, вы получаете дерево выражений в верхней части стека.
Обновление: Что касается указанных c строк, которые вы упомянули: z - это особый вид узла дерева, Sentinel , который изображен в виде крошечного прямоугольника на картинке. Это бесполезный узел, который позволяет вам знать, когда вы достигнете дна дерева. Другой способ - просто использовать нулевой указатель (приведенная выше ссылка сравнивает подходы).
z->l = z;
z->r = z;
- это то, что делает узел своим дочерним. Стражный узел также может представлять пустое дерево.
Теперь в l oop:
x->info = c;
x->l = z;
x->r = x;
создается новый листовой узел (узлы операндов не имеют дочерних элементов). Если затем мы обнаружим, что узел на самом деле является оператором, дочерние элементы немедленно заменяются операндами из стека.