Arbre binaire, trouver la profondeur d une node.

Arbre binaire, trouver la profondeur d une node. - Algo - Programmation

Marsh Posté le 05-04-2004 à 16:43:54    

:hello: ,
 
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 :
  1. 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 :
  1. int deepness(int key)
  2. {
  3.     int count =0;
  4.     _deepness(key, root, count)
  5.     return count;
  6. }
  8. void _deepness(int key, tree t,int count)
  9. {
  10.    //?  
  12. }


 
  [:dams86]  
 
l algo pour recherche une node en fonction de sa valeur est le suivant.
 

Code :
  1. tree  btree::retrieves(int x, tree t)
  2. {
  3.     if (t==NULL) return t;
  4.     else if (x < t->data) return retrieve(x, t->left);
  5.     else if (x > t->data) return retrieve(x, t->right);
  6.     else return t; //found it
  7. }


 
Google ne mas rien apporte de plus que le lien trouve cidessus.
merci pour votre aide.

Reply

Marsh Posté le 05-04-2004 à 16:43:54   

Reply

Marsh Posté le 06-04-2004 à 00:42:21    

personne nas eu a faire a ce genre d algp ? imprimer un arbre binaire en console ?

Reply

Marsh Posté le 06-04-2004 à 05:49:29    

c est bon jaitrouve

Code :
  1. int btree::nodedepth(int key){
  2.     int count = 0;
  3.     _nodedepth(key, root, count);
  4.     return count;
  5. }
  7. void btree::_nodedepth(int key, tree t, int& count){
  8.     if (t==NULL) return;
  9.     else if (key < t->data) {
  10.          count ++;
  11.          _nodedepth(key, t->left,count);
  12.          }
  13.     else if (key > t->data) {
  14.         _nodedepth(key, t->right, count);
  15.         count ++;
  16.         }
  17.     else return; //found it     
  18. }

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed