-
Notifications
You must be signed in to change notification settings - Fork 0
/
travessia.c
141 lines (125 loc) · 3.74 KB
/
travessia.c
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
#include <stdio.h>
#include <stdlib.h>
typedef struct no {
int chave;
struct no *esq;
struct no *dir;
} TNoABP;
void insere(TNoABP **raiz, int k) {
if(*raiz == NULL) {
*raiz = (TNoABP *) malloc(sizeof(TNoABP));
(*raiz)->chave = k;
(*raiz)->esq = NULL;
(*raiz)->dir = NULL;
return;
}
if(k < (*raiz)->chave) insere(&((*raiz)->esq), k);
else insere(&((*raiz)->dir), k);
}
void imprime(TNoABP *raiz) {
if(raiz == NULL) return;
imprime(raiz->esq);
printf("%d\n", raiz->chave);
imprime(raiz->dir);
}
void totalFolhas(TNoABP *raiz, int *cont) {
/* Assume que há uma variável contadora na main, inicializada com valor 0
e cujo endereço é passado como parâmetro para a função. */
if(raiz == NULL) return;
if((raiz->esq == NULL) && (raiz->dir == NULL)) {
*cont = *cont + 1;
return;
}
totalFolhas(raiz->esq, cont);
totalFolhas(raiz->dir, cont);
}
TNoABP **menorNo(TNoABP **raiz) {
if(*raiz == NULL) return NULL;
while((*raiz)->esq != NULL) raiz = &((*raiz)->esq);
return raiz;
}
void deletaArvore(TNoABP **raiz) {
if((*raiz) == NULL) return;
if((*raiz)->esq != NULL) deletaArvore(&(*raiz)->esq);
if((*raiz)->dir != NULL) deletaArvore(&(*raiz)->dir);
free(*raiz);
*raiz = NULL;
}
int soma(TNoABP *raiz, int *cont) {
/* Assume que há uma variável contadora na main, inicializada com valor 0
e cujo endereço é passado como parâmetro para a função. */
if(raiz == NULL) return 0;
(*cont)++;
return raiz->chave + soma(raiz->esq, cont) + soma(raiz->dir, cont);
}
TNoABP **busca(TNoABP **raiz, int k) {
if((*raiz) == NULL) return NULL;
while((*raiz) != NULL) {
if(k == (*raiz)->chave) return raiz;
if(k < (*raiz)->chave) raiz = &(*raiz)->esq;
else raiz = &(*raiz)->dir;
}
printf("Erro: no n esta na arvore\n");
return NULL;
}
void removeNo(TNoABP **raiz, TNoABP **no) {
if(*raiz == NULL) return;
if((*no)->chave == (*raiz)->chave) {
if((*raiz)->esq == NULL) {
TNoABP *aux = *raiz;
*raiz = (*raiz)->dir;
free(aux);
}
else if((*raiz)->dir == NULL) {
TNoABP *aux = *raiz;
*raiz = (*raiz)->esq;
free(aux);
}
else {
TNoABP *aux = (*raiz)->dir;
while (aux->esq != NULL) aux = aux->esq;
(*raiz)->chave = aux->chave;
removeNo(&(*raiz)->dir, &aux);
}
}
else if((*no)->chave < (*raiz)->chave) removeNo(&(*raiz)->esq, no);
else removeNo(&(*raiz)->dir, no);
}
void removeQuaseFolha(TNoABP **raiz, TNoABP **no) {
if(*raiz == NULL) return;
if((*raiz)->chave == (*no)->chave) {
TNoABP *aux = *raiz;
if((*raiz)->esq != NULL) *raiz = (*raiz)->esq;
else *raiz = (*raiz)->dir;
free(aux);
}
else if((*no)->chave < (*raiz)->chave) removeQuaseFolha(&(*raiz)->esq, no);
else removeQuaseFolha(&(*raiz)->dir, no);
}
void main() {
TNoABP *raiz = NULL;
int num, op, cont = 0, cont2 = 0;
do {
printf("1 - Inserir número, 0 - Continuar: ");
//scanf("%d", &op);
//if(op == 1) {
scanf("%d", &num);
insere(&raiz, num);
//}
} while(num != 0);
imprime(raiz);
totalFolhas(raiz, &cont);
printf("Cont: %d\n", cont);
TNoABP **menor;
menor = menorNo(&raiz);
if(menor) printf("Menor: %d\n", (*menor)->chave);
float media = (float) soma(raiz, &cont2) / cont2;
printf("Media: %f\n", media);
int k;
scanf("%d", &k);
TNoABP **buscar = busca(&raiz, k);
if(buscar != NULL) removeNo(&raiz, buscar);
//deletaArvore(&raiz);
if(raiz == NULL) printf("Árvore vazia\n");
else imprime(raiz);
}