Discussion :

[smalto]

pouvez vous m`expliquez la fonction [void treeinorder(node *root)] je ne comprends pas la recursion......

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
/* implement tree structure
   insert duplicate numbers
   
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
struct nodetype
{
	int data;
	struct nodetype *left, *right;
};
 
typedef struct nodetype node;
 
node* treeinsert(node*, int);
node* newnode(int);
void treeinorder(node*);
 
node* newnode(int x)
{
	node *p;
 
	p = new(node);
	p->data = x;
	p->left = NULL;
	p->right = NULL;
 
	return (p);
}
 
node* treeinsert(node *root, int x)
{
	if (root == NULL)
		root = newnode(x);
	else
		if (root->data >= x) // insert at left subtree
			root->left = treeinsert(root->left, x);
		else // insert at right subtree
			root->right = treeinsert(root->right, x);
 
	return (root);
}
 
void treeinorder(node *root)
{
	if (root != NULL)
	{
		treeinorder(root->left);
		printf("%d  ", root->data);
		treeinorder(root->right);
	}
}
 
void main(void)
{
	int num;
	node *root;
 
	root = NULL;
	printf("Enter a number to be inserted or 0 to exit: ");
	scanf("%d", &num);
	while (num != 0)
	{
		root = treeinsert(root,num);
		printf("Enter a number to be inserted or 0 to exit: ");
		scanf("%d", &num);
	}
 
	treeinorder(root);
	printf("\n");
	getch();
}

...SMALTO...
Merci de penser à la balise code à l'avenir...

[Matthieu Brucher]

C'est pas très compliqué... Teste et regarde d'abord.

Tant qu'on est pas à une feuille, on affiche les côtés gauches, puis on affichera la valeur du noeud et on fera la même chose ensuite sur les noeuds à droite.

[smalto]

quand je compile je vois ce qui ce passe, mais je ne comprends pas comment est ce qu`on revient et on affiche root parce que pour moi quand leaves est null on sort de la fonction et apres comment estce que on revient a l`affichage puisque on est null deja et aussi qd est ce que on atteint leaf right. pat example :
7 - 5 -8
4-7-6 // 10-8-14
3-14-12


-----------------------------5---------------------------------------------1er leaf-
-------------7---------------|----------------8---------------------------------2em
-------4-----------6---------|-------10------------------14-------------------3em
-----------------------------------------------------3------------12-----------4em


comsidere un arbre avec 5 la premiere root, a gauche 7 ,a gauche de 7 est 4 et a droite de 7 est 6. a droite de 5 est 8 et a gauche de 8 est 10. a droite de est 14. a gauche de 14 est 3 et a droite de 14 est 12.
s`il te plait essai de m`expliquer cela etape par etape comment est ce que l`affichage va se faire ou comment est se que la fonction treinorder va parcourir cet arbre la....s`il te plait considere en fesant ton explication que je ne conait vraiment rien donc si tu peux detailler plus cela m`aidera....merci
SMALTo0...

[Matthieu Brucher]

Oui, on sort de la fonction courante, mais il y a les autres appels à la fonction treeinorder qui ont fait qu'on est arrivé à un root==NULL qui continuent à tourner.
Là, tu auras qqch du genre 4 7 6 5 10 8 3 14 12

[smalto]

je crois que je ne suis pas trop inteligent pour concevoir cela, donc s`il te plait veut tu aller etapes par etape tu n`as pas besoin de faire tout l`arbre et me donner le resultat seulement je veux l`explication d`une partie de l`abre bien dans les details et je serais capable de faire le reste....je sais que cela semble tres facile pour toi , mais je te prie de bien vouloir m`esxcuse pour mon incomprehension.......ce que je voudrais c`est que tu prennes de la route 5 a la leaf 4 ,6 explication ds les detail et comment revenir a 5.
lis mon explication et si tu crois que je suis concret dans l`explication c`est que j`ai compris, mais c`est un peu ce que j`attendais comme explication...

par example: au debut la root est 5 ,root etant non null nous passons la fonction treeinorder encore ce qui renvoi a la gauche de Root(5), donc 7 devient la nouvelle Root(7), root(7) etant non null nous repassons dans la fonction trreinorder, ce qui renvoi a la gauche de root(7), donc 4 devient la nouvelle root(4), Root(4) etant non null nous rappelleons la fonction treeinorder, nous passons a la gauche de Root(4), la gauche de root(4) qui devait etre la nouvelle root est null,nous ne continuons plus et revenon a root(4) qui attendait une reponse de sa gauche.
root (4) etant la root precedente avant la root null, nous afficherons 4. ensuite nous irons a la droite de root(4) qui est null a son tour nous revenons a root(4). qui a son tour passera la reponse a root(7). root (7) a son tour sera affichee et fera appel a la fonction treeinorder encore donc passera a sa droite le meme processus que le cote gauche se suivra ensuite Root(6) sera affichee et reviendra a roo(7). qui a son tour reviendra a la ROOT(5) qui sera affiche aussi. et ROOT(5) a son tour passera le meme processus a sa droite a 8 qui deviendra root(8 ).

merci de ton aide, que je sois wrong ou wright.
SMALTO

[Herode]

Exact. Tu as donc compris le principe de la récursion ! 8)

NB : vu le code de la méthode treeinsert(), l'arbre que tu donnes en exemple ne peut pas exister. Cette méthode permet de construire un arbre ordonné, d'où l'intérêt de la méthode treeinorder() qui, en faisant un parcours infixé, te donnera une liste de noeuds ordonnés par valeurs croissantes.

[smalto]

merci ,si cela est le principe je crois que j`ai compris, merci a tous et a bientot pour un autre problem , car il y en a toujours......

SMALTO...