algorithme de programmation de structure de données

Question

comment dessiner des arbres binaires dont la liste de précommande est abcdefgh et dont la liste de post-commande est dcbgfhea.also, liste les nœuds d'arbres binaires dans l'ordre inorder et de niveau?

Answer 1

Arbre:

  a 
     /\ 
      b e 
     //\ 
     c f h 
    //
     d g 

afinde:

dcbagfeh

ordre de niveau

(c.-à-BFS):

abecfhdg

Answer 2

Voici un programme Python simple qui génère possible afinde listes basées sur les listes de pré-commande et de post-commande.

from itertools import product 

def inorders(pre, pos): 
    if not pre: return [""] 
    ret = [] 
    if pre[0] == pos[-1]: 
    for left_size in range(len(pre)): 
     left = inorders(pre[1:left_size+1], pos[:left_size]) 
     right = inorders(pre[left_size+1:], pos[left_size:-1]) 
     for l, r in product(left, right): 
     ret.append(l + pre[0] + r) 
    return ret 

Et voici la sortie pour votre cas:

>>> inorders("abcdefgh", "dcbgfhea") 
['bcdafgeh', 'bcdagfeh', 'bdcafgeh', 'bdcagfeh', 'cdbafgeh', 'cdbagfeh', 'dcbafgeh', 'dcbagfeh']