Discussion :

[Dayssam]

le probleme c 'est
comment generaliser un programme qui traiter arbre qlq .. d'une maniere itérative et récursive??

[Médinoc]

"qlq itérative et récursive" : syntax error.

Parle d'une manière compréhensible, s'il te plait.

Et ne crie pas, merci.

[Dayssam]

"qlq itérative et récursive" : syntax error.

Parle d'une manière compréhensible, s'il te plait.

Et ne crie pas, merci.

cest a dire d'une maniere itérative et recursive..

merci davance

[Médinoc]

Dans ce cas, c'est Deux programmes, non ?

De plus, les arbres ne sont pas tous traitables sans récursivité (sachant que du "itératif avec pile", ça reste du récursif pour moi).
Plus d'informations sur les arbres ici: http://www.developpez.net/forums/sho...13&postcount=3

[Sve@r]

Dans ce cas, c'est Deux programmes, non ?

Bah c'est plus précisément 2 algo donc ça peut être simplement 2 fonctions...

De plus, les arbres ne sont pas tous traitables sans récursivité (sachant que du "itératif avec pile", ça reste du récursif pour moi).

Exact. Etant donné que dans les arbres simplement binaires (g/d) il faut mémoriser le noeud central pour pouvoir, après avoir traiter le coté g, y revenir pour traiter le coté d (et ce pour chaque noeud dont le nombre n'est pas connu), la récursivité (réelle ou simulée) reste obligatoire. Mais certaines personnes disent que faire un algo itératif avec pile reste itératif. C'est une question de nuance (ou de point de vue)...

[Pragmateek]

En informatique on parle de récursivité quand une fonction s'appelle elle même .
Donc une fonction qui traite une pile, simulant en partie le passage de paramètre à une autre fonction, et ne s'appelle pas elle même reste itérative .

[Sve@r]

le probleme c 'est
comment generaliser un programme qui traiter arbre qlq itérative et récursive??

De rien.

[Dayssam]

slt

jai besoin des commentaires et traduction pour ce code la pour les debutants

et merci davance

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
struct node { 
    int data; 
    struct node* left; 
    struct node* right; 
}

Lookup()
Given a binary search tree and a "target" value, search the tree to see if it contains the target. The basic pattern of the lookup() code occurs in many recursive tree algorithms: deal with the base case where the tree is empty, deal with the current node, and then use recursion to deal with the subtrees. If the tree is a binary search tree, there is often some sort of less-than test on the node to decide if the recursion should go left or right.
/*
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
*/

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static int lookup(struct node* node, int target) { 
  // 1. Base case == empty tree 
  // in that case, the target is not found so return false 
  if (node == NULL) { 
    return(false); 
  } 
  else { 
    // 2. see if found here 
    if (target == node->data) return(true); 
    else { 
      // 3. otherwise recur down the correct subtree 
      if (target < node->data) return(lookup(node->left, target)); 
      else return(lookup(node->right, target)); 
    } 
  } 
}

[Médinoc]

Ce code suit le principe de base de la recherche récursive dans un arbre binaire:

1. Si le noeud est nul, on n'a pas trouvé.
2. On vérifie si la clé du noeud courant est celle recherchée. Si oui, on retourne la valeur.
3. Sinon, il faut chercher dans un des noeuds fils: Si la clé est inférieure à la clé du noeud courant, on cherche dans le fils de gauche. Sinon, dans le fils de droite.

[Sve@r]

[*]Sinon, il faut chercher dans un des noeuds fils: Si la clé est inférieure à la clé du noeud courant, on cherche dans le fils de gauche. Sinon, dans le fils de droite.

Exact. Et d'ailleurs ceci m'amènerait à modifier un poil la fin de la fonction pour la remplacer par une instruction qui, pour moi, illustre mieux cette dernière phase en remplaçant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
// 3. otherwise recur down the correct subtree 
      if (target < node->data) return(lookup(node->left, target)); 
      else return(lookup(node->right, target));

Par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
// 3. otherwise recur down the correct subtree 
      return lookup(target < node->data ?node->left :node->right, target);

[Pragmateek]

La fonction peut-être, mais l'algorithme lui-même reste récursif.

Si l'algorithme "s'appelle" lui même explicitement oui .