API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 21st, 2017
76
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 20.39 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <ctype.h>
  6.  
  7. //#include "tree.h"
  8.  
  9. #define LEFT 0
  10. #define RIGHT 1
  11.  
  12. int p,k;
  13. int maior= -99999999;
  14.  
  15. typedef struct tnode *Tree;
  16. typedef struct tnode {
  17.     int value;
  18.     Tree child [2];
  19.     Tree parent;
  20.   } Tree_node;
  21.  
  22. /*---------------------------------*/
  23.  
  24. void tree_put (Tree *t, int x, int b);  /* pre !tree_parent (t); */
  25. Tree tree_cons (int x, Tree t, Tree u);  /* pre !tree_empty (t) <= !tree_parent (t), !tree_empty (u) <= !tree_parent (u); */
  26. Tree tree_cons_single (int x, Tree t, int b); /* pre !tree_parent (t); */
  27.  
  28. int tree_empty (Tree t);
  29. int tree_is_leaf (Tree t);  /* pre !tree_empty (t) */
  30. int tree_size (Tree t);
  31. int tree_count (Tree t, int x);
  32. int tree_levels (Tree t);
  33. int tree_height (Tree t); /* pre !tree_empty (t) */
  34. int tree_depth (Tree t); /* pre !tree_empty (t) */
  35. int tree_degree (Tree t);  /* pre !tree_empty (t); */
  36. int tree_side (Tree t); /* pre !tree_empty (t), !tree_empty (p->parent) */
  37.  
  38. int tree_root (Tree t);  /* pre !tree_empty (t); */
  39.  
  40. void tree_swap (Tree t, int b, Tree *u);  /* pre !tree_empty (t), !tree_empty (*u) <= !tree_parent (*u); */
  41. // Swaps b child of t with u
  42.  
  43. Tree tree_insert (Tree t, int x, int right1, int right2);   /* pre !tree_empty (t); */
  44. // Inserts a new node with value x as the right1 child of the tree t,
  45. // linking the current right1 child as the right2 child of the new node.
  46. // Returns the tree at the newly inserted node.
  47.  
  48. void tree_remove (Tree *t);   /* pre !tree_empty (t), tree_degree (t ) <= 1; */
  49.  
  50. int tree_has (Tree t, int x);
  51. Tree tree_find (Tree t, int x);
  52. void tree_free (Tree *s);
  53.  
  54. int tree_ok (Tree t);
  55.  
  56. void tree_write_parenthetically (FILE *f, Tree t);
  57. void tree_writeln_parenthetically (FILE *f, Tree t);
  58. void tree_write_star (FILE *f, Tree t);
  59. void tree_writeln_star (FILE *f, Tree t);
  60. void tree_write (FILE *f, char *fmt, Tree t);
  61. void tree_writeln (FILE *f, char *fmt, Tree t);
  62. void tree_write_indented (FILE *f, char *fmt, Tree t, int tab, int margin);
  63. void tree_write_indented_star (FILE *f, char *fmt, Tree t, int tab, int margin);
  64.  
  65. void tree_write_indented_prefix (FILE *f, char *fmt, Tree t, int tab, int margin);
  66. void tree_write_diagram (FILE *f, char *fmt, Tree t, int tab, int margin);
  67.  
  68. int ints_from_tree (Tree t, int *v);
  69. Tree tree_from_ints (int *v, int n);
  70.  
  71.  
  72.  
  73. Tree tree_from_string (char **s);
  74. void tree_to_string (Tree t, char **s);
  75.  
  76. Tree tree_next (Tree t);
  77. Tree tree_previous (Tree t);
  78. Tree tree_next2 (Tree t, int b);
  79. Tree tree_start (Tree t);
  80. Tree tree_finish (Tree t);
  81.  
  82. void tree_prefix (Tree t, void p (int));
  83. void tree_infix (Tree t, void p (int));
  84. void tree_postfix (Tree t, void p (int));
  85.  
  86. void tree_walk_directly (Tree t, void p (int));
  87. void tree_walk_reversely (Tree t, void p (int));
  88. int tree_fill_numbers (Tree t, int *v);
  89.  
  90. void tree_walk_directly_empty_recursive (Tree t);
  91. void tree_walk_directly_empty_iterative (Tree t);
  92.  
  93. Tree tree_promote (Tree t);
  94.  
  95. #undef max
  96. #undef min
  97.  
  98. int max (int x, int y);
  99. int min (int x, int y);
  100.  
  101. /*---------------------------*/
  102.  
  103.  
  104. int max (int x, int y)
  105. {
  106.   return x > y ? x : y;
  107. }
  108.  
  109. int min (int x, int y)
  110. {
  111.   return x < y ? x : y;
  112. }
  113.  
  114. int child_ok (Tree t)
  115. {
  116.   int result = 1;
  117.   int i;
  118.   assert (t != NULL);
  119.   for (i = 0; result && i < 2; i++)
  120.     result = t->child [i] == NULL || (t->child [i]->parent  == t && child_ok (t->child[i]));
  121.   return result;
  122. }
  123.  
  124. int tree_ok (Tree t)
  125. {
  126.   return t == NULL || (t->parent == NULL && child_ok (t));
  127. }
  128.  
  129. void tree_put (Tree *t, int x, int b)
  130. {
  131.   assert (tree_ok (*t));
  132.   assert (*t == NULL || (*t)->parent == NULL);
  133.   *t = tree_cons_single (x, *t, b);
  134.   assert (tree_ok (*t));
  135. }
  136.  
  137. Tree tree_cons_single (int x, Tree t, int b)
  138. {
  139.   assert (t == NULL || t->parent == NULL);
  140.   return b ? tree_cons (x, NULL, t) : tree_cons (x, t, NULL);
  141. }
  142.  
  143. Tree tree_cons (int x, Tree t, Tree u)
  144. {
  145.   Tree result = NULL;
  146.   assert (t == NULL || t->parent == NULL);
  147.   assert (u == NULL || u->parent == NULL);
  148.   result = (Tree) malloc (sizeof (Tree_node));
  149.   result -> value = x;
  150.   result -> child[0] = t;
  151.   if (t != NULL)
  152.     t -> parent = result;
  153.   result -> child[1] = u;
  154.   if (u != NULL)
  155.     u -> parent = result;
  156.   result -> parent = NULL;
  157.   return result;
  158. }
  159.  
  160. int tree_empty (Tree t)
  161. {
  162.   return t == NULL;
  163. }
  164.  
  165. int tree_root (Tree t)
  166. {
  167.   return t->value;
  168. }
  169.  
  170. int tree_is_leaf (Tree t)
  171. {
  172.   assert (t != NULL);
  173.   return t->child[0] == NULL && t->child[1] == NULL;
  174. }
  175.  
  176. int tree_size (Tree t)
  177. {
  178.   return t == NULL ? 0 : 1 + tree_size (t->child[0]) + tree_size (t->child[1]);
  179. }
  180.  
  181. int tree_count (Tree t, int x)
  182. {
  183.   return t == NULL ? 0 : (t->value == x) + tree_count (t->child[0], x) + tree_count (t->child[1], x);
  184. }
  185.  
  186. int nc;
  187.  
  188. int tree_levels (Tree t)
  189. {
  190.   return t == NULL ? 0 : 1 + max (tree_levels (t->child [0]), tree_levels (t->child[1]));
  191. }
  192.  
  193. int tree_height (Tree t)
  194. {
  195.   return tree_levels (t) - 1;
  196. }
  197.  
  198. int tree_depth (Tree t)
  199. {
  200.   int result = 0;
  201.   assert (t != NULL);
  202.   while (t->parent != NULL)
  203.   {
  204.     result++;
  205.     t = t->parent;
  206.   }
  207.   return result;
  208. }
  209.  
  210.  
  211. int tree_degree (Tree t)
  212. {
  213.   assert (t != NULL);
  214.   return (t->child[0] != NULL) + (t->child[1] != NULL);
  215. }
  216.  
  217. //int tree_at_root (Tree t)
  218. //{
  219. //  assert (!tree_empty (t));
  220. //  return t->parent == NULL;
  221. //}
  222. //
  223. //Tree tree_child (Tree t, int b)
  224. //{
  225. //  assert (!tree_empty (t));
  226. //  return t->child [b];
  227. //}
  228. //
  229. //Tree tree_left (Tree t)
  230. //{
  231. //  assert (!tree_empty (t));
  232. //  return t->child [0];
  233. //}
  234. //
  235. //Tree tree_right (Tree t)
  236. //{
  237. //  assert (!tree_empty (t));
  238. //  return t->child [1];
  239. //}
  240.  
  241. Tree tree_first_child_0 (Tree t)
  242. {
  243.   assert (t != NULL);
  244.   return t->child [0] != NULL ? t->child [0] : t->child [1];
  245. }
  246.  
  247. Tree tree_first_child (Tree t)
  248. {
  249.   assert (t != NULL);
  250.   return t->child [t->child [0] == NULL];
  251. }
  252.  
  253.  
  254. //Tree tree_parent (Tree t)
  255. //{
  256. //  assert (!tree_empty (t));
  257. //  return t->parent;
  258. //}
  259.  
  260. int tree_side (Tree t)
  261. {
  262.   assert (t != NULL);
  263.   assert (t->parent != NULL);
  264.   return t->parent->child [1] == t;
  265. }
  266.  
  267. //void tree_set_value (Tree t, int x)
  268. //{
  269. //  assert (!tree_empty (t));
  270. //  t -> value = x;
  271. //}
  272. //
  273. //void tree_link (Tree t, Tree *u, int b)
  274. //{
  275. //  assert (t != NULL);
  276. //  assert (t -> child[b] == NULL);
  277. //  assert (u == NULL || (*u)->parent == NULL);
  278. //  t->child[b] = *u;
  279. //  if (*u != NULL)
  280. //    (*u)->parent = t;
  281. //  *u = NULL;
  282. //}
  283. //
  284. //void tree_unlink (Tree t, int b, Tree *u)
  285. //{
  286. //  Tree z;
  287. //  assert (t != NULL);
  288. //  z = *u;
  289. //  *u = t->child[b];
  290. //  t->child[b] = z;
  291. //  if (z != NULL)
  292. //    z->parent = t;
  293. //  if (*u == NULL)
  294. //    (*u)->parent = NULL;
  295. //}
  296.  
  297. void tree_swap (Tree t, int b, Tree *u)
  298. {
  299.   Tree z;
  300.   assert (t != NULL);
  301.   assert (*u == NULL || (*u)->parent == NULL);
  302.   z = *u;
  303.   *u = t->child[b];
  304.   t->child[b] = z;
  305.   if (z != NULL)
  306.     z->parent = t;
  307.   if (*u != NULL)
  308.     (*u)->parent = NULL;
  309. }
  310.  
  311. // inserts a new node with value x as the right1 child of the tree t
  312. // linking the current right1 child as the right2 child of the new node.
  313. // return the tree whose root is the newly inserted node.
  314. Tree tree_insert (Tree t, int x, int right1, int right2)
  315. {
  316.   Tree u = NULL;
  317.   assert (child_ok (t));
  318.   assert (!tree_empty (t));
  319.   tree_swap (t, right1, &u);
  320.   //u = tree_cons_single (x, u, right2);
  321.   tree_put (&u, x, right2);
  322.   tree_swap (t, right1, &u);
  323.   assert (child_ok (t));
  324.   return t->child[right1];
  325. }
  326.  
  327. void tree_remove1 (Tree *t)
  328. {
  329.   Tree z;
  330.   Tree f;
  331.   assert (!tree_empty (*t));
  332.   assert (tree_degree (*t) <= 1);
  333.   z = *t;
  334.   f = tree_first_child (z);
  335.   tree_writeln_star (stdout, f);
  336.   if (z->parent == NULL)
  337.   {
  338.     if (f != NULL)
  339.       f ->parent = NULL;
  340.     *t = f;
  341.   }
  342.   else
  343.   {
  344.     int side = tree_side (z);  // Is *t a right child?
  345.     *t = f;  
  346.     z->parent->child [side] = f;
  347.     if (f != NULL)
  348.       f ->parent = z->parent;
  349.   }
  350.   free (z);
  351. }
  352.  
  353. void tree_remove_version1 (Tree *t)
  354. {
  355.   Tree p;
  356.   assert (*t != NULL);
  357.   assert (tree_degree (*t) <= 1);
  358.   if ((p = (*t) -> parent) == NULL)
  359.   {
  360.     Tree z = *t;
  361.     *t = tree_first_child (*t);
  362.     if ((*t) != NULL)
  363.       (*t) -> parent = NULL;
  364.     free (z);
  365.   }
  366.   else
  367.   {
  368.     Tree u = NULL;
  369.     int side = tree_side (*t);
  370.     tree_swap (p, side, &u);
  371.     tree_remove (&u);
  372.     tree_swap (p, side, &u);
  373.     *t = p->child [side];
  374.   }
  375. }
  376.  
  377. void tree_remove (Tree *t)
  378. {
  379.   Tree p;
  380.   assert (*t != NULL);
  381.   assert (tree_degree (*t) <= 1);
  382.   if ((p = (*t) -> parent) == NULL)
  383.   {
  384.     Tree z = *t;
  385.     *t = tree_first_child (*t);
  386.     if ((*t) != NULL)
  387.       (*t) -> parent = NULL;
  388.     free (z);
  389.   }
  390.   else
  391.   {
  392.     Tree u = NULL;
  393.     int side = tree_side (*t);
  394.     tree_swap (p, side, &u);
  395.     tree_remove (&u);
  396.     tree_swap (p, side, &u);
  397.     *t = p;
  398.   }
  399. }
  400.  
  401. void tree_remove0 (Tree *t)
  402. {
  403.   Tree z = NULL;
  404.   Tree f = NULL;
  405.   assert (!tree_empty (*t));
  406.   assert (tree_degree (*t) <= 1);
  407.   z = *t;
  408.   f = tree_first_child (z);
  409.   //tree_writeln_star (stdout, f);
  410.   if (z->parent != NULL)
  411.     z->parent->child [tree_side (z)] = f;
  412.   if (f != NULL)
  413.     f ->parent = z->parent;
  414.   *t = f;  
  415.   free (z);
  416. }
  417.  
  418. int tree_has (Tree t, int x)
  419. {
  420.   return t != NULL && (t->value == x || tree_has (t->child[0], x) || tree_has (t->child[1], x));
  421. }
  422.  
  423. Tree tree_find (Tree t, int x)
  424. {
  425.   Tree result = NULL;
  426.   if (t != NULL)
  427.   {
  428.     if (t->value == x)
  429.       result = t;
  430.     if (result == NULL)
  431.       result = tree_find (t->child[0], x);
  432.     if (result == NULL)
  433.       result = tree_find (t->child[1], x);
  434.   }
  435.   return result;
  436. }
  437.  
  438. void tree_free_here (Tree t)
  439. {
  440.   if (t != NULL)
  441.   {
  442.     tree_free_here (t->child[0]);
  443.     tree_free_here (t->child[1]);
  444.     free (t);
  445.   }
  446. }
  447.  
  448. void tree_free0 (Tree *t)
  449. {
  450.   tree_free_here (*t);
  451.   *t = NULL;
  452. }
  453.  
  454. void tree_free (Tree *t)
  455. {
  456.   Tree z = *t;
  457.   if (z != NULL)
  458.   {
  459.     tree_free_here (z->child[0]);
  460.     tree_free_here (z->child[1]);
  461.     free (z);
  462.   }
  463.   *t = NULL;
  464. }
  465.  
  466. void tree_write_star (FILE *f, Tree t)
  467. {
  468.   if (t == NULL)
  469.     fprintf (f, "*");
  470.   else
  471.   {
  472.     fprintf (f, "(%d", t->value);
  473.     tree_write_star (f, t->child[0]);
  474.     tree_write_star (f, t->child[1]);
  475.     fprintf (f, ")");
  476.   }
  477. }
  478.  
  479. void tree_writeln_star (FILE *f, Tree t)
  480. {
  481.   tree_write_star (f, t);
  482.   fprintf (f, "\n");
  483. }
  484.  
  485. void tree_write_parenthetically (FILE *f, Tree t)
  486. {
  487.   fprintf (f, "(");
  488.   if (t)
  489.   {
  490.     fprintf (f, "%d", t->value);
  491.     tree_write_parenthetically (f, t->child[0]);
  492.     tree_write_parenthetically (f, t->child[1]);
  493.   }
  494.   fprintf (f, ")");
  495. }
  496.  
  497. void tree_writeln_parenthetically (FILE *f, Tree t)
  498. {
  499.   tree_write_parenthetically (f, t);
  500.   fprintf (f, "\n");
  501. }
  502.  
  503. void tree_write (FILE *f, char *fmt, Tree t)
  504. {
  505.   if (t)
  506.   {
  507.     tree_write (f, fmt, t->child[0]);
  508.     fprintf (f, fmt, t->value);
  509.     tree_write (f, fmt, t->child[1]);
  510.   }
  511. }
  512.  
  513. void tree_writeln (FILE *f, char *fmt, Tree t)
  514. {
  515.   tree_write (f, fmt, t);
  516.   fprintf (f, "\n");
  517. }
  518.  
  519. void tree_write_indented (FILE *f, char *fmt, Tree t, int tab, int margin)
  520. {
  521.   if (t)
  522.   {
  523.     tree_write_indented (f, fmt, t->child[1], tab, tab + margin);
  524.     fprintf (f, "%*s", margin, "");
  525.     fprintf (f, fmt, t->value);
  526.     fprintf (f, "\n");
  527.     tree_write_indented (f, fmt, t->child[0], tab, tab + margin);
  528.   }
  529. }
  530.  
  531. void tree_write_indented_star (FILE *f, char *fmt, Tree t, int tab, int margin)
  532. {
  533.   if (t)
  534.   {
  535.     tree_write_indented_star (f, fmt, t->child[1], tab, tab + margin);
  536.     fprintf (f, "%*s", margin, "");
  537.     fprintf (f, fmt, t->value);
  538.     fprintf (f, "\n");
  539.     tree_write_indented_star (f, fmt, t->child[0], tab, tab + margin);
  540.   }
  541.   else
  542.     fprintf (f, "%*s%s\n", margin, "", "*");
  543. }
  544.  
  545. void tree_write_indented_prefix (FILE *f, char *fmt, Tree t, int tab, int margin)
  546. {
  547.   if (t)
  548.   {
  549.     fprintf (f, "%*s", margin, "");
  550.     fprintf (f, fmt, t->value);
  551.     fprintf (f, "\n");
  552.     tree_write_indented_prefix (f, fmt, t->child[0], tab, tab + margin);
  553.     tree_write_indented_prefix (f, fmt, t->child[1], tab, tab + margin);
  554.   }
  555.   else
  556.     fprintf (f, "%*s%s\n", margin, "", "-");
  557. }
  558.  
  559. void tree_write_diagram (FILE *f, char *fmt, Tree t, int tab, int margin)
  560. {
  561.   if (t)
  562.   {
  563.     tree_write_diagram (f, fmt, t->child[1], tab, tab + margin);
  564.     fprintf (f, "%*s", margin, "");
  565.     fprintf (f, fmt, t->value);
  566.     fprintf (f, "\n");
  567.     tree_write_diagram (f, fmt, t->child[0], tab, tab + margin);
  568.   }
  569.   else
  570.     fprintf (f, "%*s%s\n", margin, "", "-");
  571. }
  572.  
  573. void tree_to_numbers0 (Tree t, int *v, int *n)
  574. {
  575.   *n = 0;
  576.   if (t)
  577.   {
  578.     int n0 = 0;
  579.     int n1 = 0;
  580.     tree_to_numbers0 (t->child[0], v, &n0);
  581.     v[n0] = t->value;
  582.     tree_to_numbers0 (t->child[1], v+n0+1, &n1);
  583.     *n = n0 + 1 + n1;
  584.   }
  585. }
  586.  
  587. int ints_from_tree (Tree t, int *v)
  588. {
  589.   int result = 0;
  590.   if (t != NULL)
  591.   {
  592.     int n0 = ints_from_tree (t->child[0], v);
  593.     int n1 = ints_from_tree (t->child[1], v+n0+1);
  594.     v[n0] = t->value;
  595.     result = n0 + n1 + 1;
  596.   }
  597.   return result;
  598. }
  599.  
  600. Tree tree_from_ints (int *v, int n)
  601. {
  602.   return n <= 0 ? NULL : tree_cons (v[n/2], tree_from_ints (v, n/2), tree_from_ints (v+n/2+1, n-(n/2+1)));
  603. }
  604.  
  605. Tree tree_next (Tree t)
  606. {
  607.   assert (t != NULL);
  608.   if (t->child [RIGHT] != NULL)
  609.   {
  610.     t = t->child [RIGHT];
  611.     while (t->child [LEFT] != NULL)
  612.       t = t->child [LEFT];
  613.   }
  614.   else
  615.   {
  616.     Tree p = t;
  617.     t = t->parent;
  618.     while (t != NULL && p != t->child [LEFT])
  619.     {
  620.       p = p->parent;
  621.       t = t->parent;
  622.     }
  623.   }
  624.   return t;
  625. }
  626.  
  627. Tree tree_following (Tree t, int right)
  628. {
  629.   assert (t != NULL);
  630.   if (t->child [right] != NULL)
  631.   {
  632.     t = t->child [right];
  633.     while (t->child [!right] != NULL)
  634.       t = t->child [!right];
  635.   }
  636.   else
  637.   {
  638.     Tree p = t;
  639.     t = t->parent;
  640.     while (t != NULL && p != t->child [!right])
  641.     {
  642.       p = p->parent;
  643.       t = t->parent;
  644.     }
  645.   }
  646.   return t;
  647. }
  648.  
  649. Tree tree_previous (Tree t)
  650. {
  651.   return tree_following (t, LEFT);
  652. }
  653.  
  654. Tree tree_start (Tree t)
  655. {
  656.   assert (t != NULL);
  657.   while (t->child [LEFT] != NULL)
  658.     t = t->child [LEFT];
  659.   return t;
  660. }
  661.  
  662. Tree tree_finish (Tree t)
  663. {
  664.   assert (t != NULL);
  665.   while (t->child [RIGHT] != NULL)
  666.     t = t->child [RIGHT];
  667.   return t;
  668. }
  669.  
  670. void tree_prefix (Tree t, void p (int))
  671. {
  672.   if (t != NULL)
  673.   {
  674.     p (t->value);
  675.     tree_prefix (t->child[0], p);
  676.     tree_prefix (t->child[1], p);
  677.   }
  678. }
  679.  
  680. void tree_infix (Tree t, void p (int))
  681. {
  682.   if (t != NULL)
  683.   {
  684.     tree_infix (t->child[0], p);
  685.     p (t->value);
  686.     tree_infix (t->child[1], p);
  687.   }
  688. }
  689.  
  690. void tree_walk_directly (Tree t, void p (int))
  691. {
  692.   if (t != NULL)
  693.   {
  694.     tree_walk_directly (t->child[0], p);
  695.     p (t->value);
  696.     tree_walk_directly (t->child[1], p);
  697.   }
  698. }
  699.  
  700. void tree_walk_reversely (Tree t, void p (int))
  701. {
  702.   if (t != NULL)
  703.   {
  704.     tree_walk_reversely (t->child[1], p);
  705.     p (t->value);
  706.     tree_walk_reversely (t->child[0], p);
  707.   }
  708. }
  709.  
  710. void tree_postfix (Tree t, void p (int))
  711. {
  712.   if (t != NULL)
  713.   {
  714.     tree_postfix (t->child[0], p);
  715.     tree_postfix (t->child[1], p);
  716.     p (t->value);
  717.   }
  718. }
  719.  
  720. int count_digits (int n)
  721. {
  722.   int result = 1;
  723.   while (n >= 10)
  724.   {
  725.     n /= 10;
  726.     result++;
  727.   }
  728.   return result;
  729. }
  730.  
  731. Tree tree_from_string (char **s)
  732. {
  733.   Tree result = NULL;
  734.   char *p = *s;
  735.   assert (*p == '*' || *p == '(');
  736.   if (*p++ == '(')
  737.   {
  738.     int r;
  739.     Tree t;
  740.     Tree u;
  741.     assert (isdigit (*p));
  742.     sscanf (p, "%d", &r);
  743.     p += count_digits (r);
  744.     if (!(*p == '*' || *p == '('))
  745.       printf (":::%s:::\n", p);
  746.     assert (*p == '*' || *p == '(');
  747.     t = tree_from_string (&p);
  748.     u = tree_from_string (&p);
  749.     assert (*p == ')');
  750.     p++;
  751.     result = tree_cons (r, t, u);
  752.   }
  753.   *s = p;
  754.   return result;
  755. }
  756.  
  757. void tree_to_string (Tree t, char **s)
  758. {
  759.   char *p = *s;
  760.   if (t == NULL)
  761.     p += sprintf (p, "*");
  762.   else
  763.   {
  764.     p += sprintf (p, "(%d", t->value);
  765.     tree_to_string (t->child[0], &p);
  766.     tree_to_string (t->child[1], &p);
  767.     p += sprintf (p, ")");
  768.   }
  769.   *s = p;
  770. }
  771.  
  772. //void tree_fill_numbers_here (Tree t, int**v)
  773. //{
  774. //  int *p = *v;
  775. //  if (t != NULL)
  776. //  {
  777. //    tree_fill_numbers_here (t->child[0], &p);
  778. //    //printf ("%d\n", t->value);
  779. //    *p++ = t->value;
  780. //    tree_fill_numbers_here (t->child[1], &p);
  781. //  }
  782. //  *v = p;
  783. //}
  784.  
  785. void tree_fill_numbers_here (Tree t, int**v)
  786. {
  787.   if (t != NULL)
  788.   {
  789.     tree_fill_numbers_here (t->child[0], v);
  790.     //printf ("%d\n", t->value);
  791.     *(*v)++ = t->value;
  792.     tree_fill_numbers_here (t->child[1], v);
  793.   }
  794. }
  795.  
  796. int tree_fill_numbers (Tree t, int *v)
  797. {
  798.   int *p = v;
  799.   tree_fill_numbers_here (t, &p);
  800.   return p-v;
  801. }
  802.  
  803. void tree_walk_directly_empty_recursive (Tree t)
  804. {
  805.   if (t != NULL)
  806.   {
  807.     tree_walk_directly_empty_recursive (t->child[0]);
  808.     tree_walk_directly_empty_recursive (t->child[1]);
  809.   }
  810. }
  811.  
  812. void tree_walk_directly_empty_iterative (Tree t)
  813. {
  814.   t = tree_start (t);
  815.   while (t != NULL)
  816.     t = tree_next (t);
  817. }
  818.  
  819. Tree tree_promote (Tree t)
  820. {
  821.   int side = tree_side (t);
  822.   Tree p = t->parent;
  823.   t -> parent = p->parent;
  824.   if (t->parent != NULL)
  825.     t -> parent -> child [tree_side (p)] = t;
  826.   p -> child [side] = t->child [!side];
  827.   if (p -> child [side] != NULL)
  828.     p -> child [side] -> parent = p;
  829.   t -> child [!side] = p;
  830.   p->parent = t;
  831.   return t;
  832. }
  833.  
  834.  
  835. void int_ (int x)
  836. {
  837.    
  838.     if (p==1)
  839.     {
  840.         printf(" %d", x);
  841.     }
  842.     else
  843.     {
  844.         printf("%d", x);
  845.         p=1;
  846.     }
  847. }
  848.  
  849. int tree_sum (Tree t)
  850. {
  851.     if (t)
  852.     {
  853.         return t->value + tree_sum(t->child[0]) + tree_sum(t->child[1]);
  854.     }
  855.     else
  856.     {
  857.         return 0;
  858.     }
  859. }
  860.  
  861. void maximo (int x)
  862. {
  863.     if (x>maior)
  864.     {
  865.         maior = x;
  866.     }
  867. }
  868.  
  869. int verifica_se_folha (Tree t)
  870. {
  871.     return t == NULL ? 0 : t->child[0]==NULL && t->child[1]==NULL;
  872. }
  873.  
  874. void imprime_folhas (Tree t)
  875. {
  876.     if (t!=NULL)
  877.     {
  878.         if (verifica_se_folha(t) && k==0)
  879.         {
  880.             k=1;
  881.             printf("%d", t->value);
  882.         }
  883.         else if (verifica_se_folha(t) && k==1)
  884.         {
  885.             printf(" %d", t->value);
  886.         }
  887.         imprime_folhas(t->child[0]);
  888.         imprime_folhas(t->child[1]);
  889.     }
  890. }
  891.  
  892. void elimina_folhas (Tree t)
  893. {
  894.     if (t!=NULL)
  895.     {
  896.         if (verifica_se_folha(t))
  897.         {
  898.             tree_remove(&t);
  899.         }
  900.         elimina_folhas(t->child[0]);
  901.         elimina_folhas(t->child[1]);
  902.     }
  903. }
  904.  
  905. void somar1 (Tree t, int y, int z)
  906. {
  907.     if (t != NULL)
  908.     {
  909.         if (t->value <=z && t->value >=y)
  910.         {
  911.             t->value = t->value +1;
  912.         }
  913.         somar1(t->child[0],y,z);
  914.         somar1(t->child[1],y,z);
  915.     }
  916. }
  917.  
  918. void task_a (void)
  919. {
  920.     char k;
  921.     Tree arvores[101];
  922.     while (scanf("%c", &k)!=EOF)
  923.     {
  924.         if (k== 'C')
  925.         {
  926.             int x,y,z,w;
  927.  
  928.             scanf("%d %d %d %d", &x, &y, &z, &w);
  929.  
  930.             if (z==-1 && w==-1)
  931.             {
  932.                 arvores[x]=tree_cons(y,NULL,NULL);
  933.             }
  934.             else if (z==-1 && w!=-1)
  935.             {
  936.                 arvores[x]=tree_cons(y,NULL,arvores[w]);
  937.             }
  938.             else if (z!=-1 && w==-1)
  939.             {
  940.                 arvores[x]=tree_cons(y,arvores[z],NULL);
  941.             }
  942.             else
  943.             {
  944.                 arvores[x]=tree_cons(y,arvores[z],arvores[w]);
  945.             }
  946.         }
  947.         if (k== 'Z')
  948.         {
  949.             int x;
  950.             scanf("%d", &x);
  951.             printf("%d\n", tree_size (arvores[x]));
  952.         }
  953.         if (k== 'H')
  954.         {
  955.             int x;
  956.             scanf("%d", &x);
  957.             printf("%d\n", tree_height (arvores[x]));
  958.         }
  959.         if (k== 'R')
  960.         {
  961.             int x;
  962.             scanf("%d", &x);
  963.             tree_remove(&arvores[x]);
  964.         }
  965.         if (k== 'W')
  966.         {
  967.             int x;
  968.             scanf("%d", &x);
  969.             tree_writeln_star (stdout, arvores[x]);
  970.         }
  971.         if (k== 'D')
  972.         {
  973.             int x;
  974.             scanf("%d", &x);
  975.             p=0;
  976.  
  977.             if (arvores[x] == NULL)
  978.             {
  979.                 printf("NULL\n");
  980.             }
  981.             else
  982.             {
  983.                 tree_walk_directly(arvores[x], int_);
  984.                 printf("\n");
  985.             }
  986.         }
  987.         if (k== 'U')
  988.         {
  989.             int x;
  990.             scanf("%d", &x);
  991.             p=0;
  992.  
  993.             if (arvores[x] == NULL)
  994.             {
  995.                 printf("NULL\n");
  996.             }
  997.             else
  998.             {
  999.                 tree_walk_reversely(arvores[x], int_);
  1000.                 printf("\n");
  1001.             }
  1002.            
  1003.         }
  1004.         if (k== 'S')
  1005.         {
  1006.             int x;
  1007.             scanf("%d", &x);
  1008.             if (arvores[x])
  1009.             {
  1010.                 printf("%d\n", tree_sum(arvores[x]));
  1011.             }
  1012.         }
  1013.         if (k== 'M')
  1014.         {
  1015.             int x;
  1016.             scanf("%d", &x);
  1017.             if (arvores[x])
  1018.             {
  1019.                 tree_walk_directly(arvores[x], maximo);
  1020.             }
  1021.             printf("%d\n", maior);
  1022.         }
  1023.         if (k== 'F')
  1024.         {
  1025.             int x,y;
  1026.             scanf("%d %d", &x, &y);
  1027.             printf("%d\n", tree_count(arvores[x], y));
  1028.         }
  1029.         if (k== 'L')
  1030.         {
  1031.             int x;
  1032.             scanf("%d", &x);
  1033.             if (arvores[x])
  1034.             {
  1035.                 k=0;
  1036.                 imprime_folhas(arvores[x]);
  1037.                 printf("\n");
  1038.             }
  1039.         }
  1040.         if (k== 'T')
  1041.         {
  1042.             int x;
  1043.             scanf("%d", &x);
  1044.             if (arvores[x])
  1045.             {
  1046.                 elimina_folhas(arvores[x]);
  1047.             }
  1048.         }
  1049.         if (k== 'Y')
  1050.         {
  1051.             int x,y,z;
  1052.             scanf("%d %d %d", &x, &y, &z);
  1053.             if (y<=z)
  1054.             {
  1055.                 somar1(arvores[x],y,z);
  1056.             }
  1057.         }
  1058.     }
  1059. }
  1060.  
  1061. int main (void)
  1062. {
  1063.     task_a();
  1064.     return 0;
  1065. }
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!