Comment transférer un arbre binaire (pas un arbre équilibré) sur deux systèmes différents de manière efficace, conservant sa structure complète?
5 Réponses :
La manière évidente serait de convertir votre arborescence binaire en une gamme de nœuds, remplaçant chaque pointeur dans l'arborescence d'origine avec un index à un nœud de la matrice. Vous pouvez ensuite transmettre ce tableau et, à l'autre extrémité, reconstruisez un arbre avec une structure identique.
Cette structure donnée ci-dessous
(X,(L,-,(P,-,-)),(R,-,-))
Pour les arbres arbitraires, le '-' n'est pas nécessaire. (X, (l, (p)), (r)) ferait. Ou n'est-ce pas?
Définir des fonctions de sérialisation.
void serialize( FILE *f, my_tree *node, _Bool is_root ) {
if ( node == NULL ) {
fputc( no_child, f );
return;
}
if ( ! is_root ) fputc( data_prefix, f );
write_data( f, node->data );
fputc( data_terminator, f );
write_data( node->left_child );
write_data( node->right_child );
}
void deserialize_node( FILE *f, my_tree *node ) {
node->data = read_data_field( f );
if ( fgetc( f ) != no_child ) {
node->left_child = calloc( 1, sizeof( my_tree ) );
deserialize( f, node->left_child, false );
}
if ( fgetc( f ) != no_child ) {
node->right_child = calloc( 1, sizeof( my_tree ) );
deserialize( f, node->right_child, false );
}
}
Le problème principal avec ceci est que vous devez remplacer les pointeurs ou les références de votre représentation en mémoire avec quelque chose d'autre qui peut être utilisé pour représenter sans ambiguïté le nœud qui a été signalé.
(foo
(cat
()
(dog
()
()
)
)
(zebra
()
()
)
)
Approche 1: Nous pouvons traverser deux fois l'arbre:
inadorder code> Traversal LI>
- Deuxième fois pour obtenir le
Posterner Code> Traversal LI>
OL> Maintenant, en utilisant ces deux listes à destination, nous pouvons reconstruire l'arbre binaire comme suit: p> xxx pré> pour obtenir le inonder code> TRAVERSAL: P> Input:
12
/
13
Output: 12 13 -1 -1
Input:
20
/ \
8 22
Output: 20 8 -1 -1 22 -1 -1
Input:
20
/
8
/ \
4 12
/ \
10 14
Output: 20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1
Input:
20
/
8
/
10
/
5
Output: 20 8 10 5 -1 -1 -1 -1 -1
Input:
20
\
8
\
10
\
5
Output: 20 -1 8 -1 10 -1 5 -1 -1
Est-ce un arbre de recherche binaire ou juste un arbre binaire?
Veuillez fournir des détails sur la structure de mémoire utilisée pour stocker l'arborescence. Par exemple. utilisez-vous un bloc de mémoire contigu? Appelez-vous
MALLOC pour chaque bloc de données individuel dans l'arborescence? Où réside le pointeur root?+1 juste parce que je ne pense pas que cela mérite les bowvotes. La question n'est pas ambiguë.