Последователни броеви lab8.1

Последователни броеви Problem 1 (0 / 0)

Со помош на нанижано бинарно дрво потребно е да проверите дали при inorder изминување на дрвото важи дека секој следен елемент има вредност за 1 поголема од претходниот (треба да се испечати true или false). Притоа доколку ви е потребно можете да користите дополнителни функции, но не смеете да користите рекурзија и дополнителни структури.

Име на класата во Java: ConsecutiveNumbers


import java.util.Scanner;

public class ConsecutiveNumbers {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        BTree<Integer> btree = new BTree();
        int n = scan.nextInt();
        BNode<Integer> nodes[] = new BNode[n];

        for (int i=0; i<n; ++i) {
            int index = scan.nextInt();
            int value = scan.nextInt();
            String where = scan.next();
            if (where.equals("ROOT")){
                nodes[index] = btree.makeRoot(value);
                scan.nextLine();
            }
            else {
                int whereTo = 1;
                if (where.equals("RIGHT"))
                    whereTo = 2;
                int whichNode = scan.nextInt();
                scan.nextLine();
                nodes[index] = btree.addChild(nodes[whichNode], whereTo, value);
            }
        }

        System.out.println(check(btree));
    }

    public static boolean check(BTree<Integer> tree) {


        BNode<Integer> now = tree.head.left;

        while (now.ltag == '+')
            now = now.left;

        BNode<Integer> succ = tree.successorInorder(now);

        while (succ != tree.head) {

            if ((succ.info - now.info) != 1)
                return false;

            now = succ;
            succ = tree.successorInorder(now);
        }
        return true;
    }
}

class BNode<E> {

    public E info;
    public BNode<E> left;
    public BNode<E> right;
    char ltag;
    char rtag;

    static int LEFT = 1;
    static int RIGHT = 2;

    public BNode(E info) {
        this.info = info;
        left = null;
        right = null;
        ltag = '-';
        rtag = '-';
    }

}

class BTree<E> {

    public BNode<E> head;

    public BTree() {
        head = new BNode<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 BNode<E> makeRoot(E elem) {
        BNode<E> tmp = new BNode<E>(elem);
        head.left = tmp;
        head.ltag = '+';

        tmp.left = head;
        tmp.ltag = '-';
        tmp.right = head;
        tmp.rtag = '-';

        return tmp;
    }

    public BNode<E> addChild(BNode<E> node, int where, E elem) {
        BNode<E> tmp = new BNode<E>(elem);

        if (where == BNode.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 BNode<E> successorInorder (BNode<E> node) {

        if (node.rtag == '-')
            return node.right;

        BNode<E> temp = node.right;
        while (temp.ltag != '-')
            temp = temp.left;
        return temp;
    }

}


Sample input

8
0 48 ROOT
1 46 LEFT 0
2 45 LEFT 1
3 47 RIGHT 1
4 50 RIGHT 0
5 51 RIGHT 4
6 50 LEFT 5
7 52 RIGHT 5

Sample output

false