Construire un arbre d'expression binaire

algorithm expression-trees

Question

Quelqu'un pourrait-il expliquer comment construire un arbre d'expression binaire?

Par exemple, j'ai une chaîne 2*(1+(2*1)); Comment convertir cela en un arbre d'expression binaire.

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 1

Réponse populaire

Convertir infixe en postfixe ou préfixe

L'entrée postfixe est: ab + cde + **

  1. Considérer le premier caractère s'il ne s'agit pas d'un symbole puis créer un noeud l'ajouter à la pile
  2. Si le caractère est un symbole, créez un noeud avec des éléments de symbole et ajoutez-le à gauche et à droite du symbole
  3. Poussez le nœud de symbole dans la pile.
  4. Répéter les étapes 1, 2 et 3 jusqu'à ce que l'itérateur n'ait plus d'éléments

Implémentation Java

public Tree.TreeNode createExpressionTree(){
    Iterator<Character>itr = postOrder.iterator();
    Tree tree = new Tree();
    NodeStack nodeStack = new NodeStack();
    Tree.TreeNode node;
    while (itr.hasNext()) {
        Character c = itr.next();
        if(!isDigit(c)){
            node = tree.createNode(c);
            node.right = nodeStack.pop();
            node.left = nodeStack.pop();
            nodeStack.push(node);
        }else{
            node = tree.creteNode(c);
            nodeStack.push(node);
        }
    }
    node = nodeStack.pop();
    return node;
}

Plus d'infos: http://en.wikipedia.org/wiki/Binary_expression_tree



Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow