Convertir un arbre d'expression N-aire en un arbre binaire

Question

J'ai une générique N-ary expression arbre et je veux convertir la même chose en arbre binaire. Y a-t-il des algorithmes bien définis pour faire la même chose?

J'ai essayé d'utiliser différents algorithmes de conversion de l'arbre N-ary en arbre d'expression comme https://groups.google.com/forum/?fromgroups#!topic/wncc_iitb/RrgohUZ-uhw mais ça ne marchera pas, car ils ne se soucient pas de la précédence et de tout.

Merci.

Answer 1

Réponse simple. Étape 1: Convertir l'arbre d'expression N-aire avec différents niveaux de priorité en un arbre N-aire où chaque nœud n'a qu'un seul niveau de préséance.

Étape 2: Convertissez cet arbre en arbre binaire. Si vous cherchez une solution simple plutôt qu'une solution efficace, il peut être facile d'exploser chaque nœud en niveaux correspondant à votre priorité, puis après avoir fait disparaître un arbre binaire sur les nœuds évidemment inutiles. Si vous voulez une solution plus efficace, alors vous voudrez être plus prudent dans l'expansion initiale.