Mitko_jos

za kiko :)

Dec 7th, 2014
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.88 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.StringTokenizer;
  4. class BNodeN<E> {
  5.  
  6. public E info;
  7. public BNodeN<E> left;
  8. public BNodeN<E> right;
  9. char ltag;
  10. char rtag;
  11.  
  12. static int LEFT = 1;
  13. static int RIGHT = 2;
  14.  
  15. public BNodeN(E info) {
  16. this.info = info;
  17. left = null;
  18. right = null;
  19. ltag = '-';
  20. rtag = '-';
  21. }
  22.  
  23. }
  24. class BTree<E> {
  25.  
  26. public BNodeN<E> head;
  27.  
  28. public BTree() {
  29. head = new BNodeN<E>(null);
  30. // po definicija ako nema koren, t.e. ako stebloto e prazno
  31. head.left = head;
  32. head.ltag = '-';
  33. // kaj vodacot sekogas desnata vrska pokazuva kon samiot sebe
  34. head.right = head;
  35. head.rtag = '+';
  36. }
  37.  
  38. public BNodeN<E> makeRoot(E elem) {
  39. BNodeN<E> tmp = new BNodeN<E>(elem);
  40. head.left = tmp;
  41. head.ltag = '+';
  42.  
  43. tmp.left = head;
  44. tmp.ltag = '-';
  45. tmp.right = head;
  46. tmp.rtag = '-';
  47.  
  48. return tmp;
  49. }
  50.  
  51. public BNodeN<E> makeRootNode(BNodeN<E> tmp) {
  52. head.left = tmp;
  53. head.ltag = '+';
  54.  
  55. tmp.left = head;
  56. tmp.ltag = '-';
  57. tmp.right = head;
  58. tmp.rtag = '-';
  59.  
  60. return tmp;
  61. }
  62.  
  63. public BNodeN<E> addChild(BNodeN<E> node, int where, E elem) {
  64. BNodeN<E> tmp = new BNodeN<E>(elem);
  65.  
  66. if (where == BNodeN.LEFT) {
  67.  
  68. if (node.ltag == '+') // veke postoi element
  69. return null;
  70.  
  71. tmp.left = node.left;
  72. tmp.ltag = '-';
  73. tmp.right = node;
  74. tmp.rtag = '-';
  75. node.left = tmp;
  76. node.ltag = '+';
  77. } else {
  78.  
  79. if (node.rtag == '+') // veke postoi element
  80. return null;
  81.  
  82. tmp.right = node.right;
  83. tmp.rtag = '-';
  84. tmp.left = node;
  85. tmp.ltag = '-';
  86. node.right = tmp;
  87. node.rtag = '+';
  88. }
  89.  
  90. return tmp;
  91. }
  92.  
  93. public BNodeN<E> addChildNode(BNodeN<E> node, int where, BNodeN<E> tmp) {
  94.  
  95. if (where == BNodeN.LEFT) {
  96.  
  97. if (node.ltag == '+') // veke postoi element
  98. return null;
  99.  
  100. tmp.left = node.left;
  101. tmp.ltag = '-';
  102. tmp.right = node;
  103. tmp.rtag = '-';
  104. node.left = tmp;
  105. node.ltag = '+';
  106. } else {
  107.  
  108. if (node.rtag == '+') // veke postoi element
  109. return null;
  110.  
  111. tmp.right = node.right;
  112. tmp.rtag = '-';
  113. tmp.left = node;
  114. tmp.ltag = '-';
  115. node.right = tmp;
  116. node.rtag = '+';
  117. }
  118.  
  119. return tmp;
  120. }
  121.  
  122. public BNodeN<E> insertRight(BNodeN<E> parent, E info) {
  123.  
  124. BNodeN<E> child = new BNodeN<E>(info);
  125.  
  126. child.ltag = '-';
  127. child.left = parent;
  128. child.rtag = parent.rtag;
  129. child.right = parent.right;
  130.  
  131. parent.right = child;
  132. parent.rtag = '+';
  133.  
  134. if (child.rtag == '+') {
  135. BNodeN<E> temp = child.right;
  136. while (temp.ltag == '+')
  137. temp = temp.left;
  138. temp.left = child;
  139. }
  140.  
  141. return child;
  142. }
  143.  
  144. public BNodeN<E> predecessorInorder(BNodeN<E> node) {
  145.  
  146. if (node.ltag == '-')
  147. return node.left;
  148.  
  149. BNodeN<E> p = node.left;
  150. while (p.rtag == '+')
  151. p = p.right;
  152.  
  153. return p;
  154. }
  155.  
  156. public BNodeN<E> successorInorder(BNodeN<E> node) {
  157.  
  158. if (node.rtag == '-')
  159. return node.right;
  160.  
  161. BNodeN<E> p = node.right;
  162. while (p.ltag == '+')
  163. p = p.left;
  164.  
  165. return p;
  166. }
  167.  
  168. }
  169. public class ConsecutiveNumbers {
  170.  
  171. public static void main(String[] args) throws Exception {
  172. int i,j,k;
  173.  
  174. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  175. StringTokenizer st;
  176. int N = Integer.parseInt(br.readLine());
  177. BNodeN<Integer> nodes[] = new BNodeN[N];
  178. BTree<Integer> tree = new BTree<Integer>();
  179.  
  180. for (i=0;i<N;i++)
  181. nodes[i] = null;
  182.  
  183. for (i = 0; i < N; i++) {
  184. String line = br.readLine();
  185. st = new StringTokenizer(line);
  186. int index = Integer.parseInt(st.nextToken());
  187. nodes[index] = new BNodeN<Integer>(Integer.parseInt(st.nextToken()));
  188. String action = st.nextToken();
  189. if (action.equals("LEFT")) {
  190. tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNodeN.LEFT, nodes[index]);
  191. } else if (action.equals("RIGHT")) {
  192. tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNodeN.RIGHT, nodes[index]);
  193. } else {
  194. // this node is the root
  195. tree.makeRootNode(nodes[index]);
  196. }
  197. }
  198.  
  199. br.close();
  200. boolean f = false;
  201. if (tree.head.ltag== '-')
  202. return;
  203. BNodeN<Integer> p = tree.head.left;
  204. while (p.ltag== '+')
  205. p = p.left;
  206. while (p != tree.head) {
  207. int t = p.info;
  208. p = tree.successorInorder(p);
  209. if(p!=tree.head)
  210. if(t+1!=p.info){
  211. f = true;
  212. break;
  213. }
  214. }
  215.  
  216.  
  217. if(f){
  218. f = false;
  219. System.out.println(false);
  220. }
  221. else
  222. System.out.println(true);
  223.  
  224. }
  225.  
  226. }
Advertisement
Add Comment
Please, Sign In to add comment