Tournage d'un Arbre Binaire à un tableau trié

Est-il un moyen de transformer un Binaire à un tableau trié sans avoir à traverser de l'arbre pour chaque index de tableau?

Node root;
Node runner;
int current_smallest;

void findsmallest(Node root){
    //Pre-order traversal
    if(root == null){
        return;
    }else{
        runner = root;
        if(current_smallest == null){
            current_smallest = runner.element;
        }else{
            if(current_smallest > runner.element){
            current_smallest = runner.element;
            }
        }
        findsmallest(runner.left);
        findsmallest(runner.right);
    }   
}

void fill_array( int [] array ){

    for(int i =0; i < array.length(); i++){
        findsmallest(root);
        array[i] = current_smallest;
    }
}

Comme vous pouvez le voir, cela peut être prendre un certain temps si il y a beaucoup de nœuds dans l'arbre.
Btw, j'ai oublié de montrer que l'ensemble de l'arbre doivent être parcourus au début pour obtenir la longueur du tableau.

OriginalL'auteur Adegoke A | 2013-04-23

  1. 13

    Oui, vous pouvez le faire: exécuter une dans l'ordre de la traversée de l'arbre, garder la position actuelle de la matrice, et de stocker la valeur du nœud à la position actuelle de la matrice.

    Vous pouvez le faire dans l'ordre de la traversée de manière récursive, ou vous pouvez le faire avec une pile de structure de données. Si vous voulez le faire de manière récursive, vous pouvez le faire:

    int fill_array(Node root, int [] array, int pos) {
    if (root.left != null) {
        pos = fill_array(root.left, array, pos);
    }
    array[pos++] = root.element;
    if (root.right != null) {
        pos = fill_array(root.right, array, pos);
    }
    return pos; //return the last position filled in by this invocation
}

    Noter que dans le but pour le dessus de procédure récursive pour le travail, l'appelant doit allouer suffisamment d'espace dans la array transmis à la fonction.

    OriginalL'auteur dasblinkenlight

  2. 4

    Ce que vous voulez, c'est un ordre de la traversée, qui est généralement mis en œuvre de manière récursive comme:

    • Traverser à gauche de la sous-arborescence.
    • Poignée de ce nœud (ie. insérer l'élément suivant dans votre tableau)
    • Traverser à droite de la sous-arborescence.

    OriginalL'auteur femtoRgon

  3. 3

    Un arbre binaire peut être représenté dans un tableau; si tel était le cas, tout ce que vous devez faire est de trier le tableau.

    Voici quelques infos sur la représentation de l'arbre dans le tableau: wikipédia

    Ce n'est pas nécessairement la plus efficace en terme d'espace de représentation; les "nœuds avec des références de la" représentation peut déchets de moins d'espace.

    OriginalL'auteur Tom