Chapter 25, Problem 25.7PE

Program Plan Intro

Program Plan:

Include the required packages. Define the class “Test”.

• Define the driver method “main”.
  • Declare the object for the “BST” class.
  • Call the method “insert” to add string values to the tree.
  • Call the “getNumberOfNonLeaves” method and display the result.
• Define the “BST” class.
  • Define the “getNumberOfNonLeaves” method.
    • Return the number of non-leaves node.
      • Define the overridden method “getNumberOfNonLeaves”.
        • If the “root” is “null”,
        • • return “0”.
        • If the “root.left” or “root.right” is not “null”,
        • • Return the number of non-leaves node.
        • Otherwise,
        • • return “0”.
      • Declare the required variables.
      • Create a constructor for “BST” class.
      • Create a constructor for “BST” by passing array of objects.
      • Define the “search” method to search the required data in the binary search tree.
      • Define the “insert” method.
        • If the root is null create the tree otherwise insert the value into left or right subtree.
      • Define the “createNewNode”
        • Return the result of new node creations.
      • Define the “inorder”
        • Inorder traverse from the root.
      • Define the protected “inorder” method
        • Traverse the tree according to the inorder traversal concept.
      • Define the “postorder”
        • Postorder traverse from the root.
      • Define the protected “postorder” method
        • Traverse the tree according to the postorder traversal concept.
      • Define the “preorder”
        • Preorder traverse from the root.
      • Define the protected “preorder” method
        • Traverse the tree according to the preorder traversal concept.
      • Define the “TreeNode” class
        • Declare the required variables.
        • Define the constructor.
      • Define the “getSize” method.
        • Return the size.
      • Define the “getRoot” method
        • Return the root.
      • Define the “java.util.ArrayList” method.
        • Create an object for the array list.
        • If the “current” is not equal to null, add the value to the list.
        • If the “current” is less than 0, set the “current” as left subtree element otherwise set the “current” as right subtree element.
        • Return the list.
      • Define the “delete” method.
        • If the “current” is not equal to null, add the value to the list.
        • If the “current” is less than 0, delete the “current” as left subtree element otherwise delete the “current” as right subtree element.
        • Return the list.
      • Define the “iterator” method.
        • Call the “inorderIterator” and return the value.
      • Define the “inorderIterator”
        • Create an object for that method and return the value
      • Define the “inorderIterator” class.
        • Declare the variables.
        • Define the constructor.
        • • Call the “inorder” method.
        • Define the “inorder” method.
        • • Call the inner “inorder” method with the argument.
        • Define the TreeNode “inorder” method.
        • • If the root value is null return the value, otherwise add the value into the list.
        • Define the “hasNext” method
        • • If the “current” value is less than size of the list return true otherwise return false.
        • Define the “next” method
        • • Return the list.
        • Define the “remove” method.
        • • Call the delete method.
          • Clear the list then call the “inorder” method.
      • Define the “clear” method
        • Set the values to the variables
• Define the interface.
  • Declare the required methods.
  • Define the required methods.