Use the Binary Tree code discussed in the lectures and add your implementation o
ID: 3907239 • Letter: U
Question
Use the Binary Tree code discussed in the lectures and add your implementation of the following methods in the Binary Tree class:
height(root) method that will return the height of the binary search tree.
search(element) method that performs the binary search for a specific element in the Binary Search Tree.
inOrder(root) method to print the elements in the tree in an inOrder sequence. Do not use recursion.
preorder(root) method to print the elements in the tree in preorder sequence. Use recursion.
delete(v) method that will delete a specific element in the tree.
internalCounter(root) method that returns the number of internal nodes in the binary search tree.
Write a BinaryTreeTester class to test your code by creating a Binary Search Tree.
Ask the user to enter 10 integer elements.
Print the size of the tree.
Print the height of the tree.
Print the tree’s elements in “inOrder” sequence.
Print the tree’s elements in “preOrder” sequence.
Ask the user for an element to be deleted from the tree, then use the delete method to delete that element.
Print the number of internal nodes in the tree using the internalCounter method.
Explanation / Answer
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class BTNode {
// Fields
public BTNode leftChild;
public BTNode rightChild;
public BTNode parent;
public int value;
// Constructors
public BTNode(){
leftChild = null;
rightChild = null;
value = Integer.MIN_VALUE;
}
public BTNode(int newValue){
leftChild = null;
rightChild = null;
value = newValue;
}
public BTNode(BTNode left, BTNode right, int newValue){
leftChild = left;
rightChild = right;
value = newValue;
}
// Mutators
public void setLeftChild(BTNode left){
leftChild = left;
}
public void setRightChild(BTNode right){
rightChild = right;
}
public void setData(int newValue){
value = newValue;
}
// Accessors
public BTNode getLeftChild(){
return leftChild;
}
public BTNode getRightChild(){
return rightChild;
}
public int getValue(){
return value;
}
// Comparators
public boolean isLessThan(BTNode b){
if(this.value < b.value){
return true;
}else{
return false;
}
}
public boolean isGreaterThan(BTNode b){
if(this.value > b.value){
return true;
}else{
return false;
}
}
public boolean isEqualTo(BTNode b){
if(this.value == b.value){
return true;
}else{
return false;
}
}
public int compare(BTNode b){
if(this.isLessThan(b)){
return -1;
}
if(this.isEqualTo(b)){
return 0;
}
if(this.isGreaterThan(b)){
return 1;
}
return Integer.MIN_VALUE;
}
}
public class BinaryTree {
// Fields
public BTNode root;
// Constructors
public BinaryTree(){
root = null;
}
public BinaryTree(BTNode root){
this.root = root;
}
// Helper Functions
public int getDepth(BTNode n){
if(n==null || root==null){return Integer.MIN_VALUE;}
int depth=0;
while(n.value!=root.value){
n=n.parent;
depth++;
}
return depth;
}
public boolean isInternalNode(BTNode n){
if(n.leftChild !=null || n.rightChild !=null){
return true;
}else{
return false;
}
}
public int countNumberOfNodes(BTNode curr){
if(curr==null){return 0;}
int count=0;
Queue<BTNode> hold = new LinkedList<BTNode>();
hold.add(curr);
while(!hold.isEmpty()){
BTNode x = hold.peek();
if(x.leftChild!=null){
hold.add(x.leftChild);
}
if(x.rightChild!=null){
hold.add(x.rightChild);
}
count++;
hold.poll();
}
return count;
}
// Insertion
public void insert(BTNode a){
if(a==null){return;}
if(root==null){root = a;root.parent=null;return;}
boolean hasNodeBeenAdded = false;
BTNode it = root;
while(!hasNodeBeenAdded){
switch (a.compare(it)){
case -1:
if(it.leftChild==null){
it.leftChild = a;
a.parent = it;
hasNodeBeenAdded=true;
}else{
it = it.leftChild;
}
break;
case 0:
System.out.println("Error - insert() - Node Already Exists.");
hasNodeBeenAdded=true;
break;
case 1:
if(it.rightChild==null){
it.rightChild = a;
a.parent = it;
hasNodeBeenAdded=true;
}else{
it = it.rightChild;
}
break;
case Integer.MIN_VALUE:
System.out.println("Error - insert() - Invalid Value.");
hasNodeBeenAdded=true;
break;
}
}
}
// Deletion
// Need to change algorithm to find the node to be deleted.
public boolean delete(BTNode n){
if(n==null){return false;}
if(root==null){return false;}
boolean deleted = false;
Queue<BTNode> hold = new LinkedList<BTNode>();
hold.add(root);
while(!hold.isEmpty() && !deleted){
BTNode x = hold.peek();
if(x.leftChild!=null){
hold.add(x.leftChild);
}
if(x.rightChild!=null){
hold.add(x.rightChild);
}
if(x.value==n.value){
if(x.rightChild!=null){ //Internal Node Handler
BTNode deepestLeft = getDeepestLeftNode(x.rightChild);
if(deepestLeft.rightChild!=null){ //Fix deepestLeft's right child (no left child, because it is deepest left)
deepestLeft.rightChild.parent=deepestLeft.parent;
deepestLeft.parent.leftChild=deepestLeft.rightChild;
deepestLeft.rightChild=null;
}
if(x.parent==null){ //DeepestLeft is new root
deepestLeft.parent=null;
root=deepestLeft;
}else{
if(x.parent.rightChild.isEqualTo(x)){ //Determine which child x is
deepestLeft.parent=x.parent;
deepestLeft.parent.rightChild=deepestLeft;
}
if(x.parent.leftChild.isEqualTo(x)){
deepestLeft.parent=x.parent;
deepestLeft.parent.leftChild=deepestLeft;
}
}
if(x.leftChild!=null){ //If deleted node has left child, reassign parent
deepestLeft.leftChild=x.leftChild;
deepestLeft.leftChild.parent=deepestLeft;
}
x.rightChild.parent=deepestLeft; //Fix original right childs relationship
deepestLeft.rightChild=x.rightChild;
deleted=true;
}
if(x.leftChild!=null && !deleted){ //Internal Node handler
x.parent.leftChild=x.leftChild;
x.leftChild.parent=x.parent;
deleted=true;
}
if(x.leftChild==null && x.rightChild==null && !deleted){ //Leaf node
if(x.parent!=null){
if(x.parent.rightChild.isEqualTo(x)){ //Determine which child x is
x.parent.rightChild=null;
}
if(x.parent.leftChild.isEqualTo(x)){
x.parent.leftChild=null;
}
}else{ //deleting root, when root is only node in tree.
root=null;
}
deleted=true;
}
}
hold.poll();
}
System.out.println("Error - delete() - Node not found.");
return deleted;
}
// Depth-first order Traversals
public void preorder(BTNode curr){
if(curr == null){
return;
}
doSomething(curr);
preorder(curr.leftChild);
preorder(curr.rightChild);
}
public void inorder(BTNode curr){
if(curr == null){
return;
}
inorder(curr.leftChild);
doSomething(curr);
inorder(curr.rightChild);
}
public void postorder(BTNode curr, String purpose){
if(curr == null){
return;
}
inorder(curr.leftChild);
inorder(curr.rightChild);
doSomething(curr);
}
public void doSomething(BTNode n){
System.out.print(n.value);
System.out.print(",");
}
// Binary Tree Properties
public int height(){
if(root==null){return 0;}
Queue<BTNode> hold = new LinkedList<BTNode>();
int deepestDepth = Integer.MIN_VALUE;
hold.add(root);
while(!hold.isEmpty()){
BTNode x = hold.peek();
if(x.leftChild!=null){
hold.add(x.leftChild);
}
if(x.rightChild!=null){
hold.add(x.rightChild);
}
if(getDepth(x) > deepestDepth){
deepestDepth = getDepth(x);
}
hold.poll();
}
return deepestDepth;
}
public int internalCounter(){
if(root==null){return 0;}
int counter = countNumberOfNodes(root);
return counter;
}
public BTNode getDeepestLeftNode(BTNode n){
if(n==null){
System.out.println("Error - getDeepestLeftNode() - returning bad node.");
return new BTNode(Integer.MIN_VALUE);
}
BTNode d = new BTNode(Integer.MIN_VALUE);
while(n!=null){
if(n.leftChild!=null){
n=n.leftChild;
}else{
return n;
}
}
System.out.println("Error - getDeepestLeftNode() - Returning bad node.");
return d;
}
public static void main(String[] args) {
// Binary Tree Construction
BinaryTree testTree = new BinaryTree();
Scanner sc = new Scanner(System.in);
for(int i=0; i<10; i++) {
System.out.println("Enter integer " + (i+1) + " : ");
int node;
node = sc.nextInt();
BTNode n = new BTNode(node);
testTree.insert(n);
}
System.out.println("Height of the tree : " + testTree.height());
System.out.println("PREORDER TRAVERSAL");
testTree.preorder(testTree.root);
System.out.println("INORDER TRAVERSAL");
testTree.inorder(testTree.root);
System.out.println("Enter the node to be deleted : ");
int delete = sc.nextInt();
testTree.delete(new BTNode(delete));
System.out.println("The number of internal nodes = " + testTree.countNumberOfNodes(testTree.root));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.