btnode.java

平衡二叉树 生成

// Source File Name:   BTNode.java


class BTNode
{

    public BTNode()
    {
        parent = null;
        lchild = null;
        rchild = null;
        data = null;
        balance = 0;
        x = X = 0;
        y = Y = 0;
    }

    public BTNode(BTData btdata)
    {
        parent = null;
        lchild = null;
        rchild = null;
        data = btdata;
        balance = 0;
        x = X = 0;
        y = Y = 0;
    }

    public void init(BTData btdata)
    {
        data = btdata;
    }

    public String toString()
    {
        StringBuffer stringbuffer = new StringBuffer();
        stringbuffer.append(super.toString() + ":");
        stringbuffer.append("  data:" + data);
        return stringbuffer.toString();
    }

    public String toString2()
    {
        StringBuffer stringbuffer = new StringBuffer();
        stringbuffer.append(super.toString() + ":\n");
        stringbuffer.append("  data: " + data + "\n");
        stringbuffer.append("  parent: " + parent + "\n");
        stringbuffer.append("  lchild: " + lchild + "\n");
        stringbuffer.append("  rchild: " + rchild + "\n");
        return stringbuffer.toString();
    }

    public String toString3()
    {
        String s = String.valueOf(balance);
        return s;
    }

    public int side()
    {
        BTNode btnode = parent;
        if(btnode != null)
            return this != btnode.lchild ? 1 : -1;
        else
            return 0;
    }

    public BTNode child(int i)
    {
        BTNode btnode;
        if(i == -1)
            btnode = lchild;
        else
        if(i == 1)
            btnode = rchild;
        else
            btnode = this;
        return btnode;
    }

    public void gets_child(BTNode btnode, int i)
    {
        if(i == -1)
            lchild = btnode;
        else
        if(i == 1)
            rchild = btnode;
        if(btnode != null)
            btnode.parent = this;
    }

    public void gets_parent(BTNode btnode, int i)
    {
        parent = btnode;
        if(btnode != null)
        {
            if(i == -1)
            {
                btnode.lchild = this;
                return;
            }
            if(i == 1)
                btnode.rchild = this;
        }
    }

    public void rotate(int i)
    {
        BTNode btnode = this;
        BTNode btnode1 = btnode.child(-i);
        BTNode btnode2 = btnode1.child(i);
        btnode.gets_child(btnode2, -i);
        btnode1.gets_parent(btnode.parent, btnode.side());
        btnode1.gets_child(btnode, i);
    }

    public BTNode nextdown(BTData btdata)
    {
        int i = btdata.compareTo(data);
        return child(i);
    }

    public BTNode firstInO()
    {
        BTNode btnode;
        for(btnode = this; btnode.lchild != null; btnode = btnode.lchild);
        return btnode;
    }

    public BTNode lastInO()
    {
        BTNode btnode;
        for(btnode = this; btnode.rchild != null; btnode = btnode.rchild);
        return btnode;
    }

    public BTNode firstPrO()
    {
        return this;
    }

    public BTNode lastPrO()
    {
        BTNode btnode;
        for(btnode = this; btnode.rchild != null || btnode.lchild != null;)
            if(btnode.rchild != null)
                btnode = btnode.rchild;
            else
                btnode = btnode.lchild;

        return btnode;
    }

    public BTNode firstPoO()
    {
        BTNode btnode;
        BTNode btnode1;
        for(btnode1 = this; (btnode = btnode1.lchild == null ? btnode1.rchild : btnode1.lchild) != null; btnode1 = btnode);
        return btnode1;
    }

    public BTNode nextInO()
    {
        BTNode btnode = this;
        BTNode btnode1 = null;
        if(btnode.rchild != null)
            btnode1 = btnode.rchild.firstInO();
        else
            for(; (btnode1 = btnode.parent) != null && btnode == btnode1.rchild; btnode = btnode1);
        return btnode1;
    }

    public BTNode prevInO()
    {
        BTNode btnode = this;
        BTNode btnode1 = null;
        if(btnode.lchild != null)
            btnode1 = btnode.lchild.lastInO();
        else
            for(; (btnode1 = btnode.parent) != null && btnode == btnode1.lchild; btnode = btnode1);
        return btnode1;
    }

    public BTNode nextPrO()
    {
        BTNode btnode = this;
        BTNode btnode1 = null;
        if(btnode.lchild != null)
            btnode1 = btnode.lchild;
        else
        if(btnode.rchild != null)
        {
            btnode1 = btnode.rchild;
        } else
        {
            for(; (btnode1 = btnode.parent) != null && (btnode != btnode1.lchild || btnode1.rchild == null); btnode = btnode1);
            if(btnode1 != null)
                btnode1 = btnode1.rchild;
        }
        return btnode1;
    }

    public BTNode prevPrO()
    {
        BTNode btnode = null;
        btnode = parent;
        if(btnode != null && btnode.lchild != null && this != btnode.lchild)
            btnode = btnode.lchild.lastPrO();
        return btnode;
    }

    public BTNode nextPoO()
    {
        BTNode btnode = null;
        btnode = parent;
        if(btnode != null && this == btnode.lchild && btnode.rchild != null)
            btnode = btnode.rchild.firstPoO();
        return btnode;
    }

    public BTNode prevPoO()
    {
        BTNode btnode = this;
        BTNode btnode1 = null;
        if(btnode.rchild != null)
            btnode1 = btnode.rchild;
        else
        if(btnode.lchild != null)
        {
            btnode1 = btnode.lchild;
        } else
        {
            for(; (btnode1 = btnode.parent) != null && (btnode1.lchild == null || btnode == btnode1.lchild); btnode = btnode1);
            if(btnode1 != null)
                btnode1 = btnode1.lchild;
        }
        return btnode1;
    }

    static final int STABLE = 0;
    static final int LOCATING = 1;
    static final int LOCATED = 2;
    static final int INSERTING = 3;
    static final int INSERTED = 4;
    static final int REMOVING = 5;
    static final int REMOVED = 6;
    static final int ROTATING = 7;
    static final int ROTATED = 8;
    BTNode parent;
    BTNode lchild;
    BTNode rchild;
    BTData data;
    int balance;
    int mode;
    int x;
    int X;
    int y;
    int Y;
}