Universidad Carlos III de Madrid

Note

Remember that two classes, BTree and BNode, are required in order to represent properly the empty tree.

Solution

Solutions are at the end of the exercercises.

Solution

Solutions are at the end of the exercercises.

Solution

Solutions are at the end of the exercercises.

Solution

Solutions are included in the following listing:

public class BTree<E> {

  /* ********************************************** *
   * CLASS BNode * **********************************************
   */

  static class BNode<E> {

    private E info;
    private BNode<E> left;
    private BNode<E> right;

    BNode(E info) {
      this(info, null, null);
    }

    BNode(E info, BNode<E> l, BNode<E> r) {
      this.info = info;
      left = l;
      right = r;
    }

    E getInfo() {
      return info;
    }

    BNode<E> getLeft() {
      return left;
    }

    BNode<E> getRight() {
      return right;
    }

    void setInfo(E info) {
      this.info = info;
    }

    void setLeft(BNode<E> left) {
      this.left = left;
    }

    void setRight(BNode<E> right) {
      this.right = right;
    }

    void insert(BNode<E> tree, int side) throws BTreeException {
      if (side == LEFT_SIDE) {
        if (left == null) {
          left = tree;
        } else {
          throw new BTreeException("A non-empty tree already exists");
        }
      } else if (side == RIGHT_SIDE) {
        if (right == null) {
          right = tree;
        } else {
          throw new BTreeException("A non-empty tree already exists");
        }
      } else {
        throw new BTreeException("Incorrect side");
      }
    }

    BNode<E> extract(int side) throws BTreeException {
      BNode<E> subtree;
      if (side == LEFT_SIDE) {
        subtree = left;
        left = null;
      } else if (side == RIGHT_SIDE) {
        subtree = right;
        right = null;
      } else {
        throw new BTreeException("Incorrect side");
      }
      return subtree;
    }

    int size() {
      int size = 1;
      if (left != null) {
        size += left.size();
      }
      if (right != null) {
        size += right.size();
      }
      return size;
    }

    int height() {
      int hl = -1;
      int hr = -1;
      if (left != null) {
        hl = left.height();
      }
      if (right != null) {
        hr = right.height();
      }
      return 1 + Math.max(hl, hr);
    }

    void preorder() {
      System.out.println(info);
      if (left != null) {
        left.preorder();
      }
      if (right != null) {
        right.preorder();
      }
    }

    void inorder() {
      if (left != null) {
        left.inorder();
      }
      System.out.println(info);
      if (right != null) {
        right.inorder();
      }
    }

    void postorder() {
      if (left != null) {
        left.postorder();
      }
      if (right != null) {
        right.postorder();
      }
      System.out.println(info);
    }
  }

  /* ********************************************** */

  public static final int LEFT_SIDE = 0;
  public static final int RIGHT_SIDE = 1;

  protected BNode<E> root;

  public BTree() {
    root = null;
  }

  public BTree(E info) {
    root = new BNode(info);
  }

  public BNode<E> getRoot() {
    return root;
  }

  public void setRoot(BNode<E> root) {
    this.root = root;
  }

  public void insert(BTree<E> tree, int side) throws BTreeException {
    root.insert(tree.getRoot(), side);
  }

  public int size() {
    int size = 0;
    if (root != null) {
      size = root.size();
    }
    return size;
  }

  public int height() {
    int h = -1;
    if (root != null) {
      h = root.height();
    }
    return h;
  }

  public void preorder() {
    if (root != null) {
      root.preorder();
    }
  }

  public void inorder() {
    if (root != null) {
      root.inorder();
    }
  }

  public void postorder() {
    if (root != null) {
      root.postorder();
    }
  }

}

	  

public class BTreeException extends Exception {
  public BTreeException(String mensaje) {
    super(mensaje);
  }
}

	  

Solution

Solutions are here and at the end of the exercercises:

public class TestNumNodes {

  public TestNumNodes() {
  }

  public static void main(String args[]) {
    BTree tree;
    try {
      tree = new BTree("Tres");
      BTree subarbol = new BTree("tristes");
      tree.insert(subarbol, BTree.LEFT_SIDE);
      BTree temporal = new BTree("tigres");
      tree.insert(temporal, BTree.RIGHT_SIDE);
      temporal = new BTree("com\355an");
      subarbol.insert(temporal, BTree.LEFT_SIDE);
      temporal = new BTree("trigo");
      subarbol.insert(temporal, BTree.RIGHT_SIDE);
    } catch (BTreeException ex) {
      System.out.println(ex.getMessage());
      return;
    }
    System.out.println("------------------");
    System.out.println((new StringBuilder())
        .append("Num Nodos Arbol Binario = ").append(tree.size()).toString());
    System.out.println("------------------");
  }
}
	  

Solution

Solutions are here and at the end of the exercercises:

public class TongueTwister {

  public static void main(String args[]) {
    BTree<String> tongueTwister;
    BTree.BNode<String> subtree, tmp;

    try {
      tongueTwister = new BTree<String>("Tres");

      subtree = new BTree.BNode<String>("tristes");
      tongueTwister.getRoot().insert(subtree, BTree.LEFT_SIDE);
      tmp = new BTree.BNode<String>("tigres");
      tongueTwister.getRoot().insert(tmp, BTree.RIGHT_SIDE);
      tmp = new BTree.BNode<String>("comian");
      subtree.insert(tmp, BTree.LEFT_SIDE);
      tmp = new BTree.BNode<String>("trigo");
      subtree.insert(tmp, BTree.RIGHT_SIDE);

    } catch (BTreeException ex) {
      System.out.println(ex.getMessage());
      return;
    }

    tongueTwister.preorder();
    System.out.println("------------------");
    tongueTwister.inorder();
    System.out.println("------------------");
    tongueTwister.postorder();

    System.out.println("------------------");
    System.out.println("------------------");

    try {
      subtree = tongueTwister.getRoot().getLeft().extract(BTree.LEFT_SIDE);
      tongueTwister.getRoot().getRight().insert(subtree, BTree.LEFT_SIDE);

      subtree = tongueTwister.getRoot().getLeft().extract(BTree.RIGHT_SIDE);
      tongueTwister.getRoot().getRight().insert(subtree, BTree.RIGHT_SIDE);

      tongueTwister.preorder();

    } catch (BTreeException ex) {
      System.out.println(ex.getMessage());
    }

  }
}

	  

Solution

Note

The class object that implements a stack is that provided by the JDK (java.util.Stack) and the methods to stack and unstack data are declared as follows:

public Object push(Object item); // Stack data on top of the stack

public Object pop(); // Unstack data from the top of the stack

Solutions

Solutions are included in the following listings:

public interface Operator {

  public static final char SUM = '+';
  public static final char SUBTRACTION = '-';
  public static final char PRODUCT = '*';
  public static final char DIVISION = '/';

}

	  

import java.util.Hashtable;
import java.util.Stack;

class Node {

  char value = '\0'; // The character (either an operand or a operator)

  Node left = null; // The reference to the left child node of the binary tree
  Node right = null; // The reference to the right child node of the binary tree

  public Node() {
  }

  public Node(char value, Node left, Node right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  public Node(char value) {
    this(value, null, null);
  }

  public void processNode(Hashtable values, Stack stackResults)
      throws Exception {
    // This recursive method realizes a postorder tree traversal to process the
    // node
    // Firstly, we process the left node recursively
    if (left != null) {
      left.processNode(values, stackResults);
    }

    // Secondly, we process the right node recursively
    if (right != null) {
      right.processNode(values, stackResults);
    }

    // In the other case, we process the actual node
    float result = 0;
    // Depending on the Node's value that indicates the corresponding opperation
    // the result value is calculated.
    switch (value) {
    case Operator.SUM:
      result = (Float) stackResults.pop() + (Float) stackResults.pop();
      break;

    case Operator.SUBTRACTION:
      float subtrahend = (Float) stackResults.pop();
      float minuend = (Float) stackResults.pop();
      result = minuend - subtrahend;
      break;

    case Operator.PRODUCT:
      result = (Float) stackResults.pop() * (Float) stackResults.pop();
      break;

    case Operator.DIVISION:
      float divisor = (Float) stackResults.pop();
      float dividend = (Float) stackResults.pop();
      result = dividend / divisor;
      break;

    default:
      result = (Integer) (values.get(value));
    }

    // And finally, we store the result at the results' stack
    stackResults.push(result);

  }

}

	  

import java.util.Stack;
import java.util.Hashtable;

public class PostfixExprEvaluator implements Operator {

  Node postfixASTTree = null; // The node of the AST postfix expression tree.

  Stack stackNodes = null; // Auxiliary stack to store the nodes of the AST tree
  Stack stackResults = null; // Auxiliary stack to store the intermediate
                             // results

  public PostfixExprEvaluator(String sPostfix) throws Exception {

    // Create the AST Tree from the postfix expression
    postfixASTTree = createPostfixTree(sPostfix);
  }

  private Node createPostfixTree(String sPostfix) throws Exception {

    int i = 0;
    stackNodes = new Stack();

    // while there are tokens(char) left to analyze
    while (i < sPostfix.length()) {

      // Evaluate the token (char)
      char token = sPostfix.charAt(i++);

      switch (token) {
      // If it is an operator
      case Operator.SUM:
      case Operator.PRODUCT:
      case Operator.SUBTRACTION:
      case Operator.DIVISION:

        // Popping the two operands
        Node leftOperand = (Node) stackNodes.pop();
        Node rightOperand = (Node) stackNodes.pop();

        // Create a new Binary Tree Node
        Node binaryOperation = new Node(token, rightOperand, leftOperand);

        // Push it on the stack
        stackNodes.push(binaryOperation);
        break;
      // If it is an operand
      default:
        // Push the new node on the stack
        Node operand = new Node(token);

        stackNodes.push(operand);
      }
    }

    // Finally, we return the first Node of the stack.
    return (Node) stackNodes.pop();

  }

  public float evaluateExpression(String expression, Hashtable values)
      throws Exception {

    // Expression's result
    float result = 0;
    // The results' stack
    stackResults = new Stack();

    // Create a Binary Tree with the postfix expression
    postfixASTTree = createPostfixTree(expression);

    // Traverse the tree to calculate the intermediate results
    postfixASTTree.processNode(values, stackResults);

    // The result value to be returned is located on top of the results' stack
    result = (Float) stackResults.pop();

    return result;
  }

  public static void main(String args[]) throws Exception {

    Hashtable values = new Hashtable();
    values.put('a', 2);
    values.put('b', 5);
    values.put('c', 3);
    values.put('d', 1);

    String sPostfix = "abc*-d+";

    PostfixExprEvaluator myExpression = new PostfixExprEvaluator(sPostfix);

    System.out.println(" Evaluating postfix expression '" + sPostfix
        + "' with values: " + values);

    System.out.println(" Result = "
        + myExpression.evaluateExpression(sPostfix, values));

  }

}