Restauration d'un arbre binaire entier par ses résultats de parcours de traversée

Question

Puis-je restaurer un arbre binaire complet (count (sommets) = 2^n-1) uniquement à partir d'un tableau trié comme si j'avais effectué une traversée de post-commande?

L'algorithme que je suggère est très simple, il suffit de faire postorder traversal:

1. aller à gauche
2. aller droit
3. current_vertex = array [i ++]; // initialisé i = 0

qui devrait faire le travail, n'est-ce pas?

Answer 1

Non vous ne pouvez pas comme post order array d'un binary tree peut être converti en plus d'un arbres binaires qui ne sont pas même d'où il est impossible de savoir lequel était original.

Exemple-

Poster tableau 2 3 5 peuvent ordonna être convertis en de nombreux arbres comme-

2  // 3 is right child of 2 and 5 of 5 
    3 
    5 

ou

5  //2 is left child and 3 is right child of 5 
2 3