Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.StringTokenizer;
- class BNodeN<E> {
- public E info;
- public BNodeN<E> left;
- public BNodeN<E> right;
- char ltag;
- char rtag;
- static int LEFT = 1;
- static int RIGHT = 2;
- public BNodeN(E info) {
- this.info = info;
- left = null;
- right = null;
- ltag = '-';
- rtag = '-';
- }
- }
- class BTree<E> {
- public BNodeN<E> head;
- public BTree() {
- head = new BNodeN<E>(null);
- // po definicija ako nema koren, t.e. ako stebloto e prazno
- head.left = head;
- head.ltag = '-';
- // kaj vodacot sekogas desnata vrska pokazuva kon samiot sebe
- head.right = head;
- head.rtag = '+';
- }
- public BNodeN<E> makeRoot(E elem) {
- BNodeN<E> tmp = new BNodeN<E>(elem);
- head.left = tmp;
- head.ltag = '+';
- tmp.left = head;
- tmp.ltag = '-';
- tmp.right = head;
- tmp.rtag = '-';
- return tmp;
- }
- public BNodeN<E> makeRootNode(BNodeN<E> tmp) {
- head.left = tmp;
- head.ltag = '+';
- tmp.left = head;
- tmp.ltag = '-';
- tmp.right = head;
- tmp.rtag = '-';
- return tmp;
- }
- public BNodeN<E> addChild(BNodeN<E> node, int where, E elem) {
- BNodeN<E> tmp = new BNodeN<E>(elem);
- if (where == BNodeN.LEFT) {
- if (node.ltag == '+') // veke postoi element
- return null;
- tmp.left = node.left;
- tmp.ltag = '-';
- tmp.right = node;
- tmp.rtag = '-';
- node.left = tmp;
- node.ltag = '+';
- } else {
- if (node.rtag == '+') // veke postoi element
- return null;
- tmp.right = node.right;
- tmp.rtag = '-';
- tmp.left = node;
- tmp.ltag = '-';
- node.right = tmp;
- node.rtag = '+';
- }
- return tmp;
- }
- public BNodeN<E> addChildNode(BNodeN<E> node, int where, BNodeN<E> tmp) {
- if (where == BNodeN.LEFT) {
- if (node.ltag == '+') // veke postoi element
- return null;
- tmp.left = node.left;
- tmp.ltag = '-';
- tmp.right = node;
- tmp.rtag = '-';
- node.left = tmp;
- node.ltag = '+';
- } else {
- if (node.rtag == '+') // veke postoi element
- return null;
- tmp.right = node.right;
- tmp.rtag = '-';
- tmp.left = node;
- tmp.ltag = '-';
- node.right = tmp;
- node.rtag = '+';
- }
- return tmp;
- }
- public BNodeN<E> insertRight(BNodeN<E> parent, E info) {
- BNodeN<E> child = new BNodeN<E>(info);
- child.ltag = '-';
- child.left = parent;
- child.rtag = parent.rtag;
- child.right = parent.right;
- parent.right = child;
- parent.rtag = '+';
- if (child.rtag == '+') {
- BNodeN<E> temp = child.right;
- while (temp.ltag == '+')
- temp = temp.left;
- temp.left = child;
- }
- return child;
- }
- public BNodeN<E> predecessorInorder(BNodeN<E> node) {
- if (node.ltag == '-')
- return node.left;
- BNodeN<E> p = node.left;
- while (p.rtag == '+')
- p = p.right;
- return p;
- }
- public BNodeN<E> successorInorder(BNodeN<E> node) {
- if (node.rtag == '-')
- return node.right;
- BNodeN<E> p = node.right;
- while (p.ltag == '+')
- p = p.left;
- return p;
- }
- }
- public class ConsecutiveNumbers {
- public static void main(String[] args) throws Exception {
- int i,j,k;
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st;
- int N = Integer.parseInt(br.readLine());
- BNodeN<Integer> nodes[] = new BNodeN[N];
- BTree<Integer> tree = new BTree<Integer>();
- for (i=0;i<N;i++)
- nodes[i] = null;
- for (i = 0; i < N; i++) {
- String line = br.readLine();
- st = new StringTokenizer(line);
- int index = Integer.parseInt(st.nextToken());
- nodes[index] = new BNodeN<Integer>(Integer.parseInt(st.nextToken()));
- String action = st.nextToken();
- if (action.equals("LEFT")) {
- tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNodeN.LEFT, nodes[index]);
- } else if (action.equals("RIGHT")) {
- tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNodeN.RIGHT, nodes[index]);
- } else {
- // this node is the root
- tree.makeRootNode(nodes[index]);
- }
- }
- br.close();
- boolean f = false;
- if (tree.head.ltag== '-')
- return;
- BNodeN<Integer> p = tree.head.left;
- while (p.ltag== '+')
- p = p.left;
- while (p != tree.head) {
- int t = p.info;
- p = tree.successorInorder(p);
- if(p!=tree.head)
- if(t+1!=p.info){
- f = true;
- break;
- }
- }
- if(f){
- f = false;
- System.out.println(false);
- }
- else
- System.out.println(true);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment