data_structure_assignment_2

package problem1.node;

import java.util.InputMismatchException;
import java.util.Scanner;

public class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private int data;

    //default constructor
    public TreeNode() {
        System.out.print("Enter integer value : ");
        try {
            data = new Scanner(System.in).nextInt();
        } catch (InputMismatchException e) {
            System.out.println("Invalid input");
            e.getMessage();
            System.exit(-1);
        }
        left = right = null;

    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
}



package problem1.mybst;


import problem1.node.TreeNode;
import problem4.myqueue.MyQueue;
import problem4.myqueue.Node;


// to implement BinarySearchTree
public class MyBinarySearchTree {


    private TreeNode newnode, root, tmp;
    private MyQueue queue;
    private int totalInsertion;


    public MyBinarySearchTree() {
        tmp = null;
        root = null;
        totalInsertion = 0;
        queue = new MyQueue();

    }

    //seeting root node
    public void setRoot() {
        newnode = new TreeNode();
        if (root == null) {
            root = newnode;
            tmp = root;
            newnode = null;
        }
    }

    public TreeNode getRoot() {
        return root;
    }


    public int getTotalInsertion() {
        return totalInsertion;
    }

    public void setTotalInsertion(int totalInsertion) {
        this.totalInsertion = totalInsertion;
    }

    public TreeNode getNewnode() {
        return newnode;
    }

    public void setNewnode(TreeNode newnode) {
        this.newnode = newnode;
    }

    public TreeNode getTmp() {
        return tmp;
    }

    public void setTmp(TreeNode tmp) {
        this.tmp = tmp;
    }


    public MyQueue getQueue() {
        return queue;
    }

    public void setQueue(MyQueue queue) {
        this.queue = queue;
    }

    //setting binary tree
    public void insert(TreeNode tmproot) {
        if (newnode == null) {
            newnode = new TreeNode();
            ++totalInsertion;
        }

        try {
            if (newnode.getData() <= tmproot.getData()) {
                System.out.println("left traversal...");
                if (tmproot.getLeft() == null) {
                    tmproot.setLeft(newnode);
                    System.out.println("node inserted left");
                    queue.enqueue(new Node(newnode));//only left insertion
                    newnode = null;
                    return;
                } else {
                    System.out.println("left not empty changing tmproot ");
                    insert(tmproot.getLeft());
                }
            }
        } catch (NullPointerException ignore) {
        }


        try {
            if (newnode.getData() > tmproot.getData()) {
                System.out.println("Right traversal...");
                if (tmproot.getRight() == null) {
                    tmproot.setRight(newnode);
                    System.out.println("Node inserted right");
                    newnode = null;
                } else {
                    System.out.println("Right not empty changing tmproot");
                    insert(tmproot.getRight());
                }
            }
        } catch (NullPointerException ignore) {
        }

    }

    //preorder
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }


        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    //postorder
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        postOrder(node.getLeft());
        postOrder(node.getRight());
    }

}



/*
Name : Nikhil Mohan
university id : 181500427
class id : 38
created on Intellij
Gla University
*/
package problem1.main;

import problem1.mybst.MyBinarySearchTree;

public class MyMain {
    public static void main(String[] args) {
        MyBinarySearchTree m = new MyBinarySearchTree();

        //setting root
        m.setRoot();
        System.out.println("root set : " + m.getRoot().getData());


        //insertion
        for (int i = 0; i < 5; i++) {
            m.insert(m.getRoot());
        }



        /*
        My binary search tree class in this package supports insertion of left children in to queue during
        the time of insertion.
        also if we subtract total number the number of queue elements from totla elements present we will get
         nodes not having left children.
         */

        //printing left children
        m.getQueue().queuePrint(m.getQueue());
        //Nodes not having left childrens
        System.out.println(m.getTotalInsertion() - m.getQueue().getSize(m.getQueue()));


    }

}

problem1 finished

problem 2 starts

package problem2.main;

import problem1.node.TreeNode;
import problem4.myqueue.MyQueue;
import problem4.myqueue.Node;


public class Methods {


    private MyQueue pre, post;

    //constructor
    public Methods() {

        pre = new MyQueue();
        post = new MyQueue();
    }

    public MyQueue getPre() {
        return pre;
    }

    public void setPre(MyQueue pre) {
        this.pre = pre;
    }

    public MyQueue getPost() {
        return post;
    }

    public void setPost(MyQueue post) {
        this.post = post;
    }


    public void verify_A(TreeNode root) {

        preOrder(root);
        System.out.println("First element of pre Order traversal : " + pre.getFront().getNode().getData());
        postOrder(root);
        System.out.println("Last Element of post order traversal : " + post.getEnd().getNode().getData());

    }


    //verification of statement "Both the traversal will give same element at the mid position for odd number of nodes."
    public boolean verify_B(TreeNode root) {

        pre.queuePrint(pre);
        post.queuePrint(post);

        int size = pre.getSize(pre);
        int ctr = 0;
        int predata = 0;
        int postdata = 0;

        if (size % 2 == 1) {
            //last element of this while loop is middle element of pre-order traversal queue
            while (ctr < size / 2 && pre.getTmp() != null) {
                pre.setTmp(pre.getTmp().getNext());
                ctr++;
            }
            ctr = 0;
            try {
                assert pre.getTmp() != null;
                predata = pre.getTmp().getNode().getData();
            } catch (NullPointerException ignore) {
            }
            while (ctr < size / 2 && post.getTmp() != null) {
                post.setTmp(post.getTmp().getNext());
                ctr++;
            }
            try {
                assert post.getTmp() != null;
                postdata = post.getTmp().getNode().getData();
            } catch (NullPointerException ignore) {
            }
            System.out.println(predata + "pre data");
            System.out.println(postdata + "post data");
            return predata == postdata;
        } else {
            System.out.println("Number of elements in tree are even");
            return false;
        }

    }

    //preorder
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        pre.enqueue(new Node(node));
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    //postorder
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        postOrder(node.getLeft());
        postOrder(node.getRight());
        post.enqueue(new Node(node));


    }
}

package problem2.main;

import problem1.mybst.MyBinarySearchTree;
import problem4.myqueue.MyQueue;

public class MyMain {
    public static void main(String[] args) {
        MyBinarySearchTree m = new MyBinarySearchTree();
        Methods mthds = new Methods();
        MyQueue pre = new MyQueue();
        MyQueue post = new MyQueue();
        int ctr = 0;
        //setting up the root
        m.setRoot();
        System.out.println("Root set Successfully value :" + m.getRoot().getData());

        //Setting up the bst
        for (int i = 0; i < 4; i++) {
            m.insert(m.getRoot());
        }
        mthds.setPre(pre);
        mthds.setPost(post);
        mthds.preOrder(m.getRoot());
        mthds.postOrder(m.getRoot());
        pre.queuePrint(pre);
        post.queuePrint(post);

        System.out.println("Verification of statement root element occours first in pre-order and last in post-order ");
        System.out.println(pre.getFront().getNode().getData() == post.getEnd().getNode().getData());


        //verification of statement "Both the traversal will give same  element at the mid position for odd number ofnodes."

        while (pre.getTmp() != null && ctr < pre.getSize(pre) / 2) {
            ++ctr;
            pre.setTmp(pre.getTmp().getNext());
        }
        assert pre.getTmp() != null;
        System.out.println(pre.getTmp().getNode().getData());
        ctr = 0;
        while (pre.getTmp() != null && ctr < pre.getSize(pre) / 2) {
            ++ctr;
            post.setTmp(post.getTmp().getNext());
        }
        System.out.println(post.getTmp().getNode().getData());


    }

}


problem2 finished

problem3 starts


package problem3.node;


import problem5.student.Student;

public class Node {


    private Student s;
    private Node next;


    public Node() {
        s = new Student();
        next = null;
    }

    public Student getS() {
        return s;
    }

    public void setS(Student s) {
        this.s = s;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }


}


package problem3.myqueue;


import problem3.node.Node;

public class MyPriorityQueue {

    private Node tmp, front, end;


    //inserting  new student into into queue  and priority is set by roll number
    public void enqueue(Node newNode) {

        if (front == null || newNode.getS().getRollno() < front.getS().getRollno()) {
            newNode.setNext(front);
            front = newNode;
        } else {
            tmp = front;

            while (tmp.getNext() != null && tmp.getNext().getS().getRollno() < newNode.getS().getRollno()) {
                tmp = tmp.getNext();
            }
            newNode.setNext(tmp.getNext());
            tmp.setNext(newNode);
        }
    }

    // printing queue
    public void dequeue() {
        if (front == null) {
            System.out.println("No entry found");
            return;
        }
        do {

            System.out.print(front.getS().getName() + ":");
            System.out.println(front.getS().getRollno());
            front = front.getNext();
        }
        while (front != null);
    }
}

package problem3.main;

import problem3.myqueue.MyPriorityQueue;
import problem3.node.Node;


// use problem5.student.Student class to create object of student
public class MyMain {
    public static void main(String[] args) {
        MyPriorityQueue m = new MyPriorityQueue();
        for (int i = 0; i < 4; i++) {
            Node newNode = new Node();
            m.enqueue(newNode);
        }
        m.dequeue();


    }
}


problem3 finished

problem4 starts

package problem4.myqueue;

import problem1.node.TreeNode;

public class Node {
    private TreeNode node;
    private Node next;

    public Node() {
        node = new TreeNode();
        next = null;
    }

    public Node(TreeNode treenode) {
        node = treenode;
        next = null;
    }

    public TreeNode getNode() {
        return node;
    }

    public void setNode(TreeNode node) {
        this.node = node;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}



package problem4.myqueue;
// to create queue to store pre - order successor


public class MyQueue {

    private Node front, end, tmp;
    private int size;


    public MyQueue() {
        front = null;
        end = null;
        tmp = null;
        size = 0;
    }


    public int getSize(MyQueue queue) {
        size = 0;
        while (queue.front != null) {
            ++size;
            queue.setFront(queue.front.getNext());
        }
        queue.setFront(queue.getTmp());
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }


    public Node getFront() {
        return front;
    }

    public void setFront(Node front) {
        this.front = front;
    }

    public Node getEnd() {
        return end;
    }

    public void setEnd(Node end) {
        this.end = end;
    }

    public Node getTmp() {
        return tmp;
    }

    public void setTmp(Node tmp) {
        this.tmp = tmp;
    }

    public void queuePrint(MyQueue queue) {
        while (queue.tmp != null) {

            System.out.print(queue.tmp.getNode().getData() + ",");
            queue.tmp = queue.tmp.getNext();
        }
        System.out.println("\b");
        queue.tmp = queue.front;
    }


    public void enqueue(Node node) {

        if (front == null) {
            tmp = front = end = node;
        } else {
            while (tmp.getNext() != null) {
                tmp = tmp.getNext();
            }
            end = node;
            tmp.setNext(node);
            tmp = front;
        }
    }

    public int getSuccessor(int data) {

        tmp = front;
        try {
            while (tmp.getNode().getData() != data && tmp != null) {
                tmp = tmp.getNext();
            }

            assert tmp != null;
            return tmp.getNext().getNode().getData();
        } catch (NullPointerException ignore) {
            System.out.println("No preorder Successor found");
            return -1;
        }

    }

}



package problem4.main;

import problem1.mybst.MyBinarySearchTree;
import problem2.main.Methods;
import problem4.myqueue.MyQueue;

import java.util.Scanner;

public class MyMain {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        MyBinarySearchTree m = new MyBinarySearchTree();
        Methods mthds = new Methods();
        MyQueue q = new MyQueue();
        mthds.setPre(q);

        //setting up the root
        m.setRoot();

        //inserting into the tree
        for (int i = 0; i < 5; i++) {
            m.insert(m.getRoot());
        }

        //method to print preorder Successor of given Node
        /*
        preorder method in
         */
        mthds.preOrder(m.getRoot());
        q.queuePrint(q);
        System.out.print("Enter value of which you want to find preorder Successor : ");
        System.out.println(q.getSuccessor(sc.nextInt()));

    }
}

problem5 starts

/*
 *  Created by IntelliJ IDEA.
 *  User: Vaibhav
 *  Date: 23-Mar-20
 *  Time: 7:06 PM
 */
package problem5.node;

import problem5.student.Student;

// to define node properties
public class Node {
    private Student s;
    private Node next;


    public Node(Student s) {
        this.s = s;
        next = null;
    }

    public Student getS() {
        return s;
    }

    public void setS(Student s) {
        this.s = s;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}


package problem5.student;

import java.util.Scanner;

public class Student {
    private String name;
    private int rollno, backlog, apperingcount;
    private Scanner sc;


    public Student() {
        sc = new Scanner(System.in);
        System.out.print("Name :");
        this.name = sc.next();
        System.out.print("Roll.no : ");
        this.rollno = sc.nextInt();
        System.out.print("Backlog_count : ");
        this.backlog = sc.nextInt();
        System.out.print("appering_count");
        this.apperingcount = sc.nextInt();


    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getRollno() {
        return rollno;
    }

    public void setRollno(int rollno) {
        this.rollno = rollno;
    }

    @Override
    public String toString() {
        return "name='" + name + '\'' +
                ", rollno=" + rollno +
                ", backlog=" + backlog +
                ", apperingcount=" + apperingcount
                ;
    }

    public int getBacklog() {
        return backlog;
    }

    public void setBacklog(int backlog) {
        this.backlog = backlog;
    }

    public int getApperingcount() {
        return apperingcount;
    }

    public void setApperingcount(int apperingcount) {
        this.apperingcount = apperingcount;
    }

}

/*
 *  Created by IntelliJ IDEA.
 *  User: Vaibhav
 *  Date: 23-Mar-20
 *  Time: 7:06 PM
 */
package problem5.main;

import problem5.circularqueue.MyCircularQueue;
import problem5.node.Node;
import problem5.student.Student;

import java.util.Scanner;

//executable class
public class MyMain {
    public static void main(String[] args) {
        MyCircularQueue m = new MyCircularQueue();
        Node node;

        for (int i = 0; i < 5; i++) {
            node = new Node(new Student());
            m.enqueue(node);
        }
        m.printQueue();

        m.remove(new Scanner(System.in).next());
        m.printQueue();

        m.process(new Scanner(System.in).next());


    }
}


/*
 *  Created by IntelliJ IDEA.
 *  User: Vaibhav
 *  Date: 23-Mar-20
 *  Time: 7:06 PM
 */
package problem5.circularqueue;

import problem5.node.Node;


public class MyCircularQueue {
    private Node front, tmp, end;

    public MyCircularQueue() {
        front = null;
        tmp = null;
        end = null;
    }


    public Node getFront() {
        return front;
    }

    public void setFront(Node front) {
        this.front = front;
    }

    public Node getTmp() {
        return tmp;
    }

    public void setTmp(Node tmp) {
        this.tmp = tmp;
    }

    public void enqueue(Node newNode) {
        if (front == null) {
            tmp = front = newNode;
            return;
        }
        if (tmp.getNext() == null) {
            tmp.setNext(newNode);
            newNode.setNext(tmp);
            end = newNode;
            return;
        }
        newNode.setNext(tmp.getNext());
        tmp.setNext(newNode);

    }

    public void printQueue() {
        tmp = front;
        try {
            do {
                System.out.println(tmp.getS().toString());
                tmp = tmp.getNext();
            }
            while (tmp != front && tmp != null);
        } catch (NullPointerException ignored) {
        }
    }


    public void remove(String name) {
        tmp = front;
        if (tmp.getS().getName().equals(name) && tmp.getS().getBacklog() == 0) {
            tmp = front = front.getNext();
        }
        while (!tmp.getNext().getS().getName().equals(name)) {
            tmp = tmp.getNext();
            if (tmp == front)
                return;
        }
        if (tmp.getS().getBacklog() == 0) {
            tmp.setNext(tmp.getNext().getNext());
            return;
        }
        System.out.println("Student backlog is not 0 or student entry not found");
    }

    public void process(String name) {
        tmp = front;
        if (tmp.getS().getName().equals(name)) {
            System.out.println(tmp.getS().toString());
            System.out.println(tmp.getS().getBacklog() - tmp.getS().getApperingcount());
        }
        while (!tmp.getS().getName().equals(name)) {
            tmp = tmp.getNext();
            if (tmp == front)
                return;
        }
        System.out.println(tmp.getS().toString());
        System.out.println(tmp.getS().getBacklog() - tmp.getS().getApperingcount());
    }
}

problem5 finished