用java实现二叉查找树、堆和优先队列

　　测试类：

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;
    }