Exercicio 5

Prévia do material em texto

1 // Feito por Jackson Felipe Magnabosco
 2 
 3 #include <bits/stdc++.h>
 4 
 5 using namespace std;
 6 typedef struct nodo
 7 {
 8 int informacao;
 9 struct nodo* esquerda;
 10 struct nodo* direita;
 11 }nodo;
 12 
 13 nodo *h;
 14 bool existe;
 15 
 16 
 17 nodo* insert(nodo* h1, int informacao)
 18 {
 19 if (!h1)
 20 {
 21 h1 = (nodo*) malloc(sizeof(nodo));
 22 h1->informacao = informacao;
 23 h1->esquerda = NULL;
 24 h1->direita = NULL;
 25 }
 26 else if (h1->informacao > informacao)
 27 h1->esquerda = insert(h1->esquerda, informacao);
 28 else
 29 h1->direita = insert(h1->direita, informacao);
 30 
 31 return h1;
 32 }
 33 nodo* rmv(nodo* h1, int informacao)
 34 {
 35 if (!h1) return NULL;
 36 nodo* aux;
 37 nodo* ant;
 38 if (h1->informacao == informacao)
 39 {
 40 if (!h1->esquerda && !h1->direita)
 41 {
 42 free(h1);
 43 return NULL;
 44 }
 45 else
 46 {
 47 if (h1->esquerda && !h1->direita)
 48 {
 49 aux = h1->esquerda;
 50 free(h1);
 51 h1 = NULL;
 52 return aux;
 53 }
 54 else
 55 {
 56 if (h1->direita && !h1->esquerda)
 57 {
 58 aux = h1->direita;
 59 free(h1);
 60 h1 = NULL;
 61 return aux;
 62 }
 63 else
 64 {
 65 aux = h1->esquerda;
 66 ant = NULL;
 67 while(aux->direita)
 68 {
 69 ant = aux;
 70 aux = aux->direita;
 71 }
 72 
 73 if (ant) ant->direita = aux->esquerda;
 74 
 75 aux->direita = h1->direita;
 76 if (aux == h1->esquerda)
 77 aux->esquerda = h1->esquerda->esquerda;
 78 else aux->esquerda = h1->esquerda;
 79 
 80 free(h1);
 81 h1 = NULL;
 82 return aux;
 83 }
 84 }
 85 }
 86 }
 87 else if (h1->informacao > informacao)
 88 h1->esquerda = rmv(h1->esquerda, informacao);
 89 else
 90 h1->direita = rmv(h1->direita, informacao);
 91 return h1;
 92 }
 93 int passos;
 94 int n;
 95 void pre(nodo* h1)
 96 {
 97 if (h1)
 98 {
 99 if (passos > 0) cout << ' ';
100 passos++;
101 cout << h1->informacao;
102 pre(h1->esquerda);
103 pre(h1->direita);
104 }
105 }
106 void inf(nodo* h1)
107 {
108 if (h1)
109 {
110 inf(h1->esquerda);
111 if (passos > 0) cout << ' ';
112 passos++;
113 cout << h1->informacao;
114 inf(h1->direita);
115 }
116 }
117 void pos(nodo* h1)
118 {
119 if (h1)
120 {
121 pos(h1->esquerda);
122 pos(h1->direita);
123 if (passos > 0) cout << ' ';
124 passos++;
125 cout << h1->informacao;
126 }
127 }
128 
129 void search(nodo* h1, int informacao)
130 {
131 if (h1)
132 {
133 if (h1->informacao == informacao)
134 {
135 existe = true;
136 }
137 else if (h1->informacao > informacao)
138 search(h1->esquerda, informacao);
139 
140 else
141 search(h1->direita, informacao);
142 }
143 }
144 int main()
145 {
146 char c;
147 char s[50];
148 int informacao;
149 h = NULL;
150 n = 0;
151 while((scanf("%c", &c) != EOF))
152 {
153 if (c == 'I')
154 {
155 c = getchar();
156 if (c == ' ')
157 {
158 scanf("%d", &informacao);
159 h = insert(h, informacao);
160 n++;
161 }
162 else
163 {
164 scanf("%s", s);
165 passos = 0;
166 inf(h);
167 cout << '\n';
168 }
169 }
170 else if (c == 'P')
171 {
172 c = getchar();
173 if (c == ' ')
174 {
175 scanf("%d", &informacao);
176 cout << informacao << ' ';
177 existe = false;
178 search(h, informacao);
179 if (!existe) cout << "nao ";
180 cout << "existe\n";
181 }
182 else
183 {
184 scanf("%s", s);
185 passos = 0;
186 if (strcmp(s, "EFIXA") == 0) pre(h);
187 else pos(h);
188 cout << '\n';
189 }
190 }
191 else
192 {
193 scanf("%d", &informacao);
194 h = rmv(h, informacao);
195 n--;
196 }
197 getchar();
198 }
199 }