用java实现二叉查找树、堆和优先队列
二叉查找树是以一种特殊的二叉树。它的特征是，没一个节点左子树中结点的值都小于该结点的值，右子树中结点的值都大于该结点的值。
二叉查找树的主要操作是插入元素、删除元素、遍历元素。
插入元素：如果二叉树是空的，使用新元素创建一个根节点；否则，为新元素寻找父节点。如果新元素的值小于父节点的值，则将新元素的结点设置为父节点的左孩子；否则，将其设为右孩子。
遍历元素：遍历主要有中序、前序、后序、深度优先、广度优先等。
下面这个类包括了结点的定义还有二叉树的定义。
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) o).compareTo(current.element) < 0) { parent = current; current = current.left; } else if (((Comparable) o).compareTo(current.element) > 0) { parent = current; current = current.right; } else { return false; } } if (((Comparable) o).compareTo(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 node int currentIndex = list.size() - 1;
while (currentIndex > 0) { //计算父节点的index int parentIndex = (currentIndex - 1) / 2; //如果当前节点大于他的父节点交换 if (((Comparable) (list.get(currentIndex))).compareTo(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))).compareTo(list .get(rightChileIndex)) < 0) { maxIndex = rightChileIndex; } }
//如果当前节点小于子节点的大值交换 if (((Comparable) (list.get(currentIndex))).compareTo(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; } }
