Binary Search Tree in JAVA Implement the BinarySearchTree class. The BinarySearc

Question

Binary Search Tree in JAVA

Implement the BinarySearchTree class. The BinarySearchTree class extends the BinaryTree class which implements the Tree interface. All can be seen here. Your assignment is to implement all of the abstract methods of the BinaryTree class recursively.

They are:

Insert.

Iterator (non-recursive).

Remove.

Search.

You must also implement an Iterator inner class for the BinarySearchTree class. You must submit a modified BinarySearchTree.java file with your source code.

Do not submit and do not modify the Tree.java or BinaryTree.java files.

Explanation / Answer

here is your code : ------------>>>>>>>>>>>

import java.util.Iterator;
import java.util.Stack;

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

    private void insert(Node<E> root,E data){
        if(data.compareTo(root.data) < 0){
            if(root.left == null){
                root.left = new Node<E>(data);
                root.left.left = null;
                root.left.right = null;
                return;
            }else{
                insert(root.left,data);
            }
        }else if(data.compareTo(root.data) > 0){
            if(root.right == null){
                root.right = new Node<E>(data);
                root.right.left = null;
                root.right.right = null;
                return;
            }else{
                insert(root.right,data);
            }
        }else{
            return;
        }
    }

    public void insert(E data) {
        if(root == null){
            root = new Node<E>(data);
            root.left = null;
            root.right = null;
        }else{
            insert(root,data);
        }
        return;
    }

    public Iterator<E> iterator() {
        return new MyIterator(root);
    }

    private void remove(Node<E> root,E data){
        if(root.left != null){
            if(root.left.data.compareTo(data) == 0){
                if(root.left.left == null && root.left.right == null){
                    root.left = null;
                }else if(root.left.left == null){
                    root.left = root.left.right;
                }else if(root.left.right == null){
                    root.left = root.left.left;
                }else{
                    Node<E> cur = root.left.right;
                    while(cur.left != null){
                        cur = cur.left;
                    }
                    cur.left = root.left.left;
                    root.left = root.left.right;
                }
            }
        }
        if(root.right != null){
            if(root.right.data.compareTo(data) == 0){
                if(root.right.left == null && root.right.right == null){
                    root.right = null;
                }else if(root.right.left == null){
                    root.right = root.right.right;
                }else if(root.right.right == null){
                    root.right = root.right.left;
                }else{
                    Node<E> cur = root.right.right;
                    while(cur.left != null){
                        cur = cur.left;
                    }
                    cur.left = root.right.left;
                    root.right = root.right.right;
                }
            }
        }
         if(data.compareTo(root.data) < 0){
            if(root.left == null){
                return;
            }else{
                remove(root.left,data);
            }
        }else if(data.compareTo(root.data) > 0){
            if(root.right == null){
                return;
            }else{
                remove(root.right,data);
            }
        }
    }

    public void remove(E key) {
        if(root == null){
            return;
        }else if(root.data.compareTo(key) == 0){
            if(root.left == null && root.right == null){
                root = null;
            }else if(root.left == null){
                root = root.right;
            }else if(root.right == null){
                root = root.left;
            }else{
                Node<E> cur = root.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
            }
        }
        else{
            remove(root,key);
        }
        return;
    }

    private boolean search(Node<E> root,E data){
        if(data.compareTo(root.data) < 0){
            if(root.left == null){
                return false;
            }else{
                return search(root.left,data);
            }
        }else if(data.compareTo(root.data) > 0){
            if(root.right == null){
                return false;
            }else{
                return search(root.right,data);
            }
        }else{
            return true;
        }
    }

    public boolean search(E key) {
        if(this.root == null){
            return false;
        }
        return search(this.root,key);
    }

    public class MyIterator<E> implements Iterator<E>{

        private Stack<Node<E>> stack = new Stack<>();
        private Node<E> current;

        public MyIterator(Node<E> argRoot) {
            current = argRoot;
        }

        public E next() {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            Node<E> node = current;
            current = current.right;

            return node.data;
        }

        public boolean hasNext() {
            return (!stack.isEmpty() || current != null);
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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