1
J'ai regardé du code pour les BST et je peux voir que chaque noeud est une structure. Est-ce nécessaire?Les structs sont-ils nécessaires dans les arbres de recherche binaires?
A
Répondre
7
int flat_tree[ 1000 ][ 3 ];
// for each tree node, value is stored in element [id][0]
// id of left_child stored in element [id][1]
// id of right_child stored in element [id][2]
...
Je ne vais pas aller plus loin avec cela. En règle générale, struct s/class es sont utilisés pour tout type de structure de données liée. Aussi généralement, n'importe quelle caractéristique du système de type peut être vaincue ou ignorée et vous pouvez tout faire (allocation de tas, etc) dans un tableau de int de manière très douloureuse.
+0
Meilleure réponse jusqu'à présent: en même temps, il montre deux réponses. Théoriquement non, pratiquement oui. – MSalters
+0
Une deuxième dimension peut faciliter cela, où les valeurs d'index peuvent être 0 pour gauche, 1 pour données et 2 pour droite. –
+0
@Thomas: relativement parlant, v) – Potatoswatter
4
Non, ce pourrait être une classe. Ce ne peut pas être un primitif, car il doit stocker une valeur et également pointer vers les enfants.
Eh bien, je dois dire que vous pouvez également représenter votre BST comme un tableau, où les enfants gauche et à droite du nœud à la position i sont dans des positions 2 * i + 1 et 2 * i + 2, respectivement. Mais alors vous devriez vous inquiéter du redimensionnement, et vous auriez besoin d'une valeur spéciale pour représenter null, et les opérations de suppression deviennent assez compliquées. Je ne recommande pas cette approche autrement que comme un exercice académique.
+0
Oups, je n'ai pas vu ta réponse. Je pense que vous vouliez dire ** 3 ** * i + 2, cependant. – Potatoswatter
+2
Non, 2 est correct. – danben
+0
3 semble mieux ... Cette confusion est un bon argument pour lequel on devrait utiliser des structs. – Thilo
4
Ce n'est pas obligatoire.
Mais comme les données contenues dans un noeud avec les deux liens forment une entité logique, ils sont généralement rassemblés dans une structure. De sorte qu'il devient plus facile de coder des fonctions qui prennent un noeud en argument ou renvoient un noeud.
1
Non, pas à proprement parler. Dans les jours FORTRAN, les gens utilisaient des tableaux parallèles, ou des tableaux bidimensionnels.
La section «Programmation structurée» de Tony Hoare de Dahl, Dijkstra et Hoare a traité de la structuration des données et des types d'enregistrements.
0
Vous pouvez faire plus simple que les tableaux parallèles si votre charge admet une valeur sentinelle: vous pouvez utiliser un arbre implicite (c'est-à-dire, ne pas du tout avoir de liens).
payload_type a[tree_size];
Juste une longue rangée plane contenant uniquement des valeurs de la charge utile, avec la position dans la matrice de codage pour la structure de liaison:
a[0]est racinea[1]est root-> gauchea[2]est root-> righta[3]est root-> left-> lefta[4]est root-> gauche> droite- ...
Pour le noeud à la position i, aller à 2 * i + 1 pour la gauche et 2 * i + 2 pour le droit
Vous l'initialisez à toutes les valeurs sentinelles, et commencez à ajouter des choses ...
Les structures ne sont pas nécessaires. Vous pouvez utiliser des classes à la place. En C++, les classes par défaut à des membres privés, tout dans la définition de classe avant votre première déclaration publique ou protégée sera privé. Structures, par défaut, les membres sont publics. – Zaki
Que voulez-vous dire par nécessaire? –
Les structures ne sont pas nécessaires. Tout type de données peut être utilisé. Les BST doivent avoir des pointeurs vers les nœuds et les nœuds doivent avoir du contenu (ou ils peuvent être des pointeurs vers des données). Par exemple, vous pouvez avoir un tableau de pointeurs de void: 'void * tree_array [200] [3];' où la dernière dimension est pour les pointeurs * left, data, * et * right *. Avez-vous quelque chose contre 'struct's? –