API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 24th, 2016
58
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.38 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ALLOC (TNo*)malloc(sizeof(TNo));
  5.  
  6. typedef struct no{
  7. struct no *esq, *dir;
  8. int inf, sup;
  9. } TNo;
  10.  
  11. void inicializa(TNo **ptr){
  12. (*ptr) = NULL;
  13. }
  14. /*void insere(TNo **ptr, int chave){
  15. if((*ptr) == NULL){
  16. (*ptr) = ALLOC;
  17. (*ptr)->esq = NULL;
  18. (*ptr)->dir = NULL;
  19. (*ptr)->chave = chave;
  20. } else{
  21. if(chave < (*ptr)->chave)
  22. insere(&(*ptr)->esq, chave);
  23. else if(chave > (*ptr)->chave)
  24. insere(&(*ptr)->dir, chave);
  25. else
  26. printf("\nChave #%d ja existente!", chave);
  27. }
  28. }
  29.  
  30. remove somente se for exatamente o intervalo ou estiver dentro
  31.  
  32. void antecessor(TNo *q, TNo **r){
  33. if((*r)->dir != NULL)
  34. antecessor(q, &(*r)->dir);
  35. else{
  36. q->chave = (*r)->chave;
  37. q = (*r);
  38. (*r) = (*r)->esq;
  39. free(q);
  40. }
  41. }
  42. */
  43.  
  44.  
  45.  
  46. TNo convertToTNo(struct no *r){
  47. TNo n;
  48. n.dir = r->dir;
  49. n.esq = r->esq;
  50. n.inf = r->inf;
  51. n.sup = r->sup;
  52. return n;
  53. }
  54.  
  55. void insere (TNo **ptr, TNo no){
  56. printf("\n%d-%d\n", no.inf, no.sup);
  57. if((*ptr) == NULL){
  58. (*ptr) = ALLOC;
  59. (*ptr)->esq = NULL;
  60. (*ptr)->dir = NULL;
  61. (*ptr)->inf = no.inf;
  62. (*ptr)->sup = no.sup;
  63. printf("no1\t");
  64. }
  65. // maior que o inferior E menor que o superior (entre inf e sup)
  66. else if((*ptr)->inf <= no.inf && (*ptr)->sup >= no.sup){
  67. //noJaInserido
  68. printf("\n%d %d %d %d\n", (*ptr)->inf, (*ptr)->sup, no.inf, no.sup);
  69. printf("\nConjunto ja existente!");
  70. }
  71.  
  72. // INFERIOR maior que o superior em 1 OU igual ao superior OU entre o inferior e o superior
  73. else if(((*ptr)->sup == no.inf - 1) || ((*ptr)->sup == no.inf) || ((*ptr)->inf <= no.inf && (*ptr)->sup >= no.inf)){
  74. if((*ptr)->dir){
  75. if((*ptr)->dir->inf - 1 <= no.sup){ // maior que o inferior do próximo nó em pelo menos 1
  76. printf("22->dir\t");
  77. //junta-se a ptr, alterando o superior para o atual
  78. (*ptr)->dir->inf = no.inf;
  79. struct no *aux = (*ptr)->dir;
  80. TNo a = convertToTNo(aux);
  81. free((*ptr)->dir);//REMOVE
  82. (*ptr)->dir = NULL;//REMOVE
  83. insere(&(*ptr), a);
  84. }
  85. else if((*ptr)->dir->sup < no.sup){ //menor que o inferior do próximo nó a esquerda
  86. TNo **aux = ptr;
  87. *aux = (*aux)->dir;
  88. insere(aux, no);
  89. printf("a2->dir");
  90. }
  91. }
  92. else{
  93. (*ptr)->sup = no.sup;
  94. printf("b1\t");
  95. }
  96. }
  97.  
  98.  
  99. // SUPERIOR menor que o inferior em 1 OU igual ao inferior OU entre o inferior e o superior
  100. else if(((*ptr)->inf == no.sup + 1) || ((*ptr)->inf == no.sup) || ((*ptr)->inf <= no.sup && (*ptr)->sup >= no.sup)){
  101. if((*ptr)->esq){
  102. if((*ptr)->esq->inf - 1 <= no.inf){ //maior que o inferior do próximo nó a esquerda em pelo menos 1
  103. printf("22->esq\t");
  104. //junta-se a ptr, alterando o superior para o atual
  105. (*ptr)->esq->sup = no.sup;
  106. struct no *aux = (*ptr)->esq;
  107. TNo a = convertToTNo(aux);
  108. free((*ptr)->esq);//REMOVE
  109. (*ptr)->esq = NULL;//REMOVE
  110. insere(&(*ptr), a);
  111. //remover o no da esquerda e alocá-lo ao principal
  112. }
  113. else if((*ptr)->esq->inf > no.inf){ //menor que o inferior do próximo nó a esquerda
  114. TNo **aux = ptr;
  115. *aux = (*aux)->esq;
  116. insere(aux, no);
  117. printf("a2->esq\t");
  118. }
  119. //insere(&(*ptr)->esq, no);
  120. }
  121. else{
  122. (*ptr)->inf = no.inf;
  123. //insere(&(*ptr), )
  124. printf("b2\t");
  125. }
  126. }
  127.  
  128. else if((*ptr)->inf > no.sup){
  129. insere(&(*ptr)->esq, no);
  130. printf("c1\t");
  131. }
  132.  
  133. else if((*ptr)->sup < no.sup){
  134. insere(&(*ptr)->dir, no);
  135. printf("c2\t");
  136. }
  137.  
  138. printf("\n\n");
  139.  
  140. //else if()
  141.  
  142. /*TNo *aux = *ptr->dir;
  143. (*ptr)->sup = (*ptr)->dir->sup;
  144. (*ptr)->dir = (*ptr)->dir->dir;
  145. free(aux);*/
  146. }
  147.  
  148. /*
  149. void inOrdem(TNo **ptr){
  150. if((*ptr) != NULL){
  151. free((*ptr));
  152. inOrdem((*ptr)->esq);
  153. inOrdem((*ptr)->dir);
  154. }
  155. }
  156. */
  157.  
  158.  
  159. /*
  160.  
  161.  
  162. void remover(TNo **ptr, int chave){
  163. if((*ptr) == NULL)
  164. printf("\nA chave #%d nao esta na arvore!", chave);
  165. else if(chave < (*ptr)->chave)
  166. remover(&(*ptr)->esq, chave);
  167. else if(chave > (*ptr)->chave)
  168. remover(&(*ptr)->dir, chave);
  169. else{
  170. TNo *aux = *ptr;
  171. if((*ptr)->dir == NULL){
  172. (*ptr) = (*ptr)->esq;
  173. free(aux);
  174. } else if((*ptr)->esq == NULL){
  175. (*ptr) = (*ptr)->dir;
  176. free(aux);
  177. } else antecessor((*ptr), &(*ptr)->esq);
  178. }
  179. }
  180.  
  181. void inOrdem(TNo *ptr){
  182. if(ptr != NULL){
  183. inOrdem(ptr->esq);
  184. printf("%d\n", ptr->chave);
  185. inOrdem(ptr->dir);
  186. }
  187. }
  188.  
  189. void preOrdem(TNo *ptr){
  190. if(ptr != NULL){
  191. printf("%d\n", ptr->chave);
  192. preOrdem(ptr->esq);
  193. preOrdem(ptr->dir);
  194. }
  195. }
  196.  
  197. void posOrdem(TNo *ptr){
  198. if(ptr != NULL){
  199. posOrdem(ptr->esq);
  200. posOrdem(ptr->dir);
  201. printf("%d\n", ptr->chave);
  202. }
  203. }
  204.  
  205. void filhoEsq(TNo *ptr, int chave){
  206. if(ptr->chave == chave){
  207. if(ptr->esq != NULL){
  208. printf("%d", ptr->esq->chave);
  209. }
  210. else printf("Nao tem filho a esquerda");
  211. } else{
  212. while(ptr->chave != chave){
  213. if(ptr->chave > chave){
  214. ptr = ptr->esq;
  215. } else{
  216. ptr = ptr->dir;
  217. }
  218. }
  219. if(ptr == NULL) return;
  220. }
  221. }
  222. */
  223.  
  224. void main(){
  225. TNo* raiz = NULL;
  226. int i;
  227. //for (i = 0; i < 10; i++)
  228. inicializa(&raiz);
  229.  
  230. TNo n;
  231. n.dir = NULL;
  232. n.esq = NULL;
  233. n.inf = 20;
  234. n.sup = 25;
  235. insere(&(raiz), n);
  236.  
  237. n.inf = 15;
  238. n.sup = 18;
  239. insere(&(raiz), n);
  240.  
  241. n.inf = 27;
  242. n.sup = 35;
  243. insere(&(raiz), n);
  244.  
  245. n.inf = 19;
  246. n.sup = 24;
  247. insere(&(raiz), n);
  248.  
  249. n.inf = 26;
  250. n.sup = 33;
  251. insere(&(raiz), n);
  252.  
  253. n.inf = 37;
  254. n.sup = 40;
  255. insere(&(raiz), n);
  256.  
  257. n.inf = 14;
  258. n.sup = 36;
  259. insere(&(raiz), n);
  260.  
  261.  
  262. printf("\n\t%d-%d\n", (raiz)->inf, (raiz)->sup);
  263. if((raiz)->esq)
  264. printf("\n%d-%d", (raiz)->esq->inf, (raiz)->esq->sup);
  265. if((raiz)->dir)
  266. printf("\t\t%d-%d", (raiz)->dir->inf, (raiz)->dir->sup);
  267.  
  268.  
  269. //void insere (TNo **ptr, TNo no){
  270. // if((*ptr) == NULL)
  271. // alocaNo
  272. // else
  273. // if((*ptr)->inf <= no.inf && (*ptr)->sup >= no.sup)
  274. // noJaInserido
  275. // else
  276. // if(((*ptr)->sup == no.inf - 1) && ((*ptr)->dir->inf == no.sup + 1)){
  277. // TNo *aux = *ptr->dir;
  278. // (*ptr)->sup = (*ptr)->dir->sup;
  279. // (*ptr)->dir = (*ptr)->dir->dir;
  280. // free(aux);
  281. // }
  282. // }
  283. // else
  284. // if()
  285.  
  286. /*
  287. int opt = -1;
  288. while(opt != 0){
  289. system("cls");
  290. printf("1- Inserir Chave\n");
  291. printf("2- Remover Chave\n");
  292. printf("3- Pesquisar Filho da Esquerda\n");
  293. printf("4- Pesquisar Pai\n");
  294. printf("5- Exibir em Ordem\n");
  295. printf("6- Exibir em Pre Ordem\n");
  296. printf("7- Exibir em Pos Ordem\n");
  297. printf("0- Sair\n");
  298. scanf("%d", &opt);
  299. system("cls");
  300.  
  301. switch (opt){
  302. case 1: {
  303. int chave;
  304. printf("Digite a Chave a ser inserida: ");
  305. scanf("%d", &chave);
  306. insere(&(raiz), chave);
  307. break;
  308. }
  309. case 2: {
  310. int chave;
  311. printf("Digite a Chave a ser removida: ");
  312. scanf("%d", &chave);
  313. remover(&(raiz), chave);
  314. break;
  315. }
  316. case 3: {
  317. int chave;
  318. printf("Digite a Chave a ser pesquisada: ");
  319. scanf("%d", &chave);
  320. filhoEsq(raiz, chave);
  321. system("pause");
  322. break;
  323. }
  324. case 4: {
  325. int chave;
  326. printf("Digite a Chave a ser pesquisada: ");
  327. scanf("%d", &chave);
  328. system("pause");
  329. break;
  330. }
  331. case 5: {
  332. inOrdem(raiz);
  333. system("pause");
  334. break;
  335. }
  336. case 6: {
  337. preOrdem(raiz);
  338. system("pause");
  339. break;
  340. }
  341. case 7: {
  342. posOrdem(raiz);
  343. system("pause");
  344. break;
  345. }
  346. }
  347. } */
  348. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!