Back

package com.futureshocked.datastructures;

import com.futureshocked.debug.Indenter;

/**
 * Simple implementation of a binary tree - to be used for testing out the
 *   DebuggerClassLoader.
 */
public class BinaryTree {
  /**
   * The root of the binary tree.
   */
  private BinaryNode root;

  public BinaryTree() {
    this(null);
  }

  public BinaryTree(BinaryNode root) {
    this.root = root;
  }

  /**
   * Ordinarily this method shouldn't exist for a binary tree, but this allows
   *   us to create a loop in the binary tree by setting a leave's child to
   *   the root of the tree (to test out the recursion limiter).
   *
   * @return A {@link BinaryNode} object that is the root of the tree.
   */
  public BinaryNode getRoot() {
    return root;
  }

  public void insert(int value) {
    insert(new BinaryNode(value));
  }

  public void insert(BinaryNode node) {
    root = insert(root, node);
  }

  private BinaryNode insert(BinaryNode curNode, BinaryNode newNode) {
    BinaryNode returnNode = curNode;

    if (curNode == null)
      returnNode = newNode;
    else if (curNode.getData() < newNode.getData())
      returnNode.setRightNode(insert(curNode.getRightNode(), newNode));
    else if (curNode.getData() > newNode.getData())
      returnNode.setLeftNode(insert(curNode.getLeftNode(), newNode));
    else
      returnNode = curNode;

    return returnNode;
  }

  public BinaryNode search(int number) {
    return search(root, number);
  }

  private BinaryNode search(BinaryNode curNode, int number) {
    BinaryNode returnNode = null;

    if (curNode != null) {
      if (curNode.getData() > number)
        returnNode = search(curNode.getLeftNode(), number);
      else if (curNode.getData() < number)
        returnNode = search(curNode.getRightNode(), number);
      else
        returnNode = curNode;
    }

    return returnNode;
  }

  public void printTree() {
    printTree(root, 0);
  }

  private void printTree(BinaryNode node, int depth) {
    if (node == null)
      return;

    printTree(node.getRightNode(), depth + 1);
    System.out.println(Indenter.indent(depth) + node.getData());
    printTree(node.getLeftNode(), depth + 1);
  }

  public static void main(String[] args) {
    BinaryTree bt = new BinaryTree();
    if (args.length > 0) {
      try {
        for (int x = 0; x < args.length; x++)
          bt.insert(Integer.parseInt(args[x]));
      } catch (NumberFormatException nfe) {
        nfe.printStackTrace();
      }
    }
    else {
      bt.insert(4);
      bt.insert(2);
      bt.insert(213);
      bt.insert(31);
      bt.insert(12);
      bt.insert(667);
      bt.search(667).setRightNode(bt.getRoot()); //this looks like a bad idea...
      bt.insert(999);
    }

    //bt.printTree();
  }

}

Top