Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.ArrayDeque;
- import java.util.Deque;
- import java.util.StringTokenizer;
- import java.util.NoSuchElementException;
- class BNode<E> {
- public E info;
- public BNode<E> left;
- public BNode<E> right;
- static int LEFT = 1;
- static int RIGHT = 2;
- public BNode(E info) {
- this.info = info;
- left = null;
- right = null;
- }
- public BNode() {
- this.info = null;
- left = null;
- right = null;
- }
- public BNode(E info, BNode<E> left, BNode<E> right) {
- this.info = info;
- this.left = left;
- this.right = right;
- }
- }
- class BTree<E> {
- public BNode<E> root;
- public BTree() {
- root = null;
- }
- public BTree(E info) {
- root = new BNode<E>(info);
- }
- public void makeRoot(E elem) {
- root = new BNode(elem);
- }
- public void makeRootNode(BNode<E> node) {
- root = node;
- }
- public BNode<E> addChild(BNode<E> node, int where, E elem) {
- BNode<E> tmp = new BNode<E>(elem);
- if (where == BNode.LEFT) {
- if (node.left != null) // veke postoi element
- return null;
- node.left = tmp;
- } else {
- if (node.right != null) // veke postoi element
- return null;
- node.right = tmp;
- }
- return tmp;
- }
- public BNode<E> addChildNode(BNode<E> node, int where, BNode<E> tmp) {
- if (where == BNode.LEFT) {
- if (node.left != null) // veke postoi element
- return null;
- node.left = tmp;
- } else {
- if (node.right != null) // veke postoi element
- return null;
- node.right = tmp;
- }
- return tmp;
- }
- public void findElement(int vrednost){
- BNode<E> element = findElement(this.root, vrednost);
- System.out.println(getSumLeft(element.left, vrednost)+" "+getSumRight(element.right,vrednost));
- }
- public int getSumRight(BNode<E> element, int comparingValue){
- if(element == null)
- return 0;
- int valueElement = Integer.parseInt(element.info.toString());
- if(element.left == null&&element.right == null){
- if(valueElement > comparingValue)
- return valueElement;
- }
- if(element.left != null&&element.right != null){
- if(valueElement > comparingValue)
- return valueElement + getSumRight(element.left, comparingValue) + getSumRight(element.right, comparingValue);
- else
- return getSumRight(element.left, comparingValue) + getSumRight(element.right, comparingValue);
- }
- if(element.left == null&&element.right != null){
- if(valueElement > comparingValue)
- return valueElement + getSumRight(element.right, comparingValue);
- else
- return getSumRight(element.right, comparingValue);
- }
- if(element.left != null && element.right == null){
- if(valueElement > comparingValue)
- return valueElement + getSumRight(element.left, comparingValue);
- else
- return getSumRight(element.left, comparingValue);
- }
- return 0;
- }
- public int getSumLeft(BNode<E> element,int comparingValue){
- if(element == null)
- return 0;
- int valueElement = Integer.parseInt(element.info.toString());
- if(element.left == null && element.right == null){
- if(valueElement < comparingValue)
- return valueElement;
- }
- if(element.left != null && element.right != null){
- if(valueElement < comparingValue)
- return valueElement + getSumLeft(element.left, comparingValue) + getSumLeft(element.right, comparingValue);
- else
- return getSumLeft(element.left, comparingValue) + getSumLeft(element.right, comparingValue);
- }
- if(element.left == null && element.right != null){
- if(valueElement < comparingValue)
- return valueElement + getSumLeft(element.right, comparingValue);
- else
- return getSumLeft(element.right, comparingValue);
- }
- if(element.left != null && element.right == null){
- if(valueElement < comparingValue)
- return valueElement + getSumLeft(element.left, comparingValue);
- else
- return getSumLeft(element.left, comparingValue);
- }
- return 0;
- }
- //public int getSumRight(BNode<E> element){
- //return 0;
- // }
- public BNode<E> findElement(BNode<E> node, int value){
- if(node != null)
- {
- int nodeValue = Integer.parseInt(node.info.toString());
- if(nodeValue == value)
- {
- return node;
- }
- else
- {
- BNode<E> foundNode = findElement(node.left,value);
- if(foundNode == null)
- {
- foundNode = findElement(node.right,value);
- }
- return foundNode;
- }
- }
- else
- return null;
- }
- }
- public class BinaryTreeSum {
- public static void main(String[] args) throws Exception {
- int i, j, k;
- int index;
- String action;
- String line;
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st;
- int N = Integer.parseInt(br.readLine());
- BNode<String> nodes[] = new BNode[N];
- BTree<String> tree = new BTree<String>();
- for (i=0;i<N;i++)
- nodes[i] = new BNode<String>();
- for (i = 0; i < N; i++) {
- line = br.readLine();
- st = new StringTokenizer(line);
- index = Integer.parseInt(st.nextToken());
- nodes[index].info = st.nextToken();
- action = st.nextToken();
- if (action.equals("LEFT")) {
- tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.LEFT, nodes[index]);
- } else if (action.equals("RIGHT")) {
- tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.RIGHT, nodes[index]);
- } else {
- // this node is the root
- tree.makeRootNode(nodes[index]);
- }
- }
- int baranaVrednost = Integer.parseInt(br.readLine());
- br.close();
- tree.findElement(baranaVrednost);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement