linkedbinarytree.java

用java实现的LinkedList二叉树

/*
 * Created on 2005-10-27
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package linkedBinaryTree;

//import java.lang.Math.*;

//import com.sun.org.apache.bcel.internal.generic.RETURN;

/**
 * @author dieks
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class LinkedBinaryTree implements BinaryTree {

	private BTNode root;

	private int size;

	public LinkedBinaryTree() {
		root = null;
		size = 0;
	}

	//tree    
	public Position root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree is empty.");
		return root;
	}

	public boolean isInternal(Position p) throws InvalidPositionException {
		BTNode node = checkPosition(p);
		return (node.getLeft() == null) && (node.getRight() == null);
	}

	public boolean isExternal(Position p) throws InvalidPositionException {
		BTNode node = checkPosition(p);
		return (node.getLeft() == null) && (node.getRight() == null);
	}

	public boolean isRoot(Position p) throws InvalidPositionException {
		BTNode node = checkPosition(p);
		return (node == root());
	}

	public Object replace(Position p, Object e) throws InvalidPositionException {
		BTNode node = checkPosition(p);
		Object temp = node.element();
		node.setElement(e);
		return temp;
	}

	public BTNode createNode(BTNode parent, BTNode left, BTNode right, Object e) {
		return new BTNode(parent, left, right, e);
	}

	public Position addRoot(Object e) throws NonEmptyTreeException {
		if (!isEmpty())
			throw new NonEmptyTreeException("Tree already has a root.");
		size = 1;
		root = createNode(null, null, null, e);
		return root;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return (size == 0);
	}

	public boolean hasLeft(Position p) {
		BTNode node = checkPosition(p);
		return (node.getLeft() != null);
	}

	public boolean hasRight(Position p) {
		BTNode node = checkPosition(p);
		return (node.getRight() != null);
	}

	//	height and depth	
	public static int depth(Tree t, Position p) {
		if (t.isRoot(p))
			return 0;
		else
			return 1 + depth(t, t.parent(p));
	}

	public static int treeHeight(Tree t) {
		return height(t, t.root());
	}

	public static int height(Tree t, Position p) {
		if (t.isExternal(p))
			return 0;
		else {
			int h = 0;
			Iterator c = t.children(p);
			while (c.hasNext()) {
				Position child = (Position) c.nextIterator();
				h = Math.max(h, height(t, child));
			}
			return 1 + h;
		}
	}

	//BinaryTree
	public Position leftChild(Position p) throws InvalidPositionException,
			BoundaryViolationException {

		BTNode node = (BTNode) p;
		node = node.getLeft();
		if (node == null)
			throw new BoundaryViolationException("No left child.");
		return (Position) node;
	}

	public Position rightChild(Position p) throws InvalidPositionException,
			BoundaryViolationException {

		BTNode node = (BTNode) p;
		node = node.getRight();
		if (node == null)
			throw new BoundaryViolationException("No right child.");
		return (Position) node;
	}

	public Position sibling(Position p) throws InvalidPositionException,
			BoundaryViolationException {

		BTNode node = checkPosition(p);
		BTNode parent = node.getParent();
		if (parent != null) {
			BTNode btn;
			BTNode left = parent.getLeft();
			if (left == node)
				btn = parent.getRight();
			else
				btn = parent.getLeft();
			if (btn != null)
				return (Position) btn;
		}
		throw new BoundaryViolationException("No sibling.");
	}

	public Position parent(Position p) throws InvalidPositionException,
			BoundaryViolationException {

		BTNode node = checkPosition(p);
		node = node.getParent();
		if (node == null)
			throw new BoundaryViolationException("No parent.");
		return (Position) node;
	}

	public void expandExternal(Position p, Object left, Object right)
			throws InvalidPositionException {
		if (!isExternal(p))
			throw new InvalidPositionException("Position is not external");
		BTNode node = checkPosition(p);
		node.setLeft(new BTNode(node, null, null, left));
		node.setRight(new BTNode(node, null, null, right));
		size += 2;
	}

	public Position insertLeft(Position p, Object e)
			throws InvalidPositionException {
		BTNode node = checkPosition(p);
		Position left = node.getLeft();
		if (left != null)
			throw new InvalidPositionException("Node already has a left child.");
		BTNode newNode = createNode(node, null, null, e);
		node.setLeft(newNode);
		size++;
		return newNode;
	}

	public Position insertRight(Position p, Object e)
			throws InvalidPositionException {
		BTNode node = checkPosition(p);
		Position right = node.getRight();
		if (right != null)
			throw new InvalidPositionException(
					"Node already has a right child.");
		BTNode newNode = createNode(node, null, null, e);
		node.setRight(newNode);
		size++;
		return newNode;
	}

	public Object remove(Position p) throws InvalidPositionException {
		BTNode node = checkPosition(p);
		BTNode left = node.getLeft();
		BTNode right = node.getRight();
		if (left != null && right != null)
			throw new InvalidPositionException(
					"Cannot remove node with two kids.");
		BTNode child;
		if (left != null)
			child = left;
		else if (right != null)
			child = right;
		else
			child = null;
		if (node == root) {
			if (child != null)
				child.setParent(null);
			root = child;
		} else {
			BTNode parent = node.getParent();
			if (node == parent.getLeft())
				parent.setLeft(child);
			else
				parent.setRight(child);
			if (child != null)
				node.setParent(parent);
		}
		size--;
		return p.element();
	}

	public void attach(Position p, BinaryTree t1, BinaryTree t2)
			throws InvalidPositionException {
		BTNode node = checkPosition(p);
		if (isInternal(p))
			throw new InvalidPositionException(
					"Cannot attach from internal node.");
		if (!t1.isEmpty()) {
			BTNode p1 = checkPosition(t1.root());
			node.setLeft(p1);
			p1.setParent(node);
		}
		if (!t2.isEmpty()) {
			BTNode p2 = checkPosition(t2.root());
			node.setRight(p2);
			p2.setParent(node);
		}
	}

	public Iterator positions() {
		NodeList nodelist = new NodeList();
		if (size != 0)
			//preOrder(root(), nodelist);
			//postOrder(root(), nodelist);
			//inOrder(root(), nodelist);
			eulerOrder(root(), nodelist);
		return (Iterator) new NodeListIterator(nodelist);
	}

	public Iterator elements() {
		NodeList nodelist = new NodeList();

		Iterator c = positions();
		while (c.hasNext()) {
			Position child = (Position) c.nextIterator();
			nodelist.insertLast(child.element());
		}
		return (Iterator) new NodeListIterator(nodelist);
	}

	public Iterator children(Position p) throws InvalidPositionException {
		BTNode node = checkPosition(p);
		NodeList nodelist = new NodeList();
		if (hasLeft(node)) {
			nodelist.insertLast(node.getLeft());
		}

		if (hasRight(node)) {
			nodelist.insertLast(node.getRight());
		}	
		return (Iterator) new NodeListIterator(nodelist);
	}

	public void preOrder(Position p, NodeList nodes)
			throws InvalidPositionException {
		
		nodes.insertLast(p);
		
		if (hasLeft(p))
			preOrder(leftChild(p), nodes);
		if (hasRight(p))
			preOrder(rightChild(p), nodes);
	}

	public void postOrder(Position p, NodeList nodes) {
		
		if (hasLeft(p))
			postOrder(leftChild(p), nodes);
		if (hasRight(p))
			postOrder(rightChild(p), nodes);
		nodes.insertLast(p);
	}

	
	public void inOrder(Position p, NodeList nodes) {
		
		if (hasLeft(p))
			inOrder(leftChild(p), nodes);
		nodes.insertLast(p);
		if (hasRight(p))
			inOrder(rightChild(p), nodes);
	}

	
	public void eulerOrder(Position p, NodeList nodes) {
		nodes.insertLast(p);
		if (hasLeft(p)){
			eulerOrder(leftChild(p), nodes);
			nodes.insertLast(p);
		}
		if (hasRight(p)){
			eulerOrder(rightChild(p), nodes);
			nodes.insertLast(p);
		}
	}

	//	checkPosition	
	public BTNode checkPosition(Position p) throws InvalidPositionException {
		if (p == null || !(p instanceof BTNode))
			throw new InvalidPositionException("The position is invalid");
		return (BTNode) p;
	}

	
	public void printTree() {

		System.out.println("The tree in EulerOrder is: ");
		Iterator elements = elements();
		while (elements.hasNext()) {
			System.out.print(elements.nextIterator().toString() + " ");
		}
		
	}
}