二叉查找树是以一种特殊的二叉树。它的特征是，没一个节点左子树中结点的值都小于该结点的值，右子树中结点的值都大于该结点的值。
二叉查找树的主要操作就是插入元素、删除元素、遍历元素。
插入元素：如果二叉树是空的，使用新元素创建一个根节点；否则，为新元素寻找父节点。如果新元素的值小于父节点的值，则将新元素的结点设置为父节点的左孩子；否则，将其设为右孩子。
遍历元素：遍历主要有中序、前序、后序、深度优先、广度优先等。
下面这个类包括了结点的定义还有二叉树的定义。
package binaryTree;
public class BinaryTree {
// 节点的定义private static class TreeNode {Object element;TreeNode left;TreeNode right;
public TreeNode(Object o) {element = o;}}
private TreeNode root;private int size = 0;
public BinaryTree() {
}
public BinaryTree(Object[] objects) {for (int i = 0; i < objects.length; i++) {insert(objects[i]);}}
public boolean insert(Object o) {if (root == null) {root = new TreeNode(o);} else {TreeNode parent = null;TreeNode current = root;while (current != null) {if (((Comparable) pareTo(current.element) < 0) {parent = current;current = current.left;} else if (((Comparable) pareTo(current.element) > 0) {parent = current;current = current.right;} else {return false;}}if (((Comparable) pareTo(parent.element) < 0) {parent.left = new TreeNode(o);} else {parent.right = new TreeNode(o);}}size++;return true;}
//中序遍历public void inorder(){inorder(root);}public void inorder(TreeNode root){if (root == null) {return;}inorder(root.left);System.out.println(root.element + ” “);inorder(root.right);}//后序遍历public void postorder(){postorder(root);}public void postorder(TreeNode root){if (root == null) {return;}postorder(root.left);postorder(root.right);System.out.println(root.element +” “);}//前序遍历public void preorder(){preorder(root);}public void preorder(TreeNode root){if (root == null) {return;}System.out.println(root.element + ” “);preorder(root.left);preorder(root.right);}public int getSize(){return size;}}
测试类：
package binaryTree;
public class TestBinaryTree {public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(“a”);tree.insert(“b”);tree.insert(“c”);tree.insert(“d”);tree.insert(“e”);tree.insert(“f”);tree.insert(“g”);System.out.println(“Inorder (sorted): “);tree.inorder();System.out.println(“postorder: “);tree.postorder();System.out.println(“preorder: “);tree.preorder();System.out.println(“the number of nodes is ” + tree.getSize());}
}
堆是一种在设计有效的排序算法和优先队列时有用的数据结构。堆是一个完全二叉树，并且它的每个结点都大于等于它的任何孩子结点。由于堆是二叉树，因此可以用二叉树数据结构来表示堆。然而，如果预先不知道堆的大小，一个更有效的表示是用数组或数组线性表。
对于位置i处的结点，它的左孩子位于2i+1处，右孩子位于2i+2处，它的父亲结点位于(i-1)/2处。
删除根结点。删除根节点之后要保持堆的特性，就需要一个算法了。
Move the last node to replace the root; Let the root be the current node; while(the current node has children and the current node is smaller than one of its children){ Swap the current node with the larger of its children; Now the current node is one level down; }
添加一个新结点的算法是：
<STRONG> </STRONG>Let the last node be the current node; while(the current node is greater than its parent){ Swap the current node with its parent; Now the current node is one level up; }
下面设计和实现Heap类。
package heap;
import java.util.ArrayList;
public class Heap {private ArrayList list = new ArrayList();
public Heap() {
}
public Heap(Object[] objects) {for (int i = 0; i < objects.length; i++) {add(objects[i]);}}
public void add(Object newObject) {list.add(newObject);//the index of the last nodeint currentIndex = list.size() – 1;
while (currentIndex > 0) {//计算父节点的indexint parentIndex = (currentIndex – 1) / 2;//如果当前节点大于他的父节点就交换if (((Comparable) (list.get(currentIndex))pareTo(list.get(parentIndex)) > 0) {Object temp = list.get(currentIndex);list.set(currentIndex, list.get(parentIndex));list.set(parentIndex, temp);} else {break;}currentIndex = parentIndex;}}
/** * remove the root from the heap * * @return */public Object remove() {if (list.size() == 0) {return null;}//被删除的节点—根节点Object removedObject = list.get(0);//将最后一个移动到根节点list.set(0, list.get(list.size() – 1));list.remove(list.size() – 1);int currentIndex = 0;while (currentIndex < list.size()) {//计算当前节点的左节点和右节点int leftChildIndex = 2 * currentIndex + 1;int rightChileIndex = 2 * currentIndex + 2;//找到两个子节点中最大的节点if (leftChildIndex >= list.size()) {break;}int maxIndex = leftChildIndex;if (rightChileIndex < list.size()) {if (((Comparable) (list.get(maxIndex))pareTo(list.get(rightChileIndex)) < 0) {maxIndex = rightChileIndex;}}
//如果当前节点小于子节点的最大值就交换if (((Comparable) (list.get(currentIndex))pareTo(list.get(maxIndex)) < 0) {Object temp = list.get(maxIndex);list.set(maxIndex, list.get(currentIndex));list.set(currentIndex, temp);currentIndex = maxIndex;} else {break;}}return removedObject;}
public int getSize() {return list.size();}
}
测试类：
package heap;
public class TestHeap {public static void main(String[] args) {Heap heap = new Heap(new Integer[] { 8, 9, 2, 4, 5, 6, 7, 5, 3, 0 });while (heap.getSize() > 0) {System.out.println(heap.remove() + ” “);}}}
优先队列中，元素都赋予了优先级。当访问元素的时候，具有最高优先级的元素最先移除。优先队列具有最高进先出的特性。可以使用堆来实现队列优先。
package priorityQueue;
import heap.Heap;
public class MyPriorityQueue {private Heap heap = new Heap();
public void enqueue(Object newObject) {heap.add(newObject);}
public Object dequeue() {return heap.remove();}
public int getSize() {return heap.getSize();}
}
测试类：
package priorityQueue;
public class TestPriorityQueue {public static void main(String[] args) {Patient patient1 = new Patient(“john”, 2);Patient patient2 = new Patient(“slmile”, 0);Patient patient3 = new Patient(“dohn”, 5);Patient patient4 = new Patient(“jack”, 3);Patient patient5 = new Patient(“sen”, 7);
MyPriorityQueue priorityQueue = new MyPriorityQueue();priorityQueue.enqueue(patient1);priorityQueue.enqueue(patient2);priorityQueue.enqueue(patient3);priorityQueue.enqueue(patient4);priorityQueue.enqueue(patient5);
while (priorityQueue.getSize() > 0) {System.out.println(priorityQueue.dequeue() + ” “);}}
}
class Patient implements Comparable {private String name;private int priority;
public Patient(String name, int priority) {this.name = name;this.priority = priority;}
public String toString() {return name + “(priority: ” + priority + “)”;}
public int compareTo(Object o) {return this.priority – ((Patient) o).priority;}}
那段岁月，无论从何种角度读你，你都完美无缺，
