Печать двоичного дерева с использованием обхода InOrder без неоднозначности

Я пытаюсь распечатать двоичное дерево, используя обход по порядку (в java), но без какой-либо двусмысленности.

Я создал дерево из ввода нотации пост-заказа.

Например, input = 2 3 4 * - 5 + Я затем создаю дерево и хочу распечатать его, используя обход по порядку.

Таким образом, вывод должен быть = 2 - (3 * 4) + 5. Однако использование обхода по порядку, очевидно, не дает мне разделяющих скобок.

Мой вопрос: могу ли я распечатать результат так, как я хочу, не вмешиваясь в базовые классы BinaryNode и BinaryTree, а только изменяя класс драйвера? И если да, то как мне это сделать?

Если я могу сделать это, только изменив свой метод printInOrder (в классе BinaryNode), это то, как это выглядит до сих пор:

public void printInOrder()
    {
        if (left != null)
        {
            left.printInOrder();            // Left
        }
        System.out.print(element);       // Node
        if (right != null)
        {
            right.printInOrder();           // Right
        }
    }

Это мой первый раз на Stack Overflow, полегче со мной, если я публиковал неправильно :)


traversal binary-tree inorder ambiguity
person alexcohenza    schedule 06.03.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я понял это, поэтому, например, ввод 23 + 4 + 5 * даст результат (((2 + 3) +4) * 5)

См. Код ниже:

//NOTE: printInOrder has been modified to exclude ambiguity
public void printInOrder()
{
    if (left != null)
    {
        if (height(left)== 0)
        {
            //when we reache the bottom of a node, we put a bracket around each side as we know this will have it's own operation
            // eg:  *
            //     / \
            //    3   4
            System.out.print("("); 
            left.printInOrder();            // Left
        }
        else
        {
            // We also put in a bracket here as this matches the closing brackets to come (which we do not know about yet)
            System.out.print("(");
           left.printInOrder();            // Left 
        }

    }
      System.out.print(element);                // Node
    if (right != null)
    {
        if (height(right) == 0)
        {
            //when we reache the bottom of a node, we put a bracket around each side as we know this will have it's own operation
            // eg:  *
            //     / \
            //    3   4
            right.printInOrder();           // Right
            System.out.print(")");
        }
        else
        {
            right.printInOrder();           // Right
           // System.out.print(")"); // this print statement actually isnt necessary
        }

    }
}
person alexcohenza    schedule 09.03.2013