Below is my code. Please help me fill in the remaining methods (towards Bottom).
ID: 3581656 • Letter: B
Question
Below is my code. Please help me fill in the remaining methods (towards Bottom).
import java.util.Iterator;
import javax.xml.soap.Node;
public class BinaryTreeSortedList> implements SortedListInterface {
@SuppressWarnings("hiding")
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
class BinarySearchTree {
public Node root;
public BinarySearchTree(){
this.root = null;
}
public boolean find(int id){
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
}
@Override
public boolean add(T newEntry) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean remove(T anEntry) {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean contains(T anEntry) {
// TODO Auto-generated method stub
return false;
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public int getLength() {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public T[] toArray() {
// TODO Auto-generated method stub
return null;
}
}
public interface SortedListInterface<T extends Comparable<? super T>> {
/**
* Adds a new entry to this list in its proper order, if it does not match
* an existing object in the list.
*
* @param newEntry
* An object to be added to the list.
* @return True if the object was added to the list, otherwise return false.
*/
public boolean add(T newEntry);
/**
* Removes the only occurrence of a specified entry from this
* sorted list.
*
* @param anEntry
* The object to be removed.
* @return True if anEntry was located and removed; otherwise returns false.
*/
public boolean remove(T anEntry);
/**
* Sees whether this list contains a given entry.
*
* @param anEntry
* The object that is the desired entry.
* @return True if the list contains anEntry, or false if not.
*/
public boolean contains(T anEntry);
/** Removes all entries from this list. */
public void clear();
/**
* Gets the length of this list.
*
* @return the integer number of entries currently in the list.
*/
public int getLength();
/**
* Sees whether this list is empty.
*
* @return true if the list is empty, or false if not.
*/
public boolean isEmpty();
/**
* Retrieves all entries that are in this list in the order in which they
* occur in the list.
*
* @return A newly allocated array of all the entries in the list. Note: If
* the list is empty, the returned array is empty.
*/
// Note: Can change return type to Object[] if T[] causes problems
public T[] toArray();
/**
*
* @return the sorted list of values with a space between each value
*/
public String toString();
} // end SortedListInterface
Create a class(using generics) called BinaryTreeSortedList that implements this interface with a sorted list
Explanation / Answer
import java.util.*;
class ListNode
{
int data;
ListNode next;
ListNode(int d)
{
data = d;
next = null;
}
}
class BinaryTreeNode
{
int data;
BinaryTreeNode left, right = null;
BinaryTreeNode(int data)
{
this.data = data;
left = right = null;
}
}
class BinaryTree
{
ListNode head;
BinaryTreeNode root;
void push(int new_data)
{
ListNode new_node = new ListNode(new_data);
new_node.next = head;
head = new_node;
}
BinaryTreeNode convertList2Binary(BinaryTreeNode node)
{
Queue<BinaryTreeNode> q =
new LinkedList<BinaryTreeNode>();
if (head == null)
{
node = null;
return null;
}
node = new BinaryTreeNode(head.data);
q.add(node);
head = head.next;
while (head != null)
{
BinaryTreeNode parent = q.peek();
BinaryTreeNode pp = q.poll();
BinaryTreeNode leftChild = null, rightChild = null;
leftChild = new BinaryTreeNode(head.data);
q.add(leftChild);
head = head.next;
if (head != null)
{
rightChild = new BinaryTreeNode(head.data);
q.add(rightChild);
head = head.next;
}
parent.left = leftChild;
parent.right = rightChild;
}
return node;
}
void inorderTraversal(BinaryTreeNode node)
{
if (node != null)
{
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.push(36);
tree.push(30);
tree.push(25);
tree.push(15);
tree.push(12);
tree.push(10);
BinaryTreeNode node = tree.convertList2Binary(tree.root);
System.out.println("Inorder Traversal of the"+
" constructed Binary Tree is:");
tree.inorderTraversal(node);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.