各位大哥，小弟最近在想用AVL树实现priority queue的算法（当然用heap更简单）， 但是对于用AVL树实现deleteMin()的操作，依次删除最小元素，并返回其值，直到删除树的最后一个元素的算法实在想不出来。我知道这其实和插入操作类似，因为删除会破坏平衡，因此需要通过旋转来使树重新平衡，但和插入的过程很不一样，想了几天也没头绪。不知有没有高手可以指点一下，有算法可以分享一下就更好了？下面是我写了一半的程序，插入操作可以正常完成，deleteMin（）就有问题了。非常感谢！：）
- Java code
public class MyHeap implements PriorityQueue { private AVLNode root;//declare the root node //Construct the AVL tree. public MyHeap(){ root = null; } //Insert new item into the AVL tree. public void insert(double x){ root = insert(x, root); } //Remove the minimum item from the tree and return its value. public double deleteMin(){ double temp=elementAt(findMin(root)); deleteMin(root); return temp; } //Find and return the smallest item in the tree and return its value. public double findMin(){ return elementAt(findMin(root)); } /** * Check whether tree is empty or not * return 1-->is empty * return 0-->is not empty */ public boolean isEmpty(){ return root == null; } // Erases all elements from the AVL tree. public void makeEmpty(){ while(root!=null) deleteMin(); } //return the element associate with node t private double elementAt(AVLNode t){ return t == null ? null : t.element; } /** * Internal method to insert into a subtree. * @param x the item to insert. * @param t the node that roots the tree. * @return the new root. */ private AVLNode insert(double x, AVLNode t ){ if( t == null ) return new AVLNode(x,null,null); if(x<t.element){ t.left = insert(x, t.left); if(height(t.left)-height(t.right) == 2 ) if(x<t.left.element) t = rotateLeft(t); else t = doubleRotateLeft(t); } else if(x>t.element){ t.right = insert(x, t.right); if(height(t.right) - height(t.left) == 2) if(x>t.right.element) t = rotateRight(t); else t = doubleRotateRight(t); } else ; // Duplicate; do nothing t.height = Math.max(height(t.left), height(t.right)) + 1; return t; } /** * private method to find the smallest item in the subtree. * @param t the node that roots the tree. */ private AVLNode findMin(AVLNode t){ if(t == null) return null; while(t.left != null) t = t.left; return t; } private AVLNode deleteMin(AVLNode t){ if(t==null) throw new EmptyHeapException(); else if(t.left!=null){ t.left=deleteMin(t.left); if(height(t.right)-height(t.left) == 2 ) t = rotateLeft(t); else t = doubleRotateLeft(t); return t; } else return t.right; } //in-order traverse the AVL tree private void traverse(AVLNode t) { if( t != null ) { traverse(t.left); System.out.println( t.element ); traverse(t.right); } } //Return the height of node t, or -1, if null. private int height(AVLNode t){ return t == null?-1:t.height; } /** * Rotate AVL tree node with left child. * this is a single rotation for case 1. * Update heights, then return new root. */ private AVLNode rotateLeft(AVLNode root) { AVLNode temp = root.left; root.left = temp.right; temp.right = root; root.height = Math.max(height(root.right), height(root.left))+1; temp.height = Math.max(height(temp.right), height(temp.left))+1; root=temp; return root; } /** * Rotate AVL tree node with right child. * this is a single rotation for case 4. * Update heights, then return new root. */ private AVLNode rotateRight(AVLNode root) { AVLNode temp = root.right; root.right = temp.left; temp.left = root; root.height = Math.max(height(root.right), height(root.left))+1; temp.height = Math.max(height(temp.right), height(temp.left))+1; root=temp; return root; } /** * Double rotate AVL tree node: first left child * with its right child; then root with new left child. * this is a double rotation for case 2. * Update heights, then return new root. */ private AVLNode doubleRotateLeft(AVLNode root){ root.left = rotateRight(root.left); return rotateLeft(root); } /** * Double rotate AVL tree node: first right child * with its left child; then root with new right child. * this is a double rotation for case 3. * Update heights, then return new root. */ private AVLNode doubleRotateRight(AVLNode root){ root.right = rotateLeft(root.right); return rotateRight(root); } }/*** AVLNode class used in MyHeap class*@ Liyun Zeng*@ 2-1-09*/class AVLNode{ double element; // The data include in the node AVLNode left; // Left child reference AVLNode right; // Right child reference int height; // Height of this node // Constructors AVLNode(double theElement){ this(theElement, null, null); } AVLNode(double theElement, AVLNode lt, AVLNode rt ){ element = theElement; left = lt; right = rt; height = 0; }}