Arbre non binaire

Question

Je dois créer un arbre pouvant contenir jusqu'à n sous-nœuds pour chaque nœud (c'est-à-dire, ce n'est pas un arbre binaire).
Comment faire?

Answer 1

Vous cherchez des arbres n-aire - http://oopweb.com/Algorithms/Documents/PLDS210/Volume/n_ary_trees.html La création devrait être assez simple à partir des informations contenues dans ce lien et d'autres (dans google).

Answer 2

Au lieu d'avoir quelque chose comme ceci:

Node* left; 
Node* right; 

que vous le feriez normalement pour un arbre binaire, vous pouvez faire quelque chose comme:

Node** children; 
int size; 

alors malloc la taille appropriée pour le nombre de pointeurs.

Answer 3

GLib fournit un implementation d'arbres N-ary. Si vous ne pouvez pas utiliser glib, vous devriez chercher une autre bibliothèque qui correspond à vos besoins ou lancer votre propre arbre N-aire. Dans une version simple, un nœud contiendrait une liste ou un tableau lié avec des pointeurs vers d'autres nœuds.