arbre binaire de traversée de précommande avec des enfants absents spécifiés

Question

J'ai un arbre binaire représenté par une traversée de pré-commande, qui ressemble à ceci: {1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }, où un 0 indique l'absence d'enfant d'un élément.

Comment puis-je construire l'arborescence binaire d'origine à partir de ces données? J'ai essayé de résoudre le problème avec la récursion, mais je n'ai pas réalisé comment traiter les enfants droits des nœuds, car je ne peux pas calculer leur position dans le tableau à moins qu'ils aient une feuille comme parent (le cas deux zéros après, qui indiquent qu'il n'a pas d'enfants).

J'ai l'impression que la solution doit être assez facile, mais je ne la vois toujours pas.

Answer 1

Quelque chose de simple comme ceci peut fonctionner pour vous. Vous avez juste besoin de re construire l'arbre dans une interprétation de pré-commande de la séquence d'entrée. Le code suivant ne valide pas la séquence d'entrée pour vérifier qu'il s'agit d'une représentation arborescente valide.

struct BTNode { 
    int data; 
    BTNode* left; 
    BTNode* right; 
} 

BTNode* BuildTree(int* sequence, int& pos) { 
    int value = sequence[pos++]; 
    if (value == 0) 
     return nullptr; 
    BTNode* node = new BTNode; 
    node->data = value; 
    node->left = BuildTree(sequence, pos); 
    node->right = BuildTree(sequence, pos); 
    return node; 
}