Question

Submit:    SearchTree.java  (again) with the following method added:

countSameData(SearchTree other); a public method that counts the number of tree nodes in "this" tree that are also contained in the "other" tree as determined by compareTo()==0. See example below.

You can either use your existing SearchTree from your homework exercises. Or you can start from scratch with this file that you should have started with days ago:  SearchTree.java

Further explanation:  I accomplished this by building upon many things we've done this quarter, recursion, tree traversals, and even java.util.* (yes import that if needed).

Since this BST requires Comparable, you must rely on .compareTo in case someone wants to use CalendarDate or String data for <E>

Order of data in the tree does not matter, just counting same data nodes, also knowing that trees can be empty, or compared to itself, as example below demonstrates:

SearchTree<Integer> zero = new SearchTree<Integer>();
SearchTree<Integer> one = new SearchTree<Integer>();
SearchTree<Integer> two = new SearchTree<Integer>();
one.add(9); one.add(8); one.add(7); // all left nodes
two.add(7); two.add(8); two.add(9); // all right nodes

System.out.println(one.equals(two)); // false
System.out.println(one.countSameData(two)); // 3
System.out.println(one.countSameData(one)); // 3
System.out.println(zero.countSameData(two)); // 0
two.remove(8);
System.out.println(one.countSameData(two)); // 2

public class SearchTree<E extends Comparable<E>> {
private SearchTreeNode<E> overallRoot; // root of overall tree

// post: constructs an empty search tree
public SearchTree() {
overallRoot = null;
}
  
// WRITE ADDITIONAL METHODS HERE:
  

  
  
  
  
  
  

// post: value added to tree so as to preserve binary search tree
public void add(E value) {
overallRoot = add(overallRoot, value);
}

// post: value added to tree so as to preserve binary search tree
private SearchTreeNode<E> add(SearchTreeNode<E> root, E value) {
if (root == null) {
root = new SearchTreeNode<E>(value);
} else if (root.data.compareTo(value) > 0) {
root.left = add(root.left, value);
} else if (root.data.compareTo(value) < 0) {
root.right = add(root.right, value);
}
return root;
}

// post: returns true if tree contains value, returns false otherwise
public boolean contains(E value) {
return contains(overallRoot, value);
}   

// post: returns true if given tree contains value, returns false otherwise
private boolean contains(SearchTreeNode<E> root, E value) {
if (root == null) {
return false;
} else {
int compare = value.compareTo(root.data);
if (compare == 0) {
return true;
} else if (compare < 0) {
return contains(root.left, value);
} else { // compare > 0
return contains(root.right, value);
}
}
}

// post: prints the data of the tree, one per line
public void print() {
printInorder(overallRoot);
}

// post: prints the data of the tree using an inorder traversal
private void printInorder(SearchTreeNode<E> root) {
if (root != null) {
printInorder(root.left);
System.out.println(root.data);
printInorder(root.right);
}
}

private static class SearchTreeNode<E> {
public E data; // data stored in this node
public SearchTreeNode<E> left; // left subtree
public SearchTreeNode<E> right; // right subtree

// post: constructs a leaf node with given data
public SearchTreeNode(E data) {
this(data, null, null);
}

// post: constructs a node with the given data and links
public SearchTreeNode(E data, SearchTreeNode<E> left,
SearchTreeNode<E> right) {
this.data = data;
this.left = left;
this.right = right;
}
}
}

Answer 1

//SearchTree.java

public class SearchTree<E extends Comparable<E>> {

      

      

       private SearchTreeNode<E> overallRoot; // root of overall tree

       // post: constructs an empty search tree

       public SearchTree() {

             overallRoot = null;

       }

      

            

       // post: value added to tree so as to preserve binary search tree

       public void add(E value) {

       overallRoot = add(overallRoot, value);

       }

       // post: value added to tree so as to preserve binary search tree

       private SearchTreeNode<E> add(SearchTreeNode<E> root, E value) {

       if (root == null) {

       root = new SearchTreeNode<E>(value);

       } else if (root.data.compareTo(value) > 0) {

       root.left = add(root.left, value);

       } else if (root.data.compareTo(value) < 0) {

       root.right = add(root.right, value);

       }

       return root;

       }

      

      

       // post: returns true if tree contains value, returns false otherwise

       public boolean contains(E value) {

       return contains(overallRoot, value);

       }

       // post: returns true if given tree contains value, returns false otherwise

       private boolean contains(SearchTreeNode<E> root, E value) {

       if (root == null) {

       return false;

       } else {

       int compare = value.compareTo(root.data);

       if (compare == 0) {

       return true;

       } else if (compare < 0) {

       return contains(root.left, value);

       } else { // compare > 0

       return contains(root.right, value);

       }

       }

       }

      

       // post: prints the data of the tree, one per line

       public void print() {

            

             if(overallRoot != null)

                    System.out.println("Root : "+overallRoot.data);

             printInorder(overallRoot);

       }

       // post: prints the data of the tree using an inorder traversal

       private void printInorder(SearchTreeNode<E> root) {

             if (root != null) {

      

                    printInorder(root.left);

            

                    System.out.println(root.data);

            

                    printInorder(root.right);

      

             }

       }

      

       // method that counts the number of tree nodes in "this" tree that are also contained in the "other" tree

       public int countSameData(SearchTree<E> other)

       {

             return(countSameDate(overallRoot,other));

       }

      

       // helper method to countSameDate

       private int countSameDate(SearchTreeNode<E> root, SearchTree<E> other)

       {

             // if the root is null

             if(root == null)

                    return 0;

             else if(other.contains(root.data)) // if root.data is present is other tree

             {

                    return 1+countSameDate(root.left,other)+countSameDate(root.right,other);

             }else // if root.data is not present is other tree

                    return countSameDate(root.left,other)+countSameDate(root.right,other);

       }

      

      

       // method that returns if this tree is equal to t2

       public boolean equals(SearchTree<E> t2) {

             return equals(overallRoot, t2.overallRoot);

       }

       private boolean equals(SearchTreeNode<E> n1, SearchTreeNode<E> n2) {

             if(n1 == null && n2 == null)

                    return true;

      

             if(n1 == null && n2 != null)

                    return false;

      

      

             if(n1 != null && n2 == null)

                    return false;

       return (n1.data == n2.data && equals(n1.left, n2.left) && equals(n1.right, n2.right));

       }

      

       // Removes the given value from this BST, if it exists.

       public void remove(E value) {

            

             overallRoot = remove(overallRoot, value);

       }

            

       private SearchTreeNode<E> remove(SearchTreeNode<E> root, E value) {

             if (root == null) {

                    return null;

             } else if (root.data.compareTo(value) > 0) {

                    root.left = remove(root.left, value);

             } else if (root.data.compareTo(value) < 0) {

                    root.right = remove(root.right, value);

             } else { // root.data == value; remove this node

                    if (root.right == null) {

                    return root.left; // no R child; replace w/ L

                    } else if (root.left == null) {

                    return root.right; // no L child; replace w/ R

                    } else {

                           SearchTreeNode<E> p = root.right;

                           SearchTreeNode<E> p_parent = root;

                           while(p.left != null)

                           {

                                 p_parent= p;

                                 p = p.left;

                           }

                          

                           if(p_parent != root)

                           {

                                 p_parent.left = null;

                                 p.left = root.left;

                                 p.right = root.right;

                           }else

                           {

                                 p.left = root.left;

                           }

                          

                           return p;

                    }

             }

                    return root;

       }

      

       private static class SearchTreeNode<E> {

             public E data; // data stored in this node

             public SearchTreeNode<E> left; // left subtree

             public SearchTreeNode<E> right; // right subtree

             // post: constructs a leaf node with given data

             public SearchTreeNode(E data) {

                    this(data, null, null);

             }

             // post: constructs a node with the given data and links

             public SearchTreeNode(E data, SearchTreeNode<E> left,SearchTreeNode<E> right) {

      

                    this.data = data;

      

                    this.left = left;

      

                    this.right = right;

      

                    }

             }

      

}

//end of SearchTree.java

//MainSearchTree.java

public class MainSearchTree {

      

      

       public static void main(String[] args)

       {

             SearchTree<Integer> zero = new SearchTree<Integer>();

             SearchTree<Integer> one = new SearchTree<Integer>();

             SearchTree<Integer> two = new SearchTree<Integer>();

             one.add(9); one.add(8); one.add(7); // all left nodes

             two.add(7); two.add(8); two.add(9); // all right nodes

             System.out.println(one.equals(two)); // false

             System.out.println(one.countSameData(two)); // 3

             System.out.println(one.countSameData(one)); // 3

             System.out.println(zero.countSameData(two)); // 0

             two.remove(8);

             System.out.println(one.countSameData(two)); // 2

       }

}

//end of MainSearchTree.java

Output: