Question

Need in JAVA.

You are to use Binary Trees to do this Program.

Write a complete program, which will process several sets of numbers:

For each set of numbers you should:

1. Create a binary tree.

2. Print the tree using “inorder”, “preorder”, and “postorder”.

3. Call a method Count which counts the number of nodes in the tree.

4. Call a method Children which prints the number of children each node has.

5. Inset and delete several nodes according to the instructions given.

6. Print the tree again using “inorder”, “preorder”, and “postorder”.

7. Call a method Count again which counts the number of nodes in the tree.

8. Call a method again Children which prints the number of children each node has.

Data to be used Use value to determine the end of data (example -999)

1. Set #1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -999

Insert 21, Delete 16, Insert 30, Delete 10, Delete 12, Delete 2

2. Set #2: 3 1 5 -999

Insert 3, Insert 14, Insert 33, Insert 2, Insert 6

3. Set #3: 11 25 75 12 37 60 90 8 15 32 45 50 67 97 95 -999

Insert 21, Delete 60, Insert 30, Delete 45, Delete 97, Delete 25

4. Set #4: 150 40 60 39 34 27 10 82 15 -999

Insert 21, Delete 139, Insert 34, Delete 27, Insert 12, Delete 82

5. Set #5: 2 -999

Delete 2

6. Set #6: 34 65 3 7 48 15 16 92 56 43 74 -999

Insert 21, Delete 34, Insert 30, Insert 10, Insert12, Insert 2

Answer 1

Please find the code below,

Node.java

public class Node {
    public int value;
    public int childrenCount;
    public Node left;
    public Node right;
    public Node parent;

    Node(int value) {
        this.value = value;
        this.childrenCount = 0;
        left = right = parent = null;
    }
}

BinaryTree.java

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    private Node root;
    private int numberOfNodes;

    public BinaryTree() {
        root = null;
        numberOfNodes = 0;
    }

    public int count(){
        return numberOfNodes;
    }

    public void insert(int value) {
        numberOfNodes++;
        if (root == null) {
            root = new Node(value);
            root.parent = null;
            return;
        }
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        // Do level order traversal until we find
        // an empty place.
        while (!q.isEmpty()) {
            Node temp = q.poll();
            temp.childrenCount++;
            if (temp.left == null) {
                temp.left = new Node(value);
                temp.left.parent = temp;
                break;
            } else q.add(temp.left);

            if (temp.right == null) {
                temp.right = new Node(value);
                temp.right.parent = temp;
                break;
            } else q.add(temp.right);
        }
    }

    public String inorder(Node node) {
        if (node == null) return "";
        String left = inorder(node.left);
        String right = inorder(node.right);
        return left + " " + node.value + " " + right;
    }

    public String preorder(Node node) {
        if (node == null) return "";
        String left = inorder(node.left);
        String right = inorder(node.right);
        return node.value + " " + left + " " + right;
    }

    public String postorder(Node node) {
        if (node == null) return "";
        String left = inorder(node.left);
        String right = inorder(node.right);
        return left + " " + right + " " + node.value;
    }

    public String children() {
        if (root == null) return "-1";
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Node temp = q.poll();
            sb.append("Node ").append(temp.value).append(" has ").append(temp.childrenCount).append(" children.\n");
            if (temp.left != null) q.add(temp.left);
            if (temp.right != null) q.add(temp.right);
        }
        return sb.toString();
    }

    public void updateChildrenCount(Node parentNode){
        while(parentNode != null){
            parentNode.childrenCount--;
            parentNode = parentNode.parent;
        }
    }

    public void delete(int value) {
        if (root == null) return;

        if (root.left == null && root.right == null && root.value == value) {
            root = null;
            return;
        }

        Queue<Node> q = new LinkedList<>();
        q.add(root);
        Node temp;
        while (!q.isEmpty()) {
            temp = q.poll();
            if (temp.value == value){
                numberOfNodes--;
                if(temp.left == null && temp.right == null){
                    Node parentNode = temp.parent;
                    if(parentNode.left == temp) parentNode.left = null;
                    else if(parentNode.right == temp) parentNode.right = null;
                    updateChildrenCount(parentNode);
                }
                else if(temp.left != null){
                    Node leftNode = temp.left;
                    Node traversingNode = temp;
                    while(traversingNode.left != null) {
                        leftNode = traversingNode.left;
                        traversingNode = traversingNode.left;
                    }
                    temp.value = leftNode.value;
                    Node parentNode = leftNode.parent;
                    if(parentNode.left == leftNode) parentNode.left = null;
                    else if(parentNode.right == leftNode) parentNode.right = null;
                    updateChildrenCount(parentNode);
                }
                else {
                    Node rightNode = temp.right;
                    Node traversingNode = temp;
                    while(traversingNode.right != null) {
                        rightNode = traversingNode.right;
                        traversingNode = traversingNode.right;
                    }
                    temp.value = rightNode.value;
                    Node parentNode = rightNode.parent;
                    if(parentNode.left == rightNode) parentNode.left = null;
                    else if(parentNode.right == rightNode) parentNode.right = null;
                    updateChildrenCount(parentNode);
                }
                return;
            }
            if (temp.left != null) q.add(temp.left);
            if (temp.right != null) q.add(temp.right);
        }
    }

    public void levelorder(){
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        Node temp;
        while (!q.isEmpty()) {
            int level = q.size();
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<level; i++){
                temp = q.poll();
                sb.append(temp.value).append(", ");
                if(temp.left != null) q.add(temp.left);
                if(temp.right != null) q.add(temp.right);
            }
            System.out.println(sb.toString());
        }
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        // Set 1
        String set1 = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -999";
        String[] data1 = set1.split(" ");
        for(String data : data1){
            int value = Integer.parseInt(data);
            if(value == -999) continue;
            binaryTree.insert(value);
        }
        runSteps(binaryTree.root, binaryTree);
    }

    public static void runSteps(Node root, BinaryTree binaryTree){
        printTree(root, binaryTree);

        // Insert 21, Delete 16, Insert 30, Delete 10, Delete 12, Delete 2
        binaryTree.insert(21);
        binaryTree.delete(16);
        binaryTree.insert(30);
        binaryTree.delete(10);
        binaryTree.delete(12);
        binaryTree.delete(2);

        System.out.println("After Performing Operations");

        printTree(root, binaryTree);
    }

    public static void printTree(Node root, BinaryTree binaryTree){
        String inorder = binaryTree.inorder(root);
        String preorder = binaryTree.preorder(root);
        String postorder = binaryTree.postorder(root);
        System.out.println("In order : "+inorder+"\nPre order : "+preorder+"\nPost order : "+postorder);
        System.out.println("Number of nodes in the tree : "+binaryTree.count());
        System.out.println("Number of children each node has: \n"+binaryTree.children());
    }
}

OUTPUT :

If you have any doubts ask in the comments, also please don't forget to upvote the solution.