Objective IN JAVA: (Please follow directions given) Trees sure are neat. Let’s t

Question

Objective IN JAVA: (Please follow directions given)

Trees sure are neat. Let’s take this slow and simple and make a tree of integers.

Create a class IntBSTree with the following

Internal class Node

- Instance variables

- data: an integer value

- leftChild: a Node representing the child to the left

- rightChild: a Node representing the child to the right

Instance variables

- root: a Node representing the first element in the tree.

Methods

insert: This method returns nothing and takes in an integer value that is then placed as a new node in the tree based on the binary tree properties. A reminder values greater than the parent go to the right subtree and values smaller go to the left subtree. Also it may be a good idea to use a recursive method in order to place these values.

remove: This method returns nothing and takes in an integer value that is to be removed. First the method must search for the value. If the value is found the it is removed while preserving the integrity of the binary search tree. Remember there are cases for the node having no children, having one child, and having two children.

printPreorder: This method which returns nothing and has no parameters prints the pre-order traversal of the tree. For pre-order traversal each the value is printed out, then left subtree must be visited, and finally each of the right subtrees is visited. It is a good idea to make a recursive method to assist with this.

getDepth: The depth of a node is the number of edges from the root to that number. This method returns nothing and takes in a parameter corresponding to the integer value of a node whose depth is returned. If the value is not in the tree a -1 should be returned. Again a recursive helper method may be useful to solve this.

Create another file that creates an instance of the IntBSTree and tests each of the methods.

Example Output:

Testing the tree

Insterting 10 numbers

Inserting 8

Inserting 13

Inserting 3

Inserting 4

Inserting 18

Inserting 19

Inserting 10

Inserting 1

Inserting 9

Inserting 2

Printing pre-order traversal

8

3

1

2

4

13

10

9

18

19

Removing the number 4

8

3

1

2

13

10

9

18

19

The Depth of 9 is 3

Done!

Explanation / Answer

Here is the code for the class:

class IntBSTree
{
    private class Node {
private int data; // associated data
private Node leftChild, rightChild; // left and right subtrees
private int N; // number of nodes in subtree
public Node(int val) {
this.data = val;
this.leftChild = null;
this.rightChild = null;
}
}
  
Node root;
  
public IntBSTree() {
root = null;
}
  
public boolean isEmpty() {
return size() == 0;
}
  
public int size() {
return size(root);
}
  
// return number of key-value pairs in BST rooted at x
private int size(Node x) {
if (x == null) return 0;
else return x.N;
}
  
/*private int height(Node root) {
int leftSide = 0;
int rightSide = 0;
  
if (root != null){
if (root.leftChild != null){
leftSide = height(root.leftChild);
}
if (root.rightChild != null){
rightSide = height(root.rightChild);
}
}
return leftSide > rightSide ? leftSide + 1 : rightSide + 1;
}*/
  
// insert: This method returns nothing and takes in an integer value that is then
// placed as a new node in the tree based on the binary tree properties.
// A reminder values greater than the parent go to the right subtree and values
// smaller go to the left subtree. Also it may be a good idea to use a recursive
// method in order to place these values.
void insert(int value)
{
Node newNode = new Node(value);
  
if (root == null)
root = newNode;
else {
Node tempNode = root;
Node tempParent = null;
while (tempNode!=null){
tempParent = tempNode;
if (value < tempNode.data)
tempNode = tempNode.leftChild;
else
tempNode = tempNode.rightChild;
}
  
if (value < tempNode.data)
tempNode.leftChild = newNode;
else
tempNode.rightChild = newNode;
  
}
}

// printPreorder: This method which returns nothing and has no parameters prints the
// pre-order traversal of the tree. For pre-order traversal each the value is printed
// out, then left subtree must be visited, and finally each of the right subtrees is
// visited. It is a good idea to make a recursive method to assist with this.
void printPreorder()
{
    printPreorderHelper(root);
}
void printPreorderHelper(Node root)
{
    if(root != null)
    {
       System.out.println(root.data);
       printPreorderHelper(root.leftChild);
       printPreorderHelper(root.rightChild);
    }
}

// getDepth: The depth of a node is the number of edges from the root to that number.
// This method returns nothing and takes in a parameter corresponding to the integer
// value of a node whose depth is returned. If the value is not in the tree a -1
// should be returned. Again a recursive helper method may be useful to solve this.
public int getDepth(int val)
{
    return getDepth(val, root);  
}
public int getDepth(int val, Node root)
{
    if(root == null)
        return -1;
    else if(val < root.data)
        return getDepth(val, root.leftChild);
    else if(val > root.data)
        return getDepth(val, root.rightChild);
    else
        return height(root);      
}
private int height(Node tree){
if(tree == null)
return 0;
return Math.max(height(tree.leftChild), height(tree.rightChild))+1;
}
  
// remove: This method returns nothing and takes in an integer value that is to be
// removed. First the method must search for the value. If the value is found the it
// is removed while preserving the integrity of the binary search tree. Remember there
// are cases for the node having no children, having one child, and having two children.
private void remove(int value) {
/*if (root == null)
   return;
if (value < root.data)
   delete(root.leftChild, value);
else if (value > root.data)
   delete(root.rightChild, value);
else {
if (root.rightChild == null)
   return;
if (root.leftChild == null)
   return;
Node t = root;
root = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;*/
  
  
// Find node to be removed

Node toBeRemoved = root;
Node parent = null;
boolean found = false;
while (!found && toBeRemoved != null)
{
if (toBeRemoved.data == value)
    found = true;
else
{
parent = toBeRemoved;
if (value < toBeRemoved.data)
   toBeRemoved = toBeRemoved.leftChild;
else
   toBeRemoved = toBeRemoved.rightChild;
}
}

if (!found) return;

// toBeRemoved contains obj

// If one of the children is empty, use the other

if (toBeRemoved.leftChild == null || toBeRemoved.rightChild == null)
{
Node newChild;
if (toBeRemoved.leftChild == null)
newChild = toBeRemoved.rightChild;
else
newChild = toBeRemoved.leftChild;

if (parent == null) // Found in root
root = newChild;
else if (parent.leftChild == toBeRemoved)
parent.leftChild = newChild;
else
parent.rightChild = newChild;
return;
}
  
// Neither subtree is empty

// Find smallest element of the right subtree

Node smallestParent = toBeRemoved;
Node smallest = toBeRemoved.rightChild;
while (smallest.leftChild != null)
{
smallestParent = smallest;
smallest = smallest.leftChild;
}

// smallest contains smallest child in right subtree

// Move contents, unlink child

toBeRemoved.data = smallest.data;
if (smallestParent == toBeRemoved)
smallestParent.rightChild = smallest.rightChild;
else
smallestParent.leftChild = smallest.rightChild;

}

}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.