btnode.java

The applet illustrates the behaviour of binary search trees, Searching and Sorting Algorithms, Self-

// Source File Name:   BTNode.java


class BTNode extends BTSprite
{

    public BTNode()
    {
        parent = null;
        lchild = null;
        rchild = null;
        balance = 0;
        color = 0;
        data = null;
    }

    public BTNode(BTData data)
    {
        parent = null;
        lchild = null;
        rchild = null;
        balance = 0;
        color = 0;
        this.data = new BTData(data.getKey());
    }

    public BTNode(BTNode node)
    {
        parent = node.parent;
        lchild = node.lchild;
        rchild = node.rchild;
        balance = node.balance;
        data = node.data;
    }

    public BTNode(int color)
    {
        parent = null;
        lchild = null;
        rchild = null;
        balance = 0;
        this.color = color;
        data = null;
    }

    public int getBalance()
    {
        return balance;
    }

    public void setBalance(int balance)
    {
        this.balance = balance;
    }

    public int getColor()
    {
        return color;
    }

    public void setColor(int color)
    {
        this.color = color;
    }

    public BTData getData()
    {
        return data;
    }

    public void setData(BTData data)
    {
        this.data = data;
    }

    public String getKey()
    {
        return data.getKey();
    }

    public void setKey(String key)
    {
        data.setKey(key);
    }

    public BTNode getParent()
    {
        return parent;
    }

    public void setParent(BTNode parent)
    {
        this.parent = parent;
    }

    public BTNode getChild(int side)
    {
        if(side == -1)
            return lchild;
        if(side == 1)
            return rchild;
        else
            return this;
    }

    public BTNode getChild()
    {
        return lchild == null ? rchild : lchild;
    }

    public void setChild(int side, BTNode node)
    {
        if(side == -1)
            lchild = node;
        else
        if(side == 1)
            rchild = node;
        else
            return;
    }

    public int getSide()
    {
        if(parent == null)
            return 0;
        if(this == parent.lchild)
            return -1;
        return this != parent.rchild ? 666 : 1;
    }

    public boolean hasTwoChildren()
    {
        return lchild != null && rchild != null;
    }

    public boolean isLeaf()
    {
        return lchild == null && rchild == null;
    }

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

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

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

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

    public BTNode firstPrO()
    {
        return this;
    }

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

        return node;
    }

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

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

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

    public BTNode lastPoO()
    {
        return this;
    }

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

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

    public BTNode getFirstIn(int order)
    {
        if(order == 0)
            return firstInO();
        if(order == 1)
            return firstPrO();
        if(order == 2)
            return firstPoO();
        else
            return this;
    }

    public BTNode getPrevIn(int order)
    {
        if(order == 0)
            return prevInO();
        if(order == 1)
            return prevPrO();
        if(order == 2)
            return prevPoO();
        else
            return this;
    }

    public BTNode getNextIn(int order)
    {
        if(order == 0)
            return nextInO();
        if(order == 1)
            return nextPrO();
        if(order == 2)
            return nextPoO();
        else
            return this;
    }

    public BTNode getLastIn(int order)
    {
        if(order == 0)
            return lastInO();
        if(order == 1)
            return lastPrO();
        if(order == 2)
            return lastPoO();
        else
            return this;
    }

    public int getDepth(BTNode root)
    {
        BTNode node = this;
        int depth;
        for(depth = 0; node != root; depth++)
            node = node.parent;

        return depth;
    }

    public int getWidth(BTNode root)
    {
        BTNode node = this;
        int width = 0;
        int side = root.compareSide(data);
        while(node != root && node != null) 
        {
            node = node.getNext(-side);
            width += side;
        }
        return width;
    }

    public int compareSide(BTData data)
    {
        int side = data.compareTo(this.data);
        return side;
    }

    public BTNode getFirst(int direction)
    {
        return direction != -1 ? firstInO() : lastInO();
    }

    public BTNode getNext(int direction)
    {
        return direction != -1 ? nextInO() : prevInO();
    }

    public BTNode getPrev(int direction)
    {
        return direction != -1 ? prevInO() : nextInO();
    }

    public BTNode getLast(int direction)
    {
        return direction != -1 ? lastInO() : firstInO();
    }

    static final int LEFT = -1;
    static final int RIGHT = 1;
    static final int NONE = 0;
    static final int EQUAL = 0;
    static final int ERROR = 666;
    BTNode parent;
    BTNode lchild;
    BTNode rchild;
    int balance;
    int color;
    BTData data;
}