Question

Programming Project #5 – Binary Tree

Exercise 19 on page 637 of the text a through f

Here is the array to build the initial binary tree:
int [] data = { 50, 30, 60, 10, 80, 55, 40 };

BUT, make sure the code works with any binary tree created from an array named data

In addition to the main .java file, make sure you also create a Node.java and a Tree.java file that contain the code that allows you to build a linked list style binary tree.

Here are some test cases, be sure the above array is the default tree when you turn it in.
int [] data = { 80, 70, 60, 50, 90, 40, 30, 20, 10 };
int [] data = { 50, 30, 60, 10, 80, 55, 40, 85, 75, 65, 55, 95, 45, 35, 25, 15 };

Please have 3 .java files. (Main.java, Node.java, Tree.java). All separated.

Thank you! :)

Picture of page 637 for Exercise 19 is attached below:

19 Given the recursive nature of a binary tree, a good strategy for writing a Java method that operates on a binary tree is often first to write a recursive definition of the task. Given such a recursive definition, a Java implementation is often straight forward. Write recursive definitions that perform the following tasks on arbitrary binary trees. Implement the definitions in Java. Must your methods be members of Bina- rytree? For simplicity, assume that each data item in the tree is an integer object and that there are no duplicates Count the number of nodes in the tree. (Hint: If the tree is empty, the count is 0. If the tree is not empty, the count is 1 plus the number of nodes in the poor lett subtree plus the number of nodes in the root's right subtrec.) b. Compute the height of a tree c. Find the maximum element. d. Find the sum of the elements. e. Find the average of the elements. f. Find a specific item.

Answer 1

1 class BinaryTreeNode { /** <terminated > BinaryTree Example [Java A 1 3 6 7 9 15 Height: 3 * Stores the integer of this node 15 */ private int data; 6.833333333333333 false * Reference to the left Binary Tree 140 private Binary TreeNode left; /** * Reference to the right Binary Tree private Binary TreeNode right; * Default Constructor public Binary TreeNode() { left = null; right = null; data = 0; * Constructor which specifies the data to be stored 35 * @param data 39€ 40 */ public BinaryTreeNode(int data) { left = null; right = null; this.data = data;

// Node.java
class Node {
    /**
     * 
     * Stores the integer of this node
     * 
     */
    private int data;
    /**
     * 
     * Reference to the left Tree
     * 
     */
    private Node left;
    /**
     * 
     * Reference to the right Tree
     * 
     */
    private Node right;

    /**
     * 
     * Default Constructor
     * 
     */
    public Node() {
        left = null;
        right = null;
        data = 0;
    }

    /**
     * 
     * Constructor which specifies the data to be stored
     * 
     * @param data
     * 
     */
    public Node(int data) {
        left = null;
        right = null;
        this.data = data;
    }

    /**
     * 
     * Returns the data stored in this node
     * 
     * @return Data member variable
     * 
     */
    public int getData() {
        return data;
    }

    /**
     * 
     * Returns the left Binary Tree
     * 
     * @return Left binary tree
     * 
     */
    public Node getLeft() {
        return left;
    }

    /**
     * 
     * Returns the right Binary Tree
     * 
     * @return Right binary tree
     * 
     */
    public Node getRight() {
        return right;
    }

    /**
     * 
     * Inserts a node into either the left or right tree where appropriate
     * 
     * @param newData Reference to the new data
     * 
     */
    public void insert(int newData) {
        if (newData < data) {
            if (left == null)
                left = new Node(newData);
            else
                left.insert(newData);
        } else if (newData > data) {
            if (right == null)
                right = new Node(newData);
            else
                right.insert(newData);
        } else
            System.out.println("Duplicate - not adding " + newData);
    }

    public int height() {
        if (left == null && right == null) {
            return 1;
        }
        int l = 0;
        if (left != null) {
            l = left.height();
        }
        int r = 0;
        if (right != null) {
            r = right.height();
        }
        return 1 + Math.max(l, r);
    }
    
    public int count() {
        if (left == null && right == null) {
            return 1;
        }
        int l = 0;
        if (left != null) {
            l = left.count();
        }
        int r = 0;
        if (right != null) {
            r = right.count();
        }
        return 1 + l + r;
    }
}

// Tree.java
class Tree {
    /**
     * 
     * Reference to the root Node of the tree
     * 
     */
    Node root = null;

    /**
     * 
     * Insert the data into the tree
     * 
     * @param newData New int to store in the tree
     * 
     */
    public void insertInTree(int newData) {
        if (root == null)
            root = new Node(newData);
        else
            root.insert(newData);
    }

    /**
     * 
     * Method to display the contents of the tree
     * 
     */
    public void displayInOrder() {
        displayInOrder(root);
    }

    /**
     * 
     * Traverse the tree using InOrder traversal and display the content to the
     * console
     * 
     * @param subRoot The node to start with
     * 
     */
    private void displayInOrder(Node subRoot) {
        if (subRoot == null)
            return;
        displayInOrder(subRoot.getLeft());
        System.out.print(" " + subRoot.getData() + " ");
        displayInOrder(subRoot.getRight());
    }

    public int getHeight() {
        return root.height();
    }

    
    public int maxValue() {
        return maxValue(root);
    }
    
    public int maxValue(Node start) {
        int max = start.getData();

        if(start.getLeft() != null) {
            int x = maxValue(start.getLeft());
            if(x > max) {
                max = x;
            }
        }
        if(start.getRight() != null) {
            int x = maxValue(start.getRight());
            if(x > max) {
                max = x;
            }
        }
        
        return max;
    }

    public int numNodes() {
        return root.count();
    }

    public int treeSum() {
        return treeSum(root);
    }

    private int treeSum(Node subRoot) {
        int value = subRoot.getData();
        if(subRoot.getLeft() != null) {
            value += treeSum(subRoot.getLeft());
        }
        if(subRoot.getRight() != null) {
            value += treeSum(subRoot.getRight());
        }
        return value;
    }
    public double avg() {
        return treeSum() / (double) numNodes();
    }

    public boolean searchValue(int search) {
        return searchValue(root, search);
    }

    private boolean searchValue(Node subRoot, int search) {
        if (subRoot.getData() == search) {
            return true;
        }
        if (subRoot.getLeft() != null && searchValue(subRoot.getLeft(), search)) {
            return true;
        }
        if (subRoot.getRight() != null && searchValue(subRoot.getRight(), search)) {
            return true;
        }
        return false;
    }

}

// Main.java
public class Main {
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.insertInTree(6);
        tree.insertInTree(3);
        tree.insertInTree(9);
        tree.insertInTree(1);
        tree.insertInTree(15);
        tree.insertInTree(7);
        tree.displayInOrder();
        System.out.println();
        System.out.println("Height: " + tree.getHeight());
        
        System.out.println(tree.numNodes());
        System.out.println(tree.maxValue());
        System.out.println(tree.treeSum());
        System.out.println(tree.avg());
        System.out.println(tree.searchValue(40));
    }
}

please upvote. Thanks!