btpanel.java

平衡二叉树 生成

// Source File Name:   BTPanel.java

import java.awt.*;

class BTPanel extends Panel
    implements Runnable
{

    BTPanel(BTApplet btapplet)
    {
        LINECOLOR = Color.darkGray;
        EDGECOLOR = Color.black;
        PICKCOLOR = Color.green;
        FINDCOLOR = ROOTCOLOR;
        sleeptime = 100;
        inverse = true;
        applet = btapplet;
        engine = null;
        tree = new BTTree();
        center = new Point(0, 0);
        treenode = new BTNode();
        picknode = null;
        prevpick = null;
        nextpick = null;
        nextnode = null;
        traversal = 0;
    }

    public void locate(BTData btdata)
    {
        if(tree.root != null)
        {
            treenode.mode = 1;
            treenode.init(btdata);
            treenode.x = tree.root.x;
            treenode.y = 0;
            treenode.X = tree.root.x;
            treenode.Y = tree.root.y;
            nextnode = tree.root;
            applet.playSound(1);
        }
    }

    public void insert(BTData btdata)
    {
    	System.out.println("in insert");
        if(tree.root == null)
        {
            BTNode btnode = tree.insert(btdata);
            btnode.x = center.x;
            btnode.y = 0;
            btnode.X = center.x;
            btnode.Y = center.y;
        } else
        {
        	System.out.println("in insert 1");
            if(treenode.mode == 3)
            {
            	System.out.println("in insert 2");
            	System.out.println("in insert treenode mode = 3");
                nextnode = tree.insert(treenode.data);
                if(nextnode == null)
                {
                    applet.playSound(3);
                } else
                {
                    if(nextnode.parent != null)
                    {
                        nextnode.x = nextnode.parent.x;
                        nextnode.y = nextnode.parent.y;
                    } else
                    {
                        nextnode.x = center.x;
                        nextnode.y = 0;
                    }
                    placeNodes();
                    applet.playSound(2);
                }
            }
            System.out.println("in insert 3");
            treenode.mode = 3;
            treenode.init(btdata);
            treenode.x = tree.root.x;
            treenode.y = 0;
            treenode.X = tree.root.x;
            treenode.Y = tree.root.y;
            nextnode = tree.root;
        }
        System.out.println("in insert 4");
        applet.playSound(1);
    }

    public void traverse(int traversal)
    {
    	this.traversal = traversal;
        if(tree.root == null)
        {
        	return;
        } else
        {
        	treenode.mode = 99;
        	switch(traversal)
        	{
        		case 0:
        			treenode.init(tree.root.lastInO().data);
        			System.out.println("Traverse last: " + tree.root.lastInO().data);
        			nextnode = tree.root.firstInO();
        			System.out.println("Traverse first: " + nextnode.data);
        			break;
        		
        		case 1:
        			treenode.init(tree.root.lastPrO().data);
        			System.out.println("Traverse last: " + tree.root.lastPrO().data);
        			nextnode = tree.root;
        			System.out.println("Traverse first: " + nextnode.data);
        			break;
        		
        		case 2:
        			treenode.init(tree.root.data);
        			nextnode = tree.root.firstPoO();
        			break;
        	}
        	System.out.println("Tree node mode: " + treenode.mode);
        	//treenode.init(tree.root.lastInO().data);
            treenode.x = tree.root.x;
            treenode.y = 0;
            treenode.X = tree.root.x;
            treenode.Y = tree.root.y;
            //nextnode = tree.root.firstInO();
            System.out.println("first one in the tree: " + nextnode.data.key);
            nextnode.mode = 98;
        }

    }
    
    public void remove(BTData btdata)
    {
        if(tree.root != null)
        {
            if(treenode.mode == 5)
            {
                nextnode = tree.remove(treenode.data);
                if(nextnode == null)
                {
                    applet.playSound(3);
                } else
                {
                    placeNodes();
                    applet.playSound(2);
                }
            }
            treenode.mode = 5;
            treenode.init(btdata);
            treenode.x = tree.root.x;
            treenode.y = 0;
            treenode.X = tree.root.x;
            treenode.Y = tree.root.y;
            nextnode = tree.root;
            applet.playSound(1);
        }
    }

    public void delall()
    {
        treenode.mode = 0;
        if(tree.root != null)
            tree.delall();
        placeNodes();
        tree.root = null;

    }

    public void balance()
    {
        treenode.mode = 0;
        BTTree bttree = new BTTree(true);
        bttree.insert(tree);
        tree.delall();
        tree = bttree;
        bttree = null;
        placeNodes();
    }

    public void resetModes()
    {
        for(BTNode btnode = tree.root; btnode != null; btnode = btnode.nextPrO())
            btnode.mode = 0;

    }

    public void resetNodes()
    {
        for(BTNode btnode = tree.root; btnode != null; btnode = btnode.nextPrO())
        {
            btnode.x = btnode.X;
            btnode.y = 0;
        }

    }

    synchronized void moveNodes()
    {
    
        for(BTNode btnode = tree.root; btnode != null; btnode = btnode.nextPrO())
            if(btnode != picknode)
            {
                int i = (btnode.X - btnode.x) / 2;
                int i1 = (btnode.Y - btnode.y) / 2;
                btnode.x = i == 0 ? btnode.X : btnode.x + i;
                btnode.y = i1 == 0 ? btnode.Y : btnode.y + i1;
            }
        
        if(treenode.mode != 0)
            switch(treenode.mode)
            {
            case 2: // '\002'
            default:
                break;

            case 1: // '\001'
                int j = (treenode.X - treenode.x) / 2;
                int j1 = (treenode.Y - treenode.y) / 2;
                treenode.x = j == 0 ? treenode.X : treenode.x + j;
                treenode.y = j1 == 0 ? treenode.Y : treenode.y + j1;
                if(j == 0 && j1 == 0)
                {
                    BTNode btnode1 = nextnode.nextdown(treenode.data);
                    if(btnode1 == nextnode)
                    {
                        treenode.mode = 0;
                        nextnode.mode = 2;
                        applet.playSound(2);
                        return;
                    }
                    if(btnode1 == null)
                    {
                        treenode.mode = 0;
                        applet.playSound(3);
                        return;
                    } else
                    {
                        nextnode = btnode1;
                        treenode.X = nextnode.x;
                        treenode.Y = nextnode.y;
                        applet.playSound(1);
                        return;
                    }
                }
                break;

            case 3: // '\003'
            	//System.out.println("inside moveNodes: " + treenode.data.key);
                int k = (treenode.X - treenode.x) / 2;
                int k1 = (treenode.Y - treenode.y) / 2;
                treenode.x = k == 0 ? treenode.X : treenode.x + k;
                treenode.y = k1 == 0 ? treenode.Y : treenode.y + k1;
                if(k != 0 || k1 != 0)
                    break;
                BTNode btnode2 = nextnode.nextdown(treenode.data);
                if(btnode2 == null)
                {
                    btnode2 = tree.insert(treenode.data);
                    placeNodes();
                    btnode2.x = nextnode.x;
                    btnode2.y = nextnode.y;
                    treenode.mode = 4;
                    btnode2.mode = 3;
                    nextnode = btnode2;
                    applet.playSound(2);
                    System.out.println("inside moveNodes insert: " + treenode.data.key);
                    return;
                }
                if(btnode2 == nextnode)
                {
                    treenode.mode = 0;
                    nextnode.mode = 0;
                    applet.playSound(3);
                    System.out.println("inside moveNodes ==: " + btnode2.data.key);
                    return;
                } else
                {
                    nextnode = btnode2;
                    treenode.X = nextnode.x;
                    treenode.Y = nextnode.y;
                    applet.playSound(1);
                    System.out.println("inside moveNodes: " + btnode2.data.key);
                    return;
                }

            case 4: // '\004'
                if(nextnode.x == nextnode.X && nextnode.y == nextnode.Y)
                {
                    treenode.mode = 0;
                    nextnode.mode = 4;
                    placeNodes();
                    return;
                }
                break;

            case 5: // '\005'
                int l = (treenode.X - treenode.x) / 2;
                int l1 = (treenode.Y - treenode.y) / 2;
                treenode.x = l == 0 ? treenode.X : treenode.x + l;
                treenode.y = l1 == 0 ? treenode.Y : treenode.y + l1;
                if(l != 0 || l1 != 0)
                    break;
                BTNode btnode3 = nextnode.nextdown(treenode.data);
                if(btnode3 == nextnode)
                {
                    treenode.mode = 0;
                    nextnode = tree.remove(treenode.data);
                    nextnode.data = null;
                    nextnode = null;
                    placeNodes();
                    applet.playSound(2);
                    return;
                }
                if(btnode3 == null)
                {
                    treenode.mode = 0;
                    applet.playSound(3);
                    return;
                } else
                {
                    nextnode = btnode3;
                    treenode.X = nextnode.x;
                    treenode.Y = nextnode.y;
                    applet.playSound(1);
                    return;
                }
                
            case 99:
                int m = (treenode.X - treenode.x) / 2;
                int m1 = (treenode.Y - treenode.y) / 2;
                treenode.x = m == 0 ? treenode.X : treenode.x + m;
                treenode.y = m1 == 0 ? treenode.Y : treenode.y + m1;
                if(m == 0 && m1 == 0)
                {
                	BTNode btnode4 = null;
                	switch(traversal)