Universidad Carlos III de Madrid

Nota

Recuerda que se necesitan dos clases, BTree y BNode, para poder modelar adecuadamente el árbol vacío.

Solución

Las soluciones están al final de los ejercicios.

Solución

Las soluciones están al final de los ejercicios.

Solución

Las soluciones están al final de los ejercicios.

Solución

Las soluciones se pueden ver en el siguiente listado:

public class BTree {

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

  static class BNode {

    private Object info;
    private BNode left;
    private BNode right;

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

    BNode(Object info, BNode l, BNode r) {
      this.info = info;
      left = l;
      right = r;
    }

    Object getInfo() {
      return info;
    }

    BNode getLeft() {
      return left;
    }

    BNode getRight() {
      return right;
    }

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

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

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

    void insert(BNode 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 extract(int side) throws BTreeException {
      BNode 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 root;

  public BTree() {
    root = null;
  }

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

  public BNode getRoot() {
    return root;
  }

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

  public void insert(BTree 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);
  }
}

	  

Solución

Las soluciones están aquí y al final de los ejercicios:

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("------------------");
  }
}
	  

Solución

Las soluciones están aquí y al final de los ejercicios:

public class TongueTwister {

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

    try {
      tongueTwister = new BTree("Tres");

      subtree = new BTree.BNode("tristes");
      tongueTwister.getRoot().insert(subtree, BTree.LEFT_SIDE);
      tmp = new BTree.BNode("tigres");
      tongueTwister.getRoot().insert(tmp, BTree.RIGHT_SIDE);
      tmp = new BTree.BNode("comian");
      subtree.insert(tmp, BTree.LEFT_SIDE);
      tmp = new BTree.BNode("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());
    }

  }
}

	  

Solución

Nota

El objeto que implementa una pila es el que se proporciona en el JDK(java.util.Stack) y cuyos métodos para apilar y des-apilar datos se declaran a continuación:

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

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

Soluciones

La soluciones se pueden ver en los siguientes listados:

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));

  }

}