Chapter 11: "Binary Trees"

Data Structures with Java, Rick Mercer

Answers to Self-Check Questions



11-1 identify n
	a) o->|theRootValue|   c) baker, charlie, echo, foxtrot    e) echo, foxtrot
	b) 7                   d) theRootValue, able, delta        f) 0

11-2

TreeNode root = new TreeNode (theRootValue);

root.left = new TreeNode("able");
root.left.left = new TreeNode("baker");
root.left.right = new TreeNode("charlie");

root.right = new TreeNode ("delta");
root.right.left = new TreeNode ("echo");
root.right.right = new TreeNode ("foxtrot");

11-3 inOrder, preorder and postOrder traversal
	a) inOrder = 5 + 4 * 2 / 3 * 6
	b) preorder = * + 5 4 / 2 * 3 6
	c) postOrder = 5 4 + 2 3 6 * / * 

11-4 postOrderPrint method

private void postOrderPrint (TreeNode){
    if(t != null) {
        postOrderPrint(t.left);
        postOrderPrint(t.right);
        System.out.print(t.data + " ");
    }
}

11-5

  private String max;

  public String findMax() {
    if (root == null)
      return null;
    else {
      max = root.data;
      findMaxHelper(root);
      return max;
    }
  }
  
  public void findMiaxHelper(TreeNode t) {
    if (t != null) {
      String temp = t.data;
      if (temp.compareTo(max) > 0)
        max = temp;
      findMaxHelper(t.left);
      findMaxHelper(t.right);
    }
  }

11-6 size method

private int ;

public int size() {
    size = 0;
    getSize(root);
    return size;
}

private void getSize(TreeNode t) {
    if(t != null){
        size++;
        getSize(t.left);
        getSize(t.right);
    }
}

11-7 print inOrder method

public void printInOrder{
    printInOrderHelper(root);
}

private voide printInOrderHelper(TreeNode t) {
    if(t != null){
	printInOrderHelper(t.left);
	System.out.print(t.data);
	PrintInOrderHelper(t.right);
    }
}

11-8 isFull method

public boolean isFull() {
    return isFull(root);
}

private boolean isFull(TreeNode t) {
    if (t == null)
 	return true;
    else if (t.left == null && t.right != null || t.left != null && t.right == null)
	return false;
    else
	return isFull(t.left) && isFull(t.right);
}