Как напечатать двоичное дерево функций / терминалов, как оператор lisp?

Question

У меня есть двоичное дерево функций и значений терминалов. Я хотел бы напечатать это дерево, так как будет представлен оператор lisp!

Например, дерево с корнем "+" и терминалами "2" и 4 "будет иметь вид (+ (2 4)).

Answer 1

Вам нужно сделать предварительный обход двоичного дерева. Итак, если у вас есть дерево:

      +
  5       -
        3   2

Вы хотели бы посетить +, 5, -, 3, 2, в этом порядке. Вы можете сделать это рекурсивно следующим образом (при условии, что у ваших узлов есть значения полей, left и right):

  public void preorder() {
    if (leaf == null && right == null) 
      System.out.println(value);
    else {
      System.out.println("(");
      System.out.println(value);
      if(left != null) left.preorder();
      if(right != null) right.preorder();
      System.out.println(")");
    }
  }

Обратите внимание, что вы просто посещаете текущий узел, затем левого потомка, затем правого потомка.