代码如下,无法删除 根,有时也无法删除节点.请高手帮帮忙,这是我的毕业设计,小弟不胜感激.

//Dynamic maintainence of an AVL tree
//This solution is due to Gian Gao, who took the course in Winter 2001
//The program does not work correctly
//The GUI should be separated from the rest of the program
//Modified, commented by Asish Mukhopadhyay, 12 Nov, 2004

import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.awt.event.*;

public class lab9 extends JFrame{
private DrawPanel drawArea;
private BinarySearchTree t;
private JTextField insertNode;
private JTextField deleteNode;
private JButton rebalance;
private BinaryNode binaryNode;
private MyInteger target;
//throws ItemNotFound
private BinaryNode q;
private int caseNum;
private boolean insertFlag=true;
private int difference;
BinaryNode position;

public lab9()
{
super("0360-254 Lab 9, Fall 04");
Container c=getContentPane();
drawArea=new DrawPanel();
t=new BinarySearchTree( );

//for testing
// need to be commented later

//x1.left=new BinaryNode(new MyInteger(3),null,null,null);
//x1.right=new BinaryNode(new MyInteger(9),null,null,null);
//x1.right.right=new BinaryNode(new MyInteger(7),null,null,null);
t.root=null;
//for tesing



//
JLabel promptInsertNode=new JLabel("Insert Node");
insertNode=new JTextField(6);

insertNode.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e)
{
// BinaryNode position=null;
target=new MyInteger(Integer.parseInt(insertNode.getText()));
// quan
try{position=t.insert(target);}//quan
catch(DuplicateItem ex){}
insertNode.setText("");

drawArea.drawTree(t);
}
}
);

JLabel promptDeleteNode=new JLabel("Delete Node");
deleteNode=new JTextField(6);

deleteNode.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e)
{
//BinaryNode position=null;
target= new MyInteger(Integer.parseInt(deleteNode.getText()));
try{position=t.remove(target);}
catch(ItemNotFound ex){}
deleteNode.setText("");

drawArea.drawTree(t);
}

}
);

rebalance=new JButton("Rebalance");
//rebalance.setEnabled(false);

rebalance.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e)
{
t.rebalance();

drawArea.drawTree(t);
JOptionPane.showMessageDialog(null, "The AVL tree is rebalanced");
insertNode.setEnabled(true);
deleteNode.setEnabled(true);
//rebalance.setEnabled(false);
}
}
);

JPanel inputBar=new JPanel(new FlowLayout());
inputBar.add(promptInsertNode);
inputBar.add(insertNode);
inputBar.add(promptDeleteNode);
inputBar.add(deleteNode);
inputBar.add(rebalance);

c.add(inputBar, BorderLayout.NORTH);
c.add(drawArea, BorderLayout.CENTER);

setSize(1024, 800);
show();
}






public static void main(String args[])
{
lab9 apl=new lab9();

apl.addWindowListener(
new WindowAdapter()
{
public void windowClosing(WindowEvent e)
{
System.exit(0);
}
}
);
}
}



class DrawPanel extends JPanel{
private Node nodes[];
private Edge edges[];
private Vector nodeVector;
private Vector edgeVector;
private final int space=20;
private int x;
private int y;
private int xOffset;
private int yOffset;
private Pair originalPosition[];

public DrawPanel()
{
nodes=null;
edges=null;
nodeVector=new Vector();
edgeVector=new Vector();
setBackground(Color.black);
setForeground(Color.yellow);

addMouseListener(
new MouseAdapter(){
public void mousePressed(MouseEvent e)
{
x=e.getX();
y=e.getY();

originalPosition=new Pair[nodes.length];
for(int i=0; i<originalPosition.length; i++)
originalPosition[i]=new Pair(nodes[i].x, nodes[i].y);
}

public void mouseReleased(MouseEvent e)
{
xOffset=e.getX()-x;
yOffset=e.getY()-y;

for(int i=0; i<nodes.length; i++)
{
nodes[i].x=originalPosition[i].x+xOffset;
nodes[i].y=originalPosition[i].y+yOffset;
}

repaint();
}
}
);

addMouseMotionListener(
new MouseMotionAdapter(){
public void mouseDragged(MouseEvent e)
{
xOffset=e.getX()-x;
yOffset=e.getY()-y;

for(int i=0; i<nodes.length; i++)
{
nodes[i].x=originalPosition[i].x+xOffset;
nodes[i].y=originalPosition[i].y+yOffset;
}

repaint();
}
}
);
}

public void drawTree( BinarySearchTree tree )
{
creatNodeAndEdge(tree.getRoot(), BinaryNode.height(tree.getRoot()), this.getWidth()/2, 15);
nodes=new Node[nodeVector.size()];
for(int i=0; i<nodes.length; i++)
nodes[i]=(Node)nodeVector.elementAt(i);
edges=new Edge[edgeVector.size()];
for(int i=0; i<edges.length; i++)
edges[i]=(Edge)edgeVector.elementAt(i);
repaint();
}

private void creatNodeAndEdge( BinaryNode root, int h, int x, int y)
{
//if(root.element==null)
if(root==null){
////added
nodeVector.clear();
edgeVector.clear();
return;
}

nodeVector.clear();
edgeVector.clear();
Node newNode=new Node(x, y, root.element.toString());
nodeVector.addElement(newNode);
creatNodeAndEdgeLeft(root.left, newNode, space*(int)(Math.pow(2, h-1)));
creatNodeAndEdgeRight(root.right, newNode, space*(int)(Math.pow(2, h-1)));
}

private void creatNodeAndEdgeLeft( BinaryNode left, Node parent, int s)
{
if(left==null)
return;
Node newNode=new Node(parent.x-s/2, parent.y+80, left.element.toString());
nodeVector.addElement(newNode);
Edge newEdge=new Edge(parent, newNode);
edgeVector.addElement(newEdge);
creatNodeAndEdgeLeft(left.left, newNode, s/2);
creatNodeAndEdgeRight(left.right, newNode, s/2);
}

private void creatNodeAndEdgeRight( BinaryNode right, Node parent, int s)
{
if(right==null)
return;
Node newNode=new Node(parent.x+s/2, parent.y+80, right.element.toString());
nodeVector.addElement(newNode);
Edge newEdge=new Edge(parent, newNode);
edgeVector.addElement(newEdge);
creatNodeAndEdgeLeft(right.left, newNode, s/2);
creatNodeAndEdgeRight(right.right, newNode, s/2);
}

public void paintComponent( Graphics g )
{
super.paintComponent( g );
if(nodes==null && edges== null)
return;
g.setColor( getForeground() );

for (int i=0; i<nodes.length; i++)
{
g.fillOval( nodes[i].x-Node.DIAMETER/2, nodes[i].y-Node.DIAMETER/2, Node.DIAMETER, Node.DIAMETER );
g.setColor(Color.red);
g.drawString(nodes[i].tag, nodes[i].x - Node.DIAMETER/3, nodes[i].y + Node.DIAMETER/3);
g.setColor( getForeground() );
}

for (int i=0; i<edges.length; i++)
{
g.drawLine( edges[i].start.x, edges[i].start.y, edges[i].end.x, edges[i].end.y );
// what's this part trying to do ?
// generate three points that are connected to form a triangle ?
double mx;
double my;
double px=-1;
double py=-1;
double qx=-1;
double qy=-1;
double rx=-1;
double ry=-1;

if (edges[i].end.x>edges[i].start.x && edges[i].start.y==edges[i].end.y)
{
qx=px=edges[i].end.x-Node.DIAMETER/2-10*Math.cos(Math.PI/6);
py=edges[i].start.y+5;
qy=edges[i].start.y-5;
rx=edges[i].end.x-Node.DIAMETER/2;
ry=edges[i].start.y;
}

else if (edges[i].end.x<edges[i].start.x && edges[i].start.y==edges[i].end.y)
{
qx=px=edges[i].end.x+Node.DIAMETER/2+10*Math.cos(Math.PI/6);
py=edges[i].start.y-5;
qy=edges[i].start.y+5;
rx=edges[i].end.x+Node.DIAMETER/2;
ry=edges[i].start.y;
}

else if (edges[i].end.x==edges[i].start.x && edges[i].start.y<edges[i].end.y)
{
qy=py=edges[i].end.y-Node.DIAMETER/2-10*Math.cos(Math.PI/6);
px=edges[i].start.x-5;
qx=edges[i].start.x+5;
rx=edges[i].start.x;
ry=edges[i].end.y-Node.DIAMETER/2;
}

else if (edges[i].end.x==edges[i].start.x && edges[i].start.y>edges[i].end.y)
{
qy=py=edges[i].end.y+Node.DIAMETER/2+10*Math.cos(Math.PI/6);
px=edges[i].start.x+5;
qx=edges[i].start.x-5;
rx=edges[i].start.x;
ry=edges[i].end.y+Node.DIAMETER/2;
}

else
{
double dy=Math.abs(edges[i].start.y-edges[i].end.y);;
double dx=Math.abs(edges[i].end.x-edges[i].start.x);
double sin=dy/Math.sqrt(dx*dx+dy*dy);
double cos=dx/Math.sqrt(dx*dx+dy*dy);

if (edges[i].start.x<edges[i].end.x && edges[i].start.y<edges[i].end.y)
{
mx=edges[i].end.x-(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*cos;
my=edges[i].end.y-(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*sin;

px=mx-5*sin;
py=my+5*cos;
qx=mx+5*sin;
qy=my-5*cos;
rx=edges[i].end.x-cos*Node.DIAMETER/2;
ry=edges[i].end.y-sin*Node.DIAMETER/2;
}

else if (edges[i].start.x<edges[i].end.x && edges[i].start.y>edges[i].end.y)
{
mx=edges[i].end.x-(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*cos;
my=edges[i].end.y+(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*sin;

px=mx+5*sin;
py=my+5*cos;
qx=mx-5*sin;
qy=my-5*cos;
rx=edges[i].end.x-cos*Node.DIAMETER/2;
ry=edges[i].end.y+sin*Node.DIAMETER/2;
}

else if (edges[i].start.x>edges[i].end.x && edges[i].start.y<edges[i].end.y)
{
mx=edges[i].end.x+(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*cos;
my=edges[i].end.y-(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*sin;

px=mx-5*sin;
py=my-5*cos;
qx=mx+5*sin;
qy=my+5*cos;
rx=edges[i].end.x+cos*Node.DIAMETER/2;
ry=edges[i].end.y-sin*Node.DIAMETER/2;
}

else if (edges[i].start.x>edges[i].end.x && edges[i].start.y>edges[i].end.y)
{
mx=edges[i].end.x+(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*cos;
my=edges[i].end.y+(Node.DIAMETER/2+10*Math.cos(Math.PI/6))*sin;

px=mx+5*sin;
py=my-5*cos;
qx=mx-5*sin;
qy=my+5*cos;
rx=edges[i].end.x+cos*Node.DIAMETER/2;
ry=edges[i].end.y+sin*Node.DIAMETER/2;
}
}
int xPoints[]={(int)px, (int)qx, (int)rx};
int yPoints[]={(int)py, (int)qy, (int)ry};
//drawing a filled-in triangle. What for ?
g.fillPolygon(xPoints, yPoints, 3);
}
}
}

class Node{
String tag;
int x, y;
static int DIAMETER=20;

public Node(int x, int y, String tag)
{
this.x=x;
this.y=y;
this.tag=tag;
}
}

class Edge{
Node start;
Node end;

public Edge(Node start, Node end)
{
this.start=start;
this.end=end;
}
}

class Pair{
int x;
int y;

public Pair(int x, int y)
{
this.x=x;
this.y=y;
}
}


class DuplicateItem extends Exception
{
public DuplicateItem( String message )
{
super( message );
}
}


class ItemNotFound extends Exception
{
public ItemNotFound( String message )
{
super( message );
}
}


final class MyInteger implements Comparable
{
private int value;

public MyInteger( )
{
this( 0 );
}

public MyInteger( int x )
{
value = x;
}

public int getValue( )
{
return value;
}

public String toString( )
{
return Integer.toString( value );
}

public int compares( Comparable rhs )
{
return value < ((MyInteger)rhs).value ? -1 :
value == ((MyInteger)rhs).value ? 0 : 1;
}

public int compareTo( Comparable rhs )
{
return value < ((MyInteger)rhs).value ? -1 :
value == ((MyInteger)rhs).value ? 0 : 1;
}

public boolean lessThan( Comparable rhs )
{
return value < ((MyInteger)rhs).getValue();
}

public boolean equals( Object rhs )
{
return rhs != null && value == ((MyInteger)rhs).value;
}
}



class BinaryNode
{
Comparable element;
BinaryNode left;
BinaryNode right;
BinaryNode parent;
int height;

BinaryNode( Comparable theElement )
{
this( theElement, null, null, null );
}

BinaryNode( Comparable theElement, BinaryNode lt, BinaryNode rt, BinaryNode p )
{
element = theElement;
left = lt;
right = rt;
parent = p;
}

static int height(BinaryNode t)
{
if(t==null)
return -1;
else
return 1+Math.max(height(t.left), height(t.right));
}
}

interface Comparable
{
int compares( Comparable rhs );
boolean lessThan( Comparable rhs );
int compareTo( Comparable rhs );
String toString();
}
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
class BinarySearchTree
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public BinaryNode insert(Comparable e) throws DuplicateItem
{
return root = insert(e, root);
}

public BinaryNode insert( Comparable e , BinaryNode c) throws DuplicateItem
{
if(c == null) //base case
c = new BinaryNode(e); //a new AVLNode with no children
else if(e.compareTo(c.element) < 0)
{
c.left = insert(e, c.left); //insert into left
if(c.height(c.left) - c.height(c.right) == 2) //unbalanced
{JOptionPane.showMessageDialog(null," not balanced at"+c.element);
setunbalance(c);
}
else if(e.compareTo(c.element) > 0)
{
c.right = insert(e, c.right);
if(c.height(c.right) - c.height(c.left) == 2) //unbalanced

}
else // e = c.element, ignore duplicate
{}

c.height = Math.max(c.height(c.left), c.height(c.right)) + 1;

return c;
}


/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public BinaryNode remove(Comparable e) throws ItemNotFound
{
return remove(e, root);
}
public BinaryNode remove( Comparable e , BinaryNode c) throws ItemNotFound
{
if(c == null)
return c;
else if(e.compareTo(c.element) < 0)
{
c.left = remove(e, c.left);
if(c.height(c.right) - c.height(c.left) == 2) //unbalanced

}
else if(e.compareTo(c.element) > 0)
{
c.right = remove(e, c.right);
if(c.height(c.left) - c.height(c.right) == 2) //unbalanced

}
else if(c.left != null && c.right != null) //current Node has two children
{
c.element = findMin(c.right).element;
c.right = remove(c.element, c.right);
if(c.height(c.left) - c.height(c.right) == 2) //unbalanced

}
else //current Node has only one child
c = (c.left != null) ? c.left : c.right;
c.height = Math.max(c.height(c.left), c.height(c.right)) + 1; //update height information

return c;

}

private void setunbalance(BinaryNode n)
{x=n;}


public void rebalance()
{if(checkBalanced(x)==2)
{if(x.height(x.left.left) > x.height(x.left.right))
singleWithLeft(x);
else
doubleWithLeft(x);}
else
{if(x.height(x.right.right) > x.height(x.right.left))
singleWithRight(x);
else
doubleWithRight(x);}

}

public BinaryNode singleWithLeft(BinaryNode t2)
{
BinaryNode t1 = t2.left;
t2.left = t1.right;
t1.right = t2;
t2.height = Math.max(t2.height(t2.left), t2.height(t2.right)) + 1;
t1.height = Math.max(t1.height(t1.left), t1.height(t1.right)) + 1;
return t1;
}

private BinaryNode singleWithRight(BinaryNode t2)
{
BinaryNode t1 = t2.right;
t2.right = t1.left;
t1.left = t2;
t2.height = Math.max(t2.height(t2.left), t2.height(t2.right)) + 1;
t1.height = Math.max(t1.height(t1.left), t1.height(t1.right)) + 1;
return t1;
}

private BinaryNode doubleWithLeft(BinaryNode t3)
{
t3.left = singleWithRight(t3.left);
return singleWithLeft(t3);
}

private BinaryNode doubleWithRight(BinaryNode t3)
{
t3.right = singleWithLeft(t3.right);
return singleWithRight(t3);
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
private int checkBalanced(BinaryNode t)
{
return t.height(t.left) - t.height(t.right);
}

public Comparable findMin( )
{
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public Comparable findMax( )
{
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x )
{
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}

/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode 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 BinaryNode insert( Comparable x, BinaryNode t )
{//need to modify

return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
*/
/*private BinaryNode remove( Comparable x, BinaryNode t )
{//need to modify

return t;
}*/

// Find the successor of a node.
public BinaryNode successor( BinaryNode t)
{
BinaryNode y;
if(t.right != null)
return findMin(t.right);
else {
y = t.parent;
while(y != null && t == y.right)
{
t = y;
y = y.parent;
}
return y;
}
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private BinaryNode findMin( BinaryNode t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t )
{
if( t != null )
while( t.right != null )
t = t.right;

return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
public BinaryNode find( Comparable x, BinaryNode t )
{
if( t == null )
return null;
if( x.compareTo( t.element ) < 0 )
return find( x, t.left );
else if( x.compareTo( t.element ) > 0 )
return find( x, t.right );
else
return t; // Match
}

/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( BinaryNode t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}

// routines inserted by AM

public BinaryNode getRoot()
{
//changed
if (root==null)
return null;
else return this.root;
}

public void setRoot(BinaryNode t)
{
this.root = t;
}

/** The tree root. */
BinaryNode root,x=new BinaryNode(null);
}

补充一下,只有 remove 这个类有问题，insert 还有 GUI的运用都是没有问题的。
期待高手回复

有没有高手帮帮忙啊？谢谢

没人会吗？真沮丧，高手都哪去了