competitive-programming/ALGORITHMS/struct/bts/bts.c at master · Math-O5/competitive-programming · GitHub

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
#include "bts.h"

int vazia(Arvore* a) {
	if(a == NULL) return 1;
    return 0;
}


void imprimir_pre_ordenada(Arvore* a) {
     if(!vazia(a)) {
		printf("%d ", a->valor);
		imprimir_pre_ordenada(a->esq);
		imprimir_pre_ordenada(a->dir);
     }
}

void imprimir_in_ordenada(Arvore* a) {
     if(!vazia(a)) {
	    imprimir_in_ordenada(a->esq);
		printf("%d ", a->valor);
		imprimir_in_ordenada(a->dir);
     }
}

void imprimir_pos_ordenada(Arvore* a) {
     if(!vazia(a)) {
	    imprimir_pos_ordenada(a->esq);
		imprimir_pos_ordenada(a->dir);
		printf("%d ", a->valor);
     }

}

/*
 * Faz busca, verifica a existencia de
 * um elemnto.
 * */
int buscar_pos(Arvore* b, int elem) {
    if(b == NULL) return 0;
    if(b->valor > elem) {
		return buscar_pos(b->esq, elem);
    }
    else if(b->valor < elem) {
	    return buscar_pos(b->dir, elem);
	}
	else return 1;
}


Arvore* busca_maior_valor_sub_esquerda(Arvore* a) {
    Arvore* b = a;

    while(b->esq != NULL) {
		 b = b->esq;
	}
	return b;
}

Arvore* elimina(Arvore* a, int elem) {

	 if(a->valor == elem) {
	       Arvore* b;

	       if(a->esq == NULL) {

			   b = a->dir;
			   a->valor = 0;
			   free(a);
			   return b;
		   }
	       else if(a->dir == NULL) {

			   b = a->esq;
			   a->valor = 0;
			   free(a);
			   return b;
		   }
	       b = busca_maior_valor_sub_esquerda(a->dir);
	       a->valor = b->valor;

	       a->dir = elimina(a->dir, b->valor);
     }
	 else if(a->valor < elem) a->dir = elimina(a->dir, elem);
	 else if(a->valor > elem) a->esq = elimina(a->esq, elem);

     return a;
}

int remove_(Arvore* a, int elem) {
	if(buscar_pos(a, elem) == 0) return 0;
	a = elimina(a, elem);
    return 1;
}

int inserir(Arvore* a, int elem) {

	if(a->valor > elem) {
		  if(a->esq == NULL) {
		     a->esq = calloc(1, sizeof(Arvore));
		     a->esq->valor = elem;
		     return 0;
		  }
		  else return inserir(a->esq, elem);
	 }
	 else if(a->valor < elem) {
	      if(a->dir == NULL) {
		     a->dir = calloc(1, sizeof(Arvore));
		     a->dir->valor = elem;
		     return 0;
		  }
		  else return inserir(a->dir, elem);
	 }
	 else return 1;
}