Type de données abstrait d'arbre

Question

Je fais une unité appelée Structures de données et algorithmes. Nous venons de commencer et mon professeur vient de nous enseigner les bases de la sémantique algébrique, des axiomes, etc. Jusqu'à présent, je viens d'utiliser des arbres sous la forme de tableaux. N'utilisez pas la signature pour une arborescence pré-commandée sous forme d'arborescence (valeur, arborescence), où valeur correspond à la valeur du nœud, le nœud gauche est le premier arbre et le nœud droit est le deuxième.

Maintenant que je définis mon arbre en tant qu'arbre (valeur, arbre, arbre) ou Nil, je ne vois pas comment définir l'algèbre de addNode (valeur, arbre).

Cela devient de plus en plus compliqué à chaque niveau, de plus, je ne peux pas imaginer de toute façon de parcourir un niveau comme auparavant, cela fait depuis une heure à peine. L'algèbre se ramifie dans de plus en plus d'els si nous descendons l'arbre. Est-ce que je le fais bien? Pouvez-vous me diriger dans la bonne direction? Ou les arbres ne peuvent pas être implémentés en tant qu’arbre (valeur, arbre, arbre)?

Cela fait partie de mon tutoriel (dans les questions supplémentaires, je ne mérite pas de points), mais je ne cherche pas de réponse instantanée, j'aime le sujet et aimerais en savoir plus.

Éditer 1: J'ai vérifié Wikipédia et je ne veux pas utiliser le manuel pour une réponse claire, je cherche simplement un indice pour indiquer la bonne direction, que mon approche soit correcte ou qu'il soit complètement impossible de la définir. un arbre en tant qu'arbre (valeur, arbre, arbre). Je sais que vous pouvez représenter un arbre ADT sous forme de liste. Mais je voulais vraiment y penser. J'espère que cela a du sens. Merci beaucoup les gars!

Edit 2: Uhmm, c'est difficile à expliquer sur Internet. Supposons que je définis une nouvelle structure de données appelée "arbre". Je peux le définir comme je le veux et il doit se comporter comme un arbre binaire équilibré (cependant, les valeurs des parents et des enfants ne comptent pas) Alors je le définis comme arbre: arbre (valeur, arbre, arbre) OU nil Ce n'est pas du code de programmation, c'est juste comment je le définis. Arbre est une valeur + 2 autres arbres ou Arbre est nul. AddNode (valeur, arbre) ajoute maintenant un noeud à l’arbre tout en le maintenant équilibré. Ce n'est pas du code de programmation, c'est juste de la sémantique algébrique. Je ne sais pas si je peux l'expliquer correctement. Mais je suis arrivé à une solution que je peux réaliser en utilisant des files d'attente ou des piles, mais c'est un autre ADT que je dois définir, qui n'est pas valide.

Edit 3: On dirait que j’ai supposé beaucoup de choses qui ont rendu le problème plus difficile qu’il était censé être. Tout d'abord, d'après la petite explication que j'ai donnée, la réponse de Gamecat était parfaite. Mais je suis d'accord avec les commentaires, il est parfaitement valide d'inclure d'autres TDA. En fait, lorsque nous construisons tout ce qui utilise un Int, nous utilisons un ADT pour cette structure. Je pensais que chaque TDA devait être unique. Quoi qu'il en soit, merci beaucoup les gars pour vos réponses!

Answer 1

Si vous souhaitez ajouter un nœud à une arborescence, vous pouvez utiliser une fonction récursive.

Je suppose que l'arbre est commandé. Donc, vous devriez obtenir quelque chose comme ça:

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

Assurez-vous de mettre à jour les sous-arbres s'ils ont été modifiés!

Vous pouvez convertir ceci en une fonction non récursive par:

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

Si l’arbre doit être équilibré. Vous devez enregistrer un poids d'équilibre (qui peut être -1, 0 ou 1). Si vous devez ajouter un nœud sur un " lourd " site, vous devez remanier cela. Par exemple, si le côté gauche a un noeud de plus que le côté droit et que vous devez ajouter un noeud de plus à gauche. Vous devez obtenir le nœud avec la valeur la plus élevée de la sous-arborescence de gauche et la promouvoir au sommet actuel. Le sommet précédent est ajouté à la sous-arborescence de droite. Veillez également à garder les sous-arbres équilibrés.

Exemple: ajoutez les nœuds 0,1,2,3,4

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4

Answer 2

C'est une question difficile, tant elle est vague. Je suppose que vous avez un manuel ou quelque chose de similaire dans votre matériel de cours. Même dans ce cas, vous avez l’impression que beaucoup de choses avec lesquelles vous rencontrez des problèmes sont expliquées par une ressource basique, telle que l'entrée Wikipedia sur arbres binaires.

Cette page explique comment effectuer diverses traversées d'arbres et comment les représenter.