+1 (315) 557-6473 

Program To Implement Binary Trees Using Java Programming Language Assignment Solutions.


Instructions

Objective
Write a Java assignment program to implement binary trees in the Java programming language. Binary trees are hierarchical data structures that consist of nodes, where each node has at most two child nodes, referred to as the left child and the right child. They are widely used in various computer science applications such as searching, sorting, and hierarchical data representation.

Requirements and Specifications

Program to implement binary trees in Java programming language

Source Code

TREE

public class PMTree {

    private class Node {

        Node parent;

        Node left, right;

        int days;

        Node (Node parent, int days) {

            this.parent = parent;

            this.days = days;

            this.left = this.right = null;

        }

        /*

         * When deleting, we want to know how many children a node has.

         */

        int numChildren () {

            return (left == null ? 0 : 1) + (right == null ? 0 : 1);

        }

    }

    private Node root = null;

    public boolean contains (int days) {

        return getNode (days) != null;

    }

    private Node getNode (int days) {

        Node cur = root;

        while (cur != null) {

            if (days == cur.days)

                return cur;

            else if (days < cur.days)

                cur = cur.left;

            else

                cur = cur.right;

        }

        return null;

    }

    public void insert (int days) {

        Node cur = root;

        if (root == null) {

            root = new Node (null, days);

            return;

        }

        while (true) {

            if (days == cur.days)

                return;

            else if (days < cur.days) {

                if (cur.left == null) {

                    cur.left = new Node (cur, days);

                    return;

                } else

                    cur = cur.left;

            } else {

                if (cur.right == null) {

                    cur.right = new Node (cur, days);

                    return;

                } else

                    cur = cur.right;

            }

        }

    }

    /*

     * Delete a node from the tree. If the node has one child or none,

     * delete it as if it, its parent (if it exists) and its child (if

     * it has one) are a doubly linked list. Otherwise, replace the value

     * in the node to be deleted with the minimum element of its right

     * subtree and delete the node that originally contained that element.

     * Note that, by construction, that node has at most one child (it has

     * no left child because a left child would contain a smaller value).

     */

    public void delete (int days) {

        Node node = getNode (days);

        if (node == null)

            return;

        if (node.numChildren() < 2) {

            simpleDelete (node);

        } else {

            Node min = getMinNode(node.right);

            simpleDelete (min);

            node.days = min.days;

        }

    }

    /*

     * Delete a node that has one child or none. We treat this node,

     * its parent (if it exists) and its child (if it has one) as a doubly

     * linked list and delete accordingly. The code is fiddly because of

     * the special cases. We might be deleting the root (parent == null)

     * and/or we might be deleting a node with no child, with just a left

     * child or just a right child.

     */

    private void simpleDelete (Node node) {

        Node child = node.left != null ? node.left : node.right;

        if (node == root) {

            root = child;

            if (root != null)

                root.parent = null;

        } else {

            if (node == node.parent.left)

                node.parent.left = child;

            else

                node.parent.right = child;

            if (child != null)

                child.parent = node.parent;

        }

    }

    /*

     * Return the node containing the smallest value in the subtree

     * rooted at the given node. This is found by following the left

     * child reference until we get to a node that has no left child.

     */

    private Node getMinNode (Node node) {

        while (node.left != null)

            node = node.left;

        return node;

    }

}

LIST

import java.util.*;

public class PMList {

    public static class Entry {

        public final int days;

        public final String name;

        private Entry (int days, String name) {

            this.days = days;

            this.name = name;

        }

    }

    public static List getPrimeMinisters () {

        ArrayList list = new ArrayList<>();

        list.add(new Entry(365*20 + 314, "Sir Robert Walpole"));

        list.add(new Entry(365* 1 + 119, "The Earl of Wilmington"));

        list.add(new Entry(365*10 + 191, "Henry Pelham"));

        list.add(new Entry(365* 7 + 205, "The Duke of Newcastle"));

        list.add(new Entry(365* 0 + 225, "The Duke of Devonshire"));

        list.add(new Entry(365* 0 + 317, "The Earl of Bute"));

        list.add(new Entry(365* 2 + 85, "George Grenville"));

        list.add(new Entry(365* 1 + 113, "The Marquess of Rockingham"));

        list.add(new Entry(365* 2 + 76, "The Earl of Chatham"));

        list.add(new Entry(365* 1 + 106, "The Duke of Grafton"));

        list.add(new Entry(365*12 + 58, "Lord North"));

        list.add(new Entry(365* 0 + 266, "The Earl of Shelburne"));

        list.add(new Entry(365*18 + 343, "William Pitt the Younger"));

        list.add(new Entry(365* 3 + 82, "The Duke of Portland"));

        list.add(new Entry(365* 3 + 54, "Henry Addington"));

        list.add(new Entry(365* 1 + 42, "The Lord Grenville"));

        list.add(new Entry(365* 2 + 221, "Spencer Perceval"));

        list.add(new Entry(365*14 + 305, "The Earl of Liverpool"));

        list.add(new Entry(365* 0 + 144, "The Viscount Goderich"));

        list.add(new Entry(365* 0 + 119, "George Canning"));

        list.add(new Entry(365* 2 + 320, "The Duke of Wellington"));

        list.add(new Entry(365* 3 + 229, "The Earl Grey"));

        list.add(new Entry(365* 6 + 255, "The Viscount Melbourne"));

        list.add(new Entry(365* 5 + 57, "Sir Robert Peel"));

        list.add(new Entry(365* 6 + 110, "Lord John Russell"));

        list.add(new Entry(365* 3 + 280, "The Earl of Derby"));

        list.add(new Entry(365* 2 + 42, "The Earl of Aberdeen"));

        list.add(new Entry(365* 9 + 141, "The Viscount Palmerston"));

        list.add(new Entry(365*12 + 126, "William Ewart Gladstone"));

        list.add(new Entry(365* 6 + 339, "Benjamin Disraeli"));

        list.add(new Entry(365*13 + 252, "The Marquess of Salisbury"));

        list.add(new Entry(365* 1 + 109, "The Earl of Rosebery"));

        list.add(new Entry(365* 3 + 145, "Arthur Balfour"));

        list.add(new Entry(365* 2 + 122, "Sir Henry Campbell-Bannerman"));

        list.add(new Entry(365* 8 + 244, "H. H. Asquith"));

        list.add(new Entry(365* 5 + 317, "David Lloyd George"));

        list.add(new Entry(365* 0 + 211, "Bonar Law"));

        list.add(new Entry(365* 7 + 82, "Stanley Baldwin"));

        list.add(new Entry(365* 6 + 289, "Ramsay MacDonald"));

        list.add(new Entry(365* 2 + 348, "Neville Chamberlain"));

        list.add(new Entry(365* 8 + 239, "Sir Winston Churchill"));

        list.add(new Entry(365* 6 + 92, "Clement Attlee"));

        list.add(new Entry(365* 1 + 279, "Sir Anthony Eden"));

        list.add(new Entry(365* 6 + 281, "Harold Macmillan"));

        list.add(new Entry(365* 0 + 363, "Sir Alec Douglas-Home"));

        list.add(new Entry(365* 7 + 279, "Harold Wilson"));

        list.add(new Entry(365* 3 + 259, "Edward Heath"));

        list.add(new Entry(365* 3 + 29, "James Callaghan"));

        list.add(new Entry(365*11 + 208, "Margaret Thatcher"));

        list.add(new Entry(365* 6 + 155, "John Major"));

        list.add(new Entry(365*10 + 56, "Tony Blair"));

        list.add(new Entry(365* 2 + 318, "Gordon Brown"));

        list.add(new Entry(365* 6 + 63, "David Cameron"));

        list.add(new Entry(365* 3 + 11, "Theresa May"));

        list.add(new Entry(365* 3 + 44, "Boris Johnson"));

        list.add(new Entry(365* 0 + 49, "Liz Truss"));

        list.add(new Entry(365* 0 + 1, "Rishi Sunak"));

        return list;

    }

    public static final int[] INCOMPLETE = {

            365* 1 + 119,

            365*10 + 191,

            365* 1 + 113,

            365* 2 + 76,

            365*18 + 343,

            365* 3 + 82,

            365* 2 + 221,

            365*14 + 305,

            365* 0 + 119,

            365* 3 + 280,

            365* 9 + 141,

            365*13 + 252,

            365* 2 + 122,

            365* 0 + 211,

            365* 6 + 289,

            365* 8 + 239,

            365* 1 + 279,

            365* 0 + 1

    };

}