binarytree.java

binary tree.java 二叉树的 java 实现

package chapter3;

import java.util.Stack;

public class BinarySearchTree {
 public static class BinaryNode {
  BinaryNode(Object element) {
   this(element, null, null);
  }

 

  BinaryNode(Object element, BinaryNode left, BinaryNode right) {
   this.element = element;
   this.left = left;
   this.right = right;
  }

  Object element;

  BinaryNode left;

  BinaryNode right;

 }

 

 private BinaryNode root = null;

 public BinaryNode getRoot() {
  return root;
 }

 

 public void setRoot(BinaryNode t) {
  root = t;
 }

 

 public BinarySearchTree() {
  root = null;
 }

 

 public void makeEmpty() {
  clear(root);
 }

 

 public boolean isEmpty() {
  return root == null;
 }

 

 public boolean contains(Integer o) {
  return contains(o, root);
 }

 

 private boolean contains(Integer o, BinaryNode t) {
  if (t == null)
   return false;
  int compare = o.compareTo((Integer) t.element);
  if (compare < 0)
   return contains(o, t.left);
  else if (compare > 0)
   return contains(o, t.right);
  else
   return true;
 }

 

 public Integer findMin() throws UnderflowException {
  if (isEmpty())
   throw new UnderflowException();
  return (Integer) findMin(root).element;
 }

 

 private BinaryNode findMin(BinaryNode t) {
  if (t == null)
   return null;
  else if (t.left == null)
   return t;
  else
   return findMin(t.left);
 }

 

 public Integer findMax() throws UnderflowException {
  if (isEmpty())
   throw new UnderflowException();
  return (Integer) findMax(root).element;
 }

 

 private BinaryNode findMax(BinaryNode t) {
  if (t == null)
   return null;
  else {
   while (t.right != null)
    t = t.right;
   return t;
  }
 }

 

 public void insert(Integer x) {
  root = insert(x, root);
 }

 

 private BinaryNode insert(Integer x, BinaryNode t) {
  if (t == null)
   return new BinaryNode(x);
  int compare = x.compareTo((Integer) t.element);
  if (compare < 0)
   t.left = insert(x, t.left);
  else if (compare > 0)
   t.right = insert(x, t.right);
  else
   ;
  return t;
 }

 

 public void remove(Integer x) {
  root = remove(x, root);
 }

 

 private BinaryNode remove(Object object, BinaryNode t) {
  if (t == null)
   return null;
  int compare = ((Integer) object).compareTo((Integer) t.element);
  if (compare < 0)
   t.left = remove(object, t.left);
  else if (compare > 0)
   t.right = remove(object, t.right);
  else if (t.left != null && t.right != null) {
   t.element = findMin(t.right).element;
   t.right = remove(t.element, t.right);
  } else
   t = (t.left != null) ? t.left : t.right;
  return t;
 }

 

 public BinaryNode postorderDisplay(BinaryNode t) {
  if (t == null)
   return null;
  else {
   // postorder
   t.left = postorderDisplay(t.left);
   t.right = postorderDisplay(t.right);
   System.out.print(t.element + " ");
   return t;
  }

 }

 

 public BinaryNode preorderDisplay(BinaryNode t) {
  if (t == null)
   return null;
  else {
   // preorder
   System.out.print(t.element + " ");
   t.left = preorderDisplay(t.left);
   t.right = preorderDisplay(t.right);
   return t;
  }
 }

 

 public BinaryNode inorderDisplay(BinaryNode t) {
  if (t == null)
   return null;
  else {
   // 这是典型的inorder打印
   t.left = inorderDisplay(t.left);
   System.out.print(t.element + " ");
   t.right = inorderDisplay(t.right);
   //当所有t这一级的内容全部扫描完时，将t返回让上一级递归调用
   return t;
  }
 }

 

 

 // 用递归计算一棵树的高度
 public int height(BinaryNode t) {
  int left, right, val;
  if (t == null)
   val = -1;
  else {
   left = height(t.left);
   right = height(t.right);
   val = 1 + Math.max(left, right);
  }
  return val;
 }

 

 // 该方法可以使新创建的实例从其他树中复制内容
 public BinaryNode copyTree(BinaryNode t) {
  // 由于对于复制，结点总是从下至上复制才不会导致引用错误，所以采用postorder的方法复制值
  // 继续递归...

  // 如果传进来的根为null。啥也不干
  if (t == null)
   return null;

  BinaryNode newLeft, newRight, newNode;
  newLeft = copyTree(t.left);
  newRight = copyTree(t.right);
  newNode = new BinaryNode(t.element, newLeft, newRight);
  return newNode;
 }

 

 

 private void clear(BinaryNode t) {
  if (t != null) {
   clear(t.left);
   clear(t.right);
   t = null;
  }
 }

 

//利用后缀表达式来建树

 public static BinaryNode buildExpTree(String string) {
  BinaryNode newNode, left, right;
  Stack<BinaryNode> stack = new Stack<BinaryNode>();
  char token;
  int i = 0, n = string.length();
  while (i != n) {
   while (string.charAt(i) == ' ' || string.charAt(i) == '\t')
    i++;
   if (i == n)
    break;
   token = string.charAt(i);
   i++;
   if (token == '+' || token == '-' || token == '*' || token == '/') {
    right = (BinaryNode) stack.pop();
    left = (BinaryNode) stack.pop();
    newNode = new BinaryNode(new Character(token), left, right);
    stack.push(newNode);
   } 

 

else {
    newNode = new BinaryNode(new Character(token));
    stack.push(newNode);
   }
  }
  if (!stack.isEmpty())
   return (BinaryNode) stack.pop();
  else
   return null;
 }
}