SashkoKlincharov

[Java][АПС] - Recursive PreOrder

Feb 6th, 2020
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.11 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. class BNode<E> {
  7.  
  8. public E info;
  9. public BNode<E> left;
  10. public BNode<E> right;
  11.  
  12. static int LEFT = 1;
  13. static int RIGHT = 2;
  14.  
  15. public BNode(E info) {
  16. this.info = info;
  17. left = null;
  18. right = null;
  19. }
  20.  
  21. public BNode() {
  22. this.info = null;
  23. left = null;
  24. right = null;
  25. }
  26.  
  27. public BNode(E info, BNode<E> left, BNode<E> right) {
  28. this.info = info;
  29. this.left = left;
  30. this.right = right;
  31. }
  32.  
  33. }
  34.  
  35. class BTree<E> {
  36.  
  37. public BNode<E> root;
  38.  
  39. public BTree() {
  40. root = null;
  41. }
  42.  
  43. public BTree(E info) {
  44. root = new BNode<E>(info);
  45. }
  46.  
  47. public void makeRoot(E elem) {
  48. root = new BNode(elem);
  49. }
  50.  
  51. public void makeRootNode(BNode<E> node) {
  52. root = node;
  53. }
  54.  
  55. public BNode<E> addChild(BNode<E> node, int where, E elem) {
  56.  
  57. BNode<E> tmp = new BNode<E>(elem);
  58.  
  59. if (where == BNode.LEFT) {
  60. if (node.left != null) // veke postoi element
  61. return null;
  62. node.left = tmp;
  63. } else {
  64. if (node.right != null) // veke postoi element
  65. return null;
  66. node.right = tmp;
  67. }
  68.  
  69. return tmp;
  70. }
  71.  
  72. public BNode<E> addChildNode(BNode<E> node, int where, BNode<E> tmp) {
  73.  
  74. if (where == BNode.LEFT) {
  75. if (node.left != null) // veke postoi element
  76. return null;
  77. node.left = tmp;
  78. } else {
  79. if (node.right != null) // veke postoi element
  80. return null;
  81. node.right = tmp;
  82. }
  83.  
  84. return tmp;
  85. }
  86. public void printPreOrder(BNode<E> node) {
  87. if(node==null)
  88. return ;
  89. System.out.println(node.info);
  90. if(node.left!=null) {
  91. printPreOrder(node.left);
  92. }
  93. if(node.right!=null) {
  94. printPreOrder(node.right);
  95. }
  96. }
  97.  
  98. }
  99. public class RecursivePreOrder {
  100.  
  101. public static void main(String[] args) throws IOException {
  102. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  103. int n = Integer.parseInt(br.readLine());
  104. StringTokenizer st;
  105. BNode<String> [] nodes = new BNode[n];
  106. BTree<String> tree = new BTree<String>();
  107. for(int i=0;i<n;i++)
  108. nodes[i] = new BNode<String>();
  109.  
  110. for(int i=0;i<n;i++) {
  111. String line = br.readLine();
  112. st = new StringTokenizer(line);
  113. int index = Integer.parseInt(st.nextToken());
  114. nodes[index].info = st.nextToken();
  115. String action = st.nextToken();
  116. if(action.equals("LEFT")) {
  117. tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.LEFT, nodes[index]);
  118. }
  119. else if(action.equals("RIGHT")) {
  120. tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.RIGHT, nodes[index]);
  121. }
  122. else {
  123. tree.makeRootNode(nodes[index]);
  124. }
  125. }
  126. tree.printPreOrder(tree.root);
  127. }
  128.  
  129. }
Add Comment
Please, Sign In to add comment