Tri par insertion d'arbre binaire dans C

Question

Hey quelqu'un peut-il expliquer comment trier un arbre binaire en utilisant le tri d'insertion en langage C où la complexité en temps est un problème. J'apprends juste à coder. Merci les gars!

Answer 1

Si vous avez codé l'arbre binaire au sens traditionnel, lorsque vous ajoutez des éléments à l'arborescence, il conserve l'ordre trié. Vous pouvez obtenir la liste complète des éléments dans l'ordre en traversant l'arbre. Je vous recommande de lire:

• http://en.wikipedia.org/wiki/Tree_traversal

• http://en.wikipedia.org/wiki/Binary_tree

Jetez aussi un oeil à: http://nova.umuc.edu/~jarc/idsv/lesson1.html

Answer 2

Il convient de noter qu'il ya une certaine terminologie à utiliser ici. Un arbre binaire est une structure de données dans laquelle chaque nœud a au plus deux enfants. Il n'y a pas de conventions pour la commande de nœuds dans un arbre binaire.

Un arbre de recherche binaire est un arbre binaire tel que pour donné un noeud N tous les nœuds du sous-arbre gauche de N sont considérés comme « moins de » N et tous les nœuds du sous-arbre droit de N sont considérés comme « supérieure "N. Vous pouvez également laisser des nœuds considérés comme" égaux à "N dans l'arbre, à condition que vous les définissiez de façon cohérente pour être placés dans le sous-arbre gauche ou le sous-arbre droit. Comme d'autres l'ont suggéré, le mieux est de modifier le code pour construire un arbre de recherche binaire au lieu d'un arbre binaire normal, ou convertir l'arbre binaire en une structure de données linéaire et le trier.

Answer 3

#include <stdio.h> 
#include <malloc.h> 
#define FIN "algsort.in" 
#define FOUT "algsort.out" 

struct Node { 
    int val; 
    struct Node *left; 
    struct Node *right; 
}; 

typedef struct Node node; 

void insert(node **bt, node *Node) { 

if(!(*bt)) { 

    *bt = Node; 

} else { 

     if(Node->val < (*bt)->val) 

      insert(&((*bt)->left), Node); 

     else 

      insert(&((*bt)->right), Node); 
} 
} 

void printout(struct Node *node) { 

    if(node->left) printout(node->left); 

    printf("%d ", node->val); 

    if(node->right) printout(node->right); 
} 

void postorder(struct Node *node) { 

     if(node->left) printout(node->left); 

     if(node->right) printout(node->right); 

     printf("%d ", node->val); 
} 

int main() { 

    int i, n, elem;  

    node *curr; 

    freopen(FIN, "r", stdin); 

    freopen(FOUT, "w", stdout); 

    node *bt = NULL; 

    scanf("%d", &n); 

    for(i = 0; i < n; ++i) { 

     scanf("%d", &elem); 

     curr = malloc(sizeof(struct Node)); 

     curr->val = elem; 

     curr->left = NULL; 

     curr->right = NULL; 

     insert(&bt, curr); 

    } 

    printout(bt); 

    return(0); 
    } 

Disons que algsort.in contient le tableau suivant des entiers:

algsort.int -> 9,8,7,6,5,4,3,2,0,1, - 1;

algsort.out -> -1,0,1,2,3,4,5,6,7,8,9