Tree Abstract Data Type

Question

Je suis en train de créer une unité appelée Data Structures and Algorithms. Nous venons juste de commencer et mon professeur vient de nous enseigner les bases de ce qu'est la sémantique algébrique et de ce que sont les axiomes etc. Jusqu'à présent, je viens d'utiliser des arbres sous forme de tableaux. Ne pas utiliser la signature pour l'arbre précommandé comme arbre (valeur, arbre, arbre) où la valeur est la valeur dans le nœud, le nœud gauche est le premier arbre et le nœud droit est le deuxième arbre. Maintenant que je définis mon arbre comme arbre (valeur, arbre, arbre) ou Nul, je ne peux pas comprendre comment définir l'algèbre pour addNode (valeur, arbre).

Cela devient de plus en plus compliqué à chaque niveau, en plus, je ne peux absolument pas penser à balayer un niveau comme une fois, en essayant depuis une heure maintenant. L'algèbre se ramifie de plus en plus en if-elses quand nous descendons dans l'arbre. Est-ce que je le fais bien? Pouvez-vous me pointer dans la bonne direction? Ou les arbres ne peuvent pas être implémentés comme arbre (valeur, arbre, arbre)?

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

Edit 1: J'ai vérifié Wikipedia, et je ne veux pas utiliser le manuel pour la réponse claire, je cherche juste un soupçon vers la bonne direction, que mon approche est juste ou il est tout à fait impossible de définir un arbre comme arbre (valeur, arbre, arbre). Je sais que vous pouvez représenter un arbre ADT sous la forme d'une liste. Mais je voulais vraiment y penser. J'espère que cela a du sens. Merci beaucoup les gars!

Édition 2: Euh, c'est difficile à expliquer sur internet. Disons que je définis une nouvelle structure de données appelée "arbre". Je peux le définir comme je veux, et il doit se comporter comme un arbre binaire équilibré (bien que les valeurs des parents et des enfants ne comptent pas) Donc je le définis comme arbre: arbre (valeur, arbre, arbre) OU nul Ce n'est pas code de programmation, c'est juste comment je le définis. Tree est une valeur + 2 autres arbres ou Arbre est nul. Maintenant, addNode (value, tree) ajoute un nœud à 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 atteindre en utilisant Queues ou Stacks, mais c'est un autre ADT que je vais devoir définir, ce qui n'est pas valide. Éditer 3: On dirait que j'avais supposé beaucoup de choses qui rendaient le problème plus difficile qu'il ne l'é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 possible d'inclure d'autres ADT. En fait, lorsque nous construisons quelque chose qui utilise un Int, nous utilisons un ADT pour cette structure. Je pensais que chaque ADT devait être unique. De toute façon, merci beaucoup les gars pour vos réponses!

Answer 1

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

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

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 sont modifiés!

Vous pouvez convertir 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 stocker un poids d'équilibre (qui peut être -1, 0 ou 1). Si vous devez ajouter un nœud sur un site "lourd", vous devez le réorganiser. Par exemple si le côté gauche a un nœud de plus que le côté droit et que vous devez ajouter un nœud de plus à gauche. Vous devez obtenir le noeud ayant la valeur la plus élevée dans le sous-arbre gauche et en faire la promotion au sommet actuel. Le sommet précédent est ajouté au sous-arbre de droite. Assurez-vous de garder les sous-arbres équilibrés aussi.

Exemple: ajouter les noeuds 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

Ceci est une question difficile, car il est si vague. Je suppose que vous avez un livre de texte ou quelque chose de similaire dans le cadre de votre matériel de cours. Même ainsi, il se sent comme si beaucoup de choses que vous rencontrez des problèmes sont expliquées par une ressource de base, tels que the Wikipedia entry sur arbres binaires.

Cette page décrit comment effectuer différentes traversées d'arbres et comment les arbres peuvent être représentés.