Question

Instructions. You are provided four skeleton program named TreeNode.java and Binary Search Tree.java. The source files are available on Canvas in a folder named HW4. Please modify the skeleton code to solve the following tasks. • Task 1 (10 pts). Implement the inorder-tree-walk() function as discussed in Lecture 7. • Task 2 (20 pts). Implement the search() function as discussed in Lecture • Task 3 (10 pts). Implement the iterative search() function as discussed in Lecture 7. • Task 4 (10 pts). Implement the minimum() function as discussed in Lec- ture 7. • Task 5 (10 pts). Implement the marimum() function as discussed in Lcc- ture 7. • Task 6 (20 pts). Implement the successor() function as discussed in Lec- ture 7. • Task 7 (20 pts). Implement the insert() function as discussed in Lecture • Task 8 (10 pts Extra Credit). Implement the preorder_tree_walk() and postorder-tree-walk() functions as discussed in Lecture 7. . Note: The parameters in some functions are different from the slides. You should not change the parameter for any function.

TreeNode.java

public class TreeNode {
   public int key;
   public TreeNode p;
   public TreeNode left;
   public TreeNode right;
  
   public TreeNode () {
       p = left = right = null;
   }
  
   public TreeNode (int k) {
       key = k;
       p = left = right = null;
   }
}

BinarySearchTree.java

public class BinarySearchTree {
   public TreeNode root;
  
   public BinarySearchTree () {
       root = null;
   }
  
   public void inorder_tree_walk (TreeNode x) {
      
   }
  
   public TreeNode search (TreeNode x, int k) {
      
   }
  
   public TreeNode iterative_search (int k) {
      
   }
  
   public TreeNode minimum () {
      
   }
  
   public TreeNode maximum () {
      
   }
  
   public TreeNode successor (TreeNode x) {
      
   }
  
   public void insert (int k) {
      
   }
  
   /**
   * @param args
   */
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       int[] array = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
       BinarySearchTree bst;
       TreeNode n;
      
       bst = new BinarySearchTree();
       for (int i = 0; i < array.length; i++)
           bst.insert(array[i]);
      
       System.out.println("Inorder_tree_walk starts ------------------");
       bst.inorder_tree_walk(bst.root);
       System.out.println("Inorder_tree_walk ends ------------------");
       System.out.print("\n\n");
      
       System.out.println("Search starts ------------------");
       n = bst.search(bst.root, 13);
       System.out.println("found: " + n.key);
       System.out.println("Search ends ------------------");
       System.out.print("\n\n");

       System.out.println("Iterative search starts ------------------");
       n = bst.iterative_search(4);
       System.out.println("found: " + n.key);
       System.out.println("Iterative search ends ------------------");
       System.out.print("\n\n");
      
       System.out.println("Minimum starts ------------------");
       n = bst.minimum();
       System.out.println("Minimum key is " + n.key);
       System.out.println("Minimum ends ------------------");
       System.out.print("\n\n");
      
       System.out.println("Maximum starts ------------------");
       n = bst.maximum();
       System.out.println("Maximum key is " + n.key);
       System.out.println("Maximum ends ------------------");
       System.out.print("\n\n");

       System.out.println("Successor starts ------------------");
       n = bst.successor(bst.root.left.right.right);
       System.out.println("Successor key is " + n.key);
       System.out.println("Successor ends ------------------");
       System.out.print("\n\n");
   }

}

Answer 1

156 157 158 159 160 161 bst new BinarySearchTree ( ) ; for (int i 0; i < array.length; i+) bst.insert(array [i]) <terminated> BinarySearchTree (2) Java Application] CAProgran System.out.println (" Inorder tree_walk bst.inorder_tree_walk (bst.root); System.out.println("Inorder_treewalk System.out.print("\n\n"); starts "); 6 7 -"); ends 13 164 165 166 167 168 169 15 System.out.println("Search starts bst.search(bst.root, 13); System.out.println ("found: " n.key); System.out.println ("Search ends System.out.print("\n\n"); .") ; 17 20 -"); Inorder_tree_walk ends System.out.println("Iterative search starts n bst.iterative_search (4); System.out.println ("found: " + n.key); System.out.println("Iterative search ends System.out.print ("\n\n") ; -"); Search starts found: 13 172 173 174 175 176 177 Search ends "); Iterative search starts found: 4 System.out.println("Minimum starts n bst.minimum); ") ; Iterative search ends ("Minimum key is n.key); 180 181 182 183 184 185 System.out.println ( "Minimum ends System.out.print("\n\n") ; ') Minimum starts 2 System.out.println ( "Maximum starts bst.maximum); System.out.println ( "Maximum key is System.out.printintidxmum ends System.out.print("\n\n"); "); Minimum ends n n.key) Maximum starts 187 188 189 190 191 192 193 194 195 Maximum key is 20 Maximum ends System.out.println("Successor starts n= bst.successor (bst.root.left.right.right) System.out.println("Successor key is" n.key) System.out.println("Successor ends System.out.print("\n\n"); } -"); Successor starts ") ; 15 Successor ends

public class BinarySearchTree {

        class TreeNode {
                public int key;
                public TreeNode p;
                public TreeNode left;
                public TreeNode right;

                public TreeNode() {
                        p = left = right = null;
                }

                public TreeNode(int k) {
                        key = k;
                        p = left = right = null;
                }
        }

        public TreeNode root;

        public BinarySearchTree() {
                root = null;
        }

        public void inorder_tree_walk(TreeNode x) {
                if(x != null) {
                        inorder_tree_walk(x.left);
                        System.out.println(x.key);
                        inorder_tree_walk(x.right);
                }
        }

        public TreeNode search(TreeNode x, int k) {
                if(x == null) {
                        return null;
                }
                if(x.key == k) {
                        return x;
                }
                if(x.key > k) {
                        return search(x.left, k);
                } else {
                        return search(x.right, k);
                }
        }

        public TreeNode iterative_search(int k) {
                TreeNode start = root;
                
                while(start != null) {
                        if(start.key == k) {
                                return start;
                        }
                        if(start.key > k) {
                                start = start.left;
                        } else {
                                start = start.right;
                        }
                }
                
                return start;
        }

        public TreeNode minimum() {
                TreeNode start = root;
                if(root == null) {
                        return null;
                }
                
                while(start.left != null) {
                        start = start.left;
                }
                
                return start;
        }

        public TreeNode maximum() {
                TreeNode start = root;
                if(root == null) {
                        return null;
                }
                
                while(start.right != null) {
                        start = start.right;
                }
                
                return start;
        }

        public TreeNode successor(TreeNode x) {
                if (x == null) {
                        return null;
                } else if (x.right != null) {
                        // successor is leftmost Entry in right subtree of e
                        TreeNode p = x.right;
                        while (p.left != null) {
                                p = p.left;
                        }
                        return p;

                } // e has a right child
                else {

                        // go up the tree to the left as far as possible, then go up
                        // to the right.
                        TreeNode temp = x.p;
                        TreeNode ch = x;
                        while ((temp != null) && (ch == temp.right)) {
                                ch = temp;
                                temp = temp.p;
                        } // while
                        return temp;
                } // e has no right child
        }

        public void insert(int k) {
                TreeNode newNode = new TreeNode(k);
                
                if(root == null) {
                        root = newNode;
                } else {
                        TreeNode parent = root;
                        while(true) {
                                if(parent.key == k) {
                                        return;
                                }
                                if(parent.key > k) {
                                        if(parent.left == null) {
                                                parent.left = newNode;
                                                newNode.p = parent;
                                                return;
                                        } else {
                                                parent = parent.left;
                                        }
                                } else {
                                        if(parent.right == null) {
                                                parent.right = newNode;
                                                newNode.p = parent;
                                                return;
                                        } else {
                                                parent = parent.right;
                                        }
                                }
                        }
                }
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                int[] array = { 15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 };
                BinarySearchTree bst;
                TreeNode n;

                bst = new BinarySearchTree();
                for (int i = 0; i < array.length; i++)
                        bst.insert(array[i]);

                System.out.println("Inorder_tree_walk starts ------------------");
                bst.inorder_tree_walk(bst.root);
                System.out.println("Inorder_tree_walk ends ------------------");
                System.out.print("\n\n");

                System.out.println("Search starts ------------------");
                n = bst.search(bst.root, 13);
                System.out.println("found: " + n.key);
                System.out.println("Search ends ------------------");
                System.out.print("\n\n");

                System.out.println("Iterative search starts ------------------");
                n = bst.iterative_search(4);
                System.out.println("found: " + n.key);
                System.out.println("Iterative search ends ------------------");
                System.out.print("\n\n");

                System.out.println("Minimum starts ------------------");
                n = bst.minimum();
                System.out.println("Minimum key is " + n.key);
                System.out.println("Minimum ends ------------------");
                System.out.print("\n\n");

                System.out.println("Maximum starts ------------------");
                n = bst.maximum();
                System.out.println("Maximum key is " + n.key);
                System.out.println("Maximum ends ------------------");
                System.out.print("\n\n");

                System.out.println("Successor starts ------------------");
                n = bst.successor(bst.root.left.right.right);
                System.out.println("Successor key is " + n.key);
                System.out.println("Successor ends ------------------");
                System.out.print("\n\n");
        }

}

please upvote. Thanks!