,
j essaye de coder , en suivant l algo du Krug. une fonction qui imprime un arbre de haut en bas.
http://www.faqts.com/knowledge_bas [...] 9/fid/1266
exemple :
l insertion de 2 1 3 0 8 dans un arbre binaire ordonne (binary search tree) donnerai a l ecran:
2
1 3
0 8
la methode consiste a cree une grille 2D qui vas contenir
la representation de larbre.
1ere etape traverser l arbre inorder (gauche a droite) (l axe x)
et inserer les elements a leur position X. ici : 1 2 0 3 8
et Y correspondant a leur profondeur par rapport a la racine.
(1,2) (2,0) (0,3) (3,2) (8,3).
Pour creer la grille, le nombre de node n etant pas connu lors de la compilation et comme j ai pas envie de partir avec des pointeurs dans tous les sens j utilise un vecteur de vecteur
Code :
- vector < vector<int> > grid
|
ce qu il me faudrais c est une fonction me renvoyant la profondeur dune node. (node reconnu grace a sa valeur "data" )
Code :
- int deepness(int key)
- {
- int count =0;
- _deepness(key, root, count)
- return count;
- }
- void _deepness(int key, tree t,int count)
- {
- //?
- }
|
l algo pour recherche une node en fonction de sa valeur est le suivant.
Code :
- tree btree::retrieves(int x, tree t)
- {
- if (t==NULL) return t;
- else if (x < t->data) return retrieve(x, t->left);
- else if (x > t->data) return retrieve(x, t->right);
- else return t; //found it
- }
|
Google ne mas rien apporte de plus que le lien trouve cidessus.
merci pour votre aide.