-
Notifications
You must be signed in to change notification settings - Fork 0
/
BST.c
132 lines (105 loc) · 2.67 KB
/
BST.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
#include <stdio.h>
#include <stdlib.h>
typedef struct btree btree;
struct btree
{
int item;
btree *left;
btree *right;
};
btree* create_empty()
{
return NULL;
}
int empty(btree *bt)
{
return (bt == NULL);
}
btree* create_btree(int item, btree *left, btree *right)
{
btree *new_btree = (btree*) malloc(sizeof(btree));
new_btree->item = item;
new_btree->left = left;
new_btree->right = right;
return new_btree;
}
btree* del(btree *bt, int num)
{
if(bt == NULL) return bt;
if(bt->item > item) bt->left = del(bt->left, num);
else if(bt->item < item) bt->right = del(bt->right, num);
else
{
if(bt->right == NULL)
btree *aux = bt->left; free(bt);
return aux;
}
}
btree* add_term(btree *bt, int item, int i, int *save) //// binary search tree ////
{
if(bt == NULL) bt = create_btree(item,NULL,NULL);
else if(bt->item > item) bt->left = add(bt->left, item, i+1, save);
else bt->right = add(bt->right, item, i+1, save);
return bt;
}
int search_term(btree *bt, int item, int i, int *save)//// binary search tree////
{
if(bt == NULL) return 0;
else if(bt->item == item) return 1;
else if(bt->item > item) search_term(bt->left, item, i+1, save);
else search_term(bt->right, item, i+1, save);
}
int search_level(btree *bt,int item, int i, int *save)
{
if(bt == NULL) return 0;
else if(bt->item == item) {*save+=i; return *save; }
else if(bt->item > item) search_term(bt->left, item, i+1, save);
else search_term(bt->right, item, i+1, save);
}
void main()
{
btree *tree =create_empty();
long int t,n,op,i=0,num,save=0;
long int a[100000];
printf("inicio\n");
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
while(n--)
{
scanf("%d %d", &op, &num);
if(op == 1) // add num
{
if(search(tree,num,0, &save)){ printf("%d\n", search_level(tree,num,0,&save)); save = 0;}
else
{
a[i] = num; i++;
tree = add_term(tree, num,0,&save);
printf("%d\n", save); save = 0;
}
}
else if(op == 2) // del num
{
if(search(tree,num,0,&save))
{
printf("%d\n", save); save=0;
tree = del(tree,num);
}
}
else if( op == 3) //maiores que num
{
}
else if(op == 4) // kth num in order
{
}
}
}
tree = create_btree(5,NULL,NULL);
tree->left = create_btree(2,NULL,NULL);
tree->right = create_btree(6,NULL,NULL);
print_pre(tree);
printf("resposta da busca de 5 = %d\n",search_term(tree,5,0,&save)); save=0;
printf("resposta da busca de 2= %d\n",search_term(tree,2,0,&save)); save=0;
printf("resposta da busca de 6 = %d",search_term(tree,6,0,&save));
}