Comment imprimer un infixe à partir d'un arbre d'expression binaire avec les parenthèses nécessaires?

Question

Je travaille sur l'impression d'une expression infixe à partir de mon arbre binaire. Cependant, je peux afficher le formulaire entièrement sous forme de parenthèses, mais la question consiste à imprimer uniquement les parenthèses nécessaires.

Par exemple, considérons l'expression 7 2 8 - - 9 3 * +. Le formulaire de Postfix peut être imprimé en pleine parenthésée:

((7 - (2 - 8)) + (9 * 3)) 

Ou il peut être imprimé avec des parenthèses nécessaires:

7 - (2 - 8) + 9 * 3 

Ce que je Codé pour c'est ...

public Node root; 

public void infix() { 
    infix(root); 
} 

public void infix(Node r) { 
    if (r != null) { 
     if (r.left != null && r.right != null) { //Check if it is a leaf 
      System.out.print ("("); 
     } 
     infix(r.left); 
     System.out.print(r.data); 
     infix(r.right); 
     if (r.left != null && r.right != null) { //Check if it is a leaf 
      System.out.print (")"); 
     } 
    } 
} 

Mais Je n'ai aucune idée de comment faire cela. Quelqu'un pourrait-il m'aider s'il vous plaît?

Answer 1

Pour cela, vous avez besoin du concept de «niveau de priorité» de l'opérateur actuel. Par exemple, à la racine ou lorsque l'opérateur en cours est + ou -, le niveau est 0, mais lorsque l'opérateur actuel est * ou /, le niveau est 1. Vous devez ajouter le niveau actuel en tant que paramètre à la méthode récursive . Vous savez alors que vous avez besoin de parenthèses lorsque l'opérateur interne (par exemple +) a un niveau de priorité inférieur à celui de l'opérateur externe (par exemple, *).