Chapter 17, Problem 7PE

Program Plan Intro

Adding methods to Binary Tree

Program plan:

BinaryTree.java:

• Define the class “BinaryTree.java”.
• Declare the private variable root from class “Node”.
• Defining the constructor “BinaryTree” to generate an empty tree.
  • Assign root to null.
• Define the parameterized constructor “BinaryTree(object rootData)” to generate a tree one root element.
  • Generate root node.
• Define the parameterized constructor “public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)”.
  • Generates root and children nodes.
• Define the “preorder()” method for both tree with many nodes and a tree with one node.
  • For a tree with one node and no children,
    • “preorder(root,v)” is called.
      • For a tree with multiple nodes,
        • If (node == null) returns v.visit(node.data);
        • If (node.left != null) then, preorder(node.left, v);
        • If (node.right != null) then, preorder(node.right, v);
• Define the “inorder()” method for both tree with many nodes and a tree with one node.
  • For a tree with one node and no children,
    • “inorder(root,v)” is called.
      • For a tree with multiple nodes,
        • If (node.left != null) then,  inorder(node.left, v) and v.visit(node.data);
        • If (node.right != null) then, inorder(node.right, v);
• Define the “postorder()” method for both tree with many nodes and a tree with one node.
  • For a tree with one node and no children,
    • “postorder(root,v)” is called.
      • For a tree with multiple nodes,
        • If (node.left != null) then, postorder(v, node.left);
        • If (node.right != null) then, postorder(v, node.right) and v.visit(node.data);
• Define the class “Node”.
  • Declare “object data”.
  • Declare “Node left”.
  • Declare “Node right”.
• Define the function static “height()”
  • If (n == null) returns the null value.
  • Otherwise returns the value 1 + Math.max(height(n.left), height(n.right)).
• Define the function “height()”
  • Returns the height of this tree.
• Define “isEmpty()” function:
  • It checks whether this tree is empty.
  • Return true value if this tree is empty.
• Define the “data()” function.
  • Gets the data at the root of this tree.
  • Returns the root data.
• Define “left()” and “right()” function.
  • “left()” function return the left child of the root.
  • “right()” function return the right child of the root.

Visitor.java:

• Define interface “Visitor”
• Calls the “visit(object data)”

BinaryTreeTester.java:

• Import the required header files.
• Define “BinaryTreeTester” class.
  • Define the “main()” function.
    • Create an object “names” for “BinaryTree” with tree values.
    • Create an object “visit” for “Visitor” object and print the data.
    • Call “inorder()”, “preoder()” and “postorder()” function.