Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.87 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayDeque;
  4. import java.util.Deque;
  5. import java.util.StringTokenizer;
  6. import java.util.NoSuchElementException;
  7.  
  8. class BNode<E> {
  9.    
  10.     public E info;
  11.     public BNode<E> left;
  12.     public BNode<E> right;
  13.    
  14.     static int LEFT = 1;
  15.     static int RIGHT = 2;
  16.    
  17.     public BNode(E info) {
  18.         this.info = info;
  19.         left = null;
  20.         right = null;
  21.     }
  22.    
  23.     public BNode() {
  24.         this.info = null;
  25.         left = null;
  26.         right = null;
  27.     }
  28.    
  29.     public BNode(E info, BNode<E> left, BNode<E> right) {
  30.         this.info = info;
  31.         this.left = left;
  32.         this.right = right;
  33.     }
  34.    
  35. }
  36.  
  37. class BTree<E> {
  38.    
  39.     public BNode<E> root;
  40.    
  41.     public BTree() {
  42.         root = null;
  43.     }
  44.    
  45.     public BTree(E info) {
  46.         root = new BNode<E>(info);
  47.     }
  48.    
  49.     public void makeRoot(E elem) {
  50.         root = new BNode(elem);
  51.     }
  52.    
  53.     public void makeRootNode(BNode<E> node) {
  54.         root = node;
  55.     }
  56.    
  57.     public BNode<E> addChild(BNode<E> node, int where, E elem) {
  58.        
  59.         BNode<E> tmp = new BNode<E>(elem);
  60.        
  61.         if (where == BNode.LEFT) {
  62.             if (node.left != null)  // veke postoi element
  63.                 return null;
  64.             node.left = tmp;
  65.         } else {
  66.             if (node.right != null) // veke postoi element
  67.                 return null;
  68.             node.right = tmp;
  69.         }
  70.        
  71.         return tmp;
  72.     }
  73.    
  74.     public BNode<E> addChildNode(BNode<E> node, int where, BNode<E> tmp) {
  75.        
  76.         if (where == BNode.LEFT) {
  77.             if (node.left != null)  // veke postoi element
  78.                 return null;
  79.             node.left = tmp;
  80.         } else {
  81.             if (node.right != null) // veke postoi element
  82.                 return null;
  83.             node.right = tmp;
  84.         }
  85.        
  86.         return tmp;
  87.     }
  88.    
  89.  
  90.    
  91.     public void findElement(int vrednost){
  92.         BNode<E> element = findElement(this.root, vrednost);
  93.         System.out.println(getSumLeft(element.left, vrednost)+" "+getSumRight(element.right,vrednost));
  94.     }
  95.    
  96.     public int getSumRight(BNode<E> element, int comparingValue){
  97.        
  98.        
  99.         if(element == null)
  100.             return 0;      
  101.        
  102.         int valueElement = Integer.parseInt(element.info.toString());
  103.        
  104.         if(element.left == null&&element.right == null){
  105.                
  106.                 if(valueElement > comparingValue)
  107.                     return valueElement;   
  108.         }
  109.        
  110.         if(element.left != null&&element.right != null){
  111.             if(valueElement > comparingValue)
  112.                 return valueElement + getSumRight(element.left, comparingValue) + getSumRight(element.right, comparingValue);
  113.             else
  114.                 return getSumRight(element.left, comparingValue) + getSumRight(element.right, comparingValue);
  115.         }
  116.  
  117.         if(element.left == null&&element.right != null){
  118.             if(valueElement > comparingValue)
  119.                 return valueElement + getSumRight(element.right, comparingValue);
  120.             else
  121.                 return getSumRight(element.right, comparingValue);
  122.         }
  123.        
  124.         if(element.left != null && element.right == null){
  125.             if(valueElement > comparingValue)
  126.                 return valueElement + getSumRight(element.left, comparingValue);
  127.             else
  128.                 return getSumRight(element.left, comparingValue);
  129.         }
  130.         return 0;
  131.     }
  132.    
  133.    
  134.     public int getSumLeft(BNode<E> element,int comparingValue){
  135.        
  136.         if(element == null)
  137.             return 0;      
  138.        
  139.         int valueElement = Integer.parseInt(element.info.toString());
  140.        
  141.         if(element.left == null && element.right == null){
  142.                
  143.                 if(valueElement < comparingValue)
  144.                     return valueElement;   
  145.         }
  146.        
  147.         if(element.left != null && element.right != null){
  148.             if(valueElement < comparingValue)
  149.                 return valueElement + getSumLeft(element.left, comparingValue) + getSumLeft(element.right, comparingValue);
  150.             else
  151.                 return getSumLeft(element.left, comparingValue) + getSumLeft(element.right, comparingValue);
  152.         }
  153.  
  154.         if(element.left == null && element.right != null){
  155.             if(valueElement < comparingValue)
  156.                 return valueElement + getSumLeft(element.right, comparingValue);
  157.             else
  158.                 return getSumLeft(element.right, comparingValue);
  159.         }
  160.        
  161.         if(element.left != null && element.right == null){
  162.             if(valueElement < comparingValue)
  163.                 return valueElement + getSumLeft(element.left, comparingValue);
  164.             else
  165.                 return getSumLeft(element.left, comparingValue);
  166.         }
  167.  
  168.         return 0;
  169.     }
  170.    
  171.     //public int getSumRight(BNode<E> element){
  172.        
  173.         //return 0;
  174.    // }
  175.    
  176.     public BNode<E> findElement(BNode<E> node, int value){
  177.        
  178.           if(node != null)
  179.           {
  180.               int nodeValue = Integer.parseInt(node.info.toString());
  181.              
  182.              
  183.               if(nodeValue == value)
  184.               {
  185.                    return node;
  186.                    
  187.                }
  188.               else
  189.               {
  190.                  
  191.                    
  192.                     BNode<E> foundNode = findElement(node.left,value);
  193.                    
  194.                    
  195.                     if(foundNode == null)
  196.                     {
  197.                         foundNode = findElement(node.right,value);
  198.                     }
  199.                                    
  200.                     return foundNode;                  
  201.                  }
  202.             }
  203.         else
  204.          return null;
  205.     }
  206.    
  207. }
  208.  
  209.  
  210. public class BinaryTreeSum {
  211.  
  212.     public static void main(String[] args) throws Exception {
  213.         int i, j, k;
  214.         int index;
  215.         String action;
  216.        
  217.         String line;
  218.  
  219.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  220.         StringTokenizer st;
  221.  
  222.         int N = Integer.parseInt(br.readLine());
  223.  
  224.         BNode<String> nodes[] = new BNode[N];
  225.         BTree<String> tree = new BTree<String>();
  226.        
  227.         for (i=0;i<N;i++)
  228.             nodes[i] = new BNode<String>();
  229.        
  230.         for (i = 0; i < N; i++) {
  231.             line = br.readLine();
  232.             st = new StringTokenizer(line);
  233.             index = Integer.parseInt(st.nextToken());
  234.             nodes[index].info = st.nextToken();
  235.             action = st.nextToken();
  236.             if (action.equals("LEFT")) {
  237.                 tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.LEFT, nodes[index]);
  238.             } else if (action.equals("RIGHT")) {
  239.                 tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.RIGHT, nodes[index]);    
  240.             } else {
  241.                 // this node is the root
  242.                 tree.makeRootNode(nodes[index]);
  243.             }
  244.         }
  245.  
  246.         int baranaVrednost = Integer.parseInt(br.readLine());
  247.        
  248.            
  249.         br.close();
  250.         tree.findElement(baranaVrednost);
  251.        
  252.     }
  253. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement