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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#include <cstdlib>
#include <iostream>
using namespace std;
/****************************************************************************/
struct Nodo { // the Node.
int info; // the int value of the node
void* figlio; // pointer to be casted NodoInLista
};
/****************************************************************************/
struct NodoInLista { // represents a node child.
Nodo* puntatore; // pointer to the real child node
NodoInLista* fratello; // pointer to his brother
};
/****************************************************************************/
// add child
void aggiungiFiglio(struct Nodo* padre, struct Nodo* figlio);
// print tree
void stampaAlbero(struct Nodo* radice);
// search
struct Nodo* cerca(struct Nodo* radice, int val);
/****************************************************************************/
// add child
void aggiungiFiglio(struct Nodo* padre, struct Nodo* figlio) {
// the NodoInLista to be added as a child
struct NodoInLista* n = (struct NodoInLista*) malloc(sizeof(struct NodoInLista));
n->puntatore = figlio; // pointer to the Node child
n->fratello = NULL; // pointer to its 'younger' brother
// if the father has no children
if(padre->figlio == NULL)
// add the new child
padre->figlio = n;
// if the father already has some children
else {
// pointer to the first child
struct NodoInLista* t = (struct NodoInLista*) padre->figlio;
do {
// when founds a node whose 'younger brother' is NULL
if(t->fratello == NULL) {
// adds the new brother
t->fratello = n;
break;
}
} while((t = t->fratello) != NULL);
}
}
/****************************************************************************/
// prints
void stampaAlbero(struct Nodo* radice) {
// if the tree is empty
if(radice == NULL) {
printf("L'albero รจ vuoto.\n");
return;
}
// prints the current node value
printf("%d, ", radice->info);
// store its children here
struct NodoInLista* n = (struct NodoInLista*) radice->figlio;
// while the current node has children
while(n != NULL) {
// call this function on the child
stampaAlbero(n->puntatore);
// point to the next child
n = n->fratello;
}
}
/****************************************************************************/
struct Nodo* cerca(struct Nodo* radice, int val) {
if(radice == NULL)
return NULL;
// if this node contains the value we are searching for, return
if(radice->info == val)
return radice;
/////////////////////////////////
// PROBLEM HERE //
/////////////////////////////////
//getchar();
//system("PAUSE");
//printf("qui.\n");
// the child of the current node
struct NodoInLista* figlio = (struct NodoInLista*) radice->figlio;
// the pointer to the node with the searched value
struct Nodo* trovato = NULL;
// while the current node has a child
while(figlio != NULL) {
// recursive call. if the searched value was not found
if( (trovato = cerca(figlio->puntatore, val)) == NULL)
// try with the next child
figlio = figlio->fratello;
else
// else return the pointer to the node with the searched value
return trovato;
}
}
/****************************************************************************/
int main(int argc, char *argv[]) {
struct Nodo radice, figlio1, figlio2, figlio11, figlio12, figlio21, figlio22;
// the nodes values
radice.info = 1;
figlio1.info = 2;
figlio2.info = 3;
figlio11.info = 4;
figlio12.info = 5;
figlio21.info = 6;
figlio22.info = 7;
// the nodes children
radice.figlio = NULL;
figlio1.figlio = NULL;
figlio2.figlio = NULL;
figlio11.figlio = NULL;
figlio12.figlio = NULL;
figlio21.figlio = NULL;
figlio22.figlio = NULL;
/*
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// adds the children to the nodes
aggiungiFiglio(&radice,&figlio1);
aggiungiFiglio(&radice,&figlio2);
aggiungiFiglio(&figlio1,&figlio11);
aggiungiFiglio(&figlio1,&figlio12);
aggiungiFiglio(&figlio2,&figlio21);
aggiungiFiglio(&figlio2,&figlio22);
// prints the tree
stampaAlbero(&radice);
printf("\n");
// searches for a value and prints it
struct Nodo* c = cerca(&radice, 5);
if(c != NULL)
printf("Trovato %d.\n", c->info);
else
printf("Non Trovato.\n");
system("PAUSE");
return EXIT_SUCCESS;
}
|
