使用InOrder遍历打印二叉树没有歧义

Question

我想使用按顺序遍历（在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 
     } 
    } 

这是我第一次堆栈溢出，去容易对如果我没有正确发帖:)

Answer 1

我想出来了，例如，输入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 
     } 

    } 
}