linkedbinarytree.jad

源程序（包括最初的版本

// Decompiled by DJ v3.8.8.85 Copyright 2005 Atanas Neshkov  Date: 2005-6-30 14:41:41
// Home Page : http://members.fortunecity.com/neshkov/dj.html  - Check often for new version!
// Decompiler options: packimports(3) 
// Source File Name:   LinkedBinaryTree.java

package datastructures;

import java.io.PrintStream;
import queue.ArrayQueue;
import stack.ArrayStack;

// Referenced classes of package datastructures:
//            BinaryTreeNode, BinaryTree

public class LinkedBinaryTree
    implements BinaryTree
{
    class Ceng
    {

        BinaryTreeNode node;
        int flag;

        Ceng()
        {
        }

        Ceng(BinaryTreeNode n, int f)
        {
            node = n;
            flag = f;
        }
    }

    class BTreeNodeFlag
    {

        BinaryTreeNode node;
        int flag;

        BTreeNodeFlag()
        {
            flag = 0;
        }

        BTreeNodeFlag(BinaryTreeNode tp)
        {
            flag = 0;
            node = tp;
        }

        BTreeNodeFlag(BinaryTreeNode tp, int f)
        {
            flag = 0;
            node = tp;
            flag = f;
        }
    }


    public LinkedBinaryTree()
    {
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public Object root()
    {
        return root != null ? root.element : null;
    }

    public void makeTree(Object root, Object left, Object right)
    {
        this.root = new BinaryTreeNode(root, ((LinkedBinaryTree)left).root, ((LinkedBinaryTree)right).root);
    }

    public BinaryTree removeLeftSubtree()
    {
        if(root == null)
        {
            throw new IllegalArgumentException("tree is empty");
        } else
        {
            LinkedBinaryTree leftSubtree = new LinkedBinaryTree();
            leftSubtree.root = root.leftChild;
            root.leftChild = null;
            return leftSubtree;
        }
    }

    public BinaryTree removeRightSubtree()
    {
        if(root == null)
        {
            throw new IllegalArgumentException("tree is empty");
        } else
        {
            LinkedBinaryTree rightSubtree = new LinkedBinaryTree();
            rightSubtree.root = root.rightChild;
            root.rightChild = null;
            return rightSubtree;
        }
    }

    public void preOrder()
    {
        thePreOrder(root);
    }

    static void thePreOrder(BinaryTreeNode t)
    {
        if(t != null)
        {
            System.out.print(String.valueOf(String.valueOf(t.toString())).concat(" "));
            thePreOrder(t.leftChild);
            thePreOrder(t.rightChild);
        }
    }

    public void inOrder()
    {
        theInOrder(root);
    }

    static void theInOrder(BinaryTreeNode t)
    {
        if(t != null)
        {
            theInOrder(t.leftChild);
            System.out.print(String.valueOf(String.valueOf(t.toString())).concat(" "));
            theInOrder(t.rightChild);
        }
    }

    public void postOrder()
    {
        thePostOrder(root);
    }

    static void thePostOrder(BinaryTreeNode t)
    {
        if(t != null)
        {
            thePostOrder(t.leftChild);
            thePostOrder(t.rightChild);
            System.out.print(String.valueOf(String.valueOf(t.toString())).concat(" "));
        }
    }

    public int size()
    {
        count = 0;
        thePreOrderCount(root);
        return count;
    }

    static void thePreOrderCount(BinaryTreeNode t)
    {
        if(t != null)
        {
            count++;
            thePreOrderCount(t.leftChild);
            thePreOrderCount(t.rightChild);
        }
    }

    public int height()
    {
        return theHeight(root);
    }

    static int theHeight(BinaryTreeNode t)
    {
        if(t == null)
            return 0;
        int hl = theHeight(t.leftChild);
        int hr = theHeight(t.rightChild);
        if(hl > hr)
            return ++hl;
        else
            return ++hr;
    }

    public int Similar(BinaryTreeNode bRoot)
    {
        return thePostOrderSimilar(root, bRoot);
    }

    static int thePostOrderSimilar(BinaryTreeNode b1, BinaryTreeNode b2)
    {
        if(b1 == null && b2 == null)
            return 1;
        if(b1 != null && b2 == null || b1 == null && b2 != null)
        {
            return 0;
        } else
        {
            int t1 = thePostOrderSimilar(b1.leftChild, b2.leftChild);
            int t2 = thePostOrderSimilar(b1.rightChild, b2.rightChild);
            return t1 * t2;
        }
    }

    public void preOrder_iter()
    {
        thePreOrder_iter(root);
    }

    void thePreOrder_iter(BinaryTreeNode t)
    {
        if(t != null)
        {
            BinaryTreeNode p = t;
            ArrayStack s = new ArrayStack();
            do
            {
                for(; p != null; p = p.leftChild)
                {
                    System.out.print(String.valueOf(String.valueOf(p.toString())).concat(" "));
                    s.push(p);
                }

                if(!s.empty())
                {
                    p = (BinaryTreeNode)s.pop();
                    p = p.rightChild;
                }
            } while(p != null || !s.empty());
        }
    }

    public void postOrder_iter()
    {
        thePostOrder_iter(root);
    }

    void thePostOrder_iter(BinaryTreeNode t)
    {
        if(t != null)
        {
            BinaryTreeNode p = t;
            ArrayStack s = new ArrayStack();
            do
            {
                for(; p != null; p = p.leftChild)
                {
                    BTreeNodeFlag element = new BTreeNodeFlag();
                    element.flag = 1;
                    element.node = p;
                    s.push(element);
                }

                if(!s.empty())
                {
                    BTreeNodeFlag element = (BTreeNodeFlag)s.peek();
                    if(element.flag == 2 && !s.empty())
                    {
                        System.out.print(String.valueOf(String.valueOf(element.node.toString())).concat(" "));
                        s.pop();
                        if(!s.empty())
                        {
                            element = (BTreeNodeFlag)s.peek();
                            if(element.flag == 1)
                            {
                                p = element.node.rightChild;
                                element.flag = 2;
                            }
                        }
                    } else
                    {
                        element.flag = 2;
                        p = element.node.rightChild;
                    }
                }
            } while(p != null || !s.empty());
        }
    }

    public void levelOrderTraverse()
    {
        theLevelOrder(root);
    }

    void theLevelOrder(BinaryTreeNode t)
    {
        ArrayQueue q = new ArrayQueue();
        int i = 1;
        if(t != null)
        {
            BinaryTreeNode p = t;
            Ceng ceng = new Ceng(p, i);
            q.put(ceng);
            do
            {
                if(q.isEmpty() || p == null)
                    break;
                if(p.leftChild != null)
                {
                    ceng = new Ceng(p.leftChild, ++i);
                    q.put(ceng);
                }
                if(p.rightChild != null)
                {
                    if(p.leftChild == null)
                        ceng = new Ceng(p.rightChild, ++i);
                    else
                        ceng = new Ceng(p.rightChild, i);
                    q.put(ceng);
                }
                if(!q.isEmpty())
                {
                    ceng = (Ceng)q.remove();
                    if(q.isEmpty() || ceng.flag < ((Ceng)q.getFrontElement()).flag)
                        System.out.println(ceng.node.toString());
                    else
                        System.out.print(String.valueOf(String.valueOf(ceng.node.toString())).concat(" "));
                    if(!q.isEmpty())
                    {
                        ceng = (Ceng)q.getFrontElement();
                        p = ceng.node;
                    }
                }
            } while(true);
        }
    }

    public void deleteSubtree(Object x)
    {
        theDeleteSubtree(root, x);
    }

    static void theDeleteSubtree(BinaryTreeNode t, Object x)
    {
        if(t != null)
        {
            if(t.leftChild != null && t.leftChild.element.equals(x))
                t.leftChild = null;
            if(t.rightChild != null && t.rightChild.element.equals(x))
                t.rightChild = null;
            theDeleteSubtree(t.leftChild, x);
            theDeleteSubtree(t.rightChild, x);
        }
    }

    public void creatBinaryTree(String s)
    {
        int i = 0;
        ArrayQueue q = new ArrayQueue();
        String fa = s.substring(i, i + 1);
        String ch = s.substring(i + 1, i + 2);
        for(String flag = s.substring(i + 2, i + 3); ch.compareTo("#") != 0; flag = s.substring(i + 2, i + 3))
        {
            BinaryTreeNode p1 = new BinaryTreeNode(ch);
            q.put(p1);
            if(fa.compareTo("#") == 0)
            {
                root = p1;
            } else
            {
                BinaryTreeNode p2;
                for(p2 = (BinaryTreeNode)q.getFrontElement(); !p2.element.equals(fa); p2 = (BinaryTreeNode)q.getFrontElement())
                    q.remove();

                if(flag.compareTo("L") == 0)
                    p2.leftChild = p1;
                else
                if(flag.compareTo("R") == 0)
                    p2.rightChild = p1;
            }
            i += 3;
            fa = s.substring(i, i + 1);
            ch = s.substring(i + 1, i + 2);
        }

    }

    public void crtBT(Object pre[], Object ino[])
    {
        root = theCrtBT(root, pre, ino, 0, 0, pre.length);
    }

    static int search(Object a[], Object b)
    {
        for(int i = 0; i < a.length; i++)
            if(a[i].equals(b))
                return i;

        return -1;
    }

    static BinaryTreeNode theCrtBT(BinaryTreeNode t, Object pre[], Object ino[], int ps, int is, int n)
    {
        if(n == 0)
        {
            t = null;
        } else
        {
            int k = search(ino, pre[ps]);
            if(k == -1)
            {
                t = null;
            } else
            {
                t = new BinaryTreeNode();
                t.element = pre[ps];
                if(k == is)
                    t.leftChild = null;
                else
                    t.leftChild = theCrtBT(t.leftChild, pre, ino, ps + 1, is, k - is);
                if(k == (is + n) - 1)
                    t.rightChild = null;
                else
                    t.rightChild = theCrtBT(t.rightChild, pre, ino, ps + 1 + (k - is), k + 1, n - (k - is) - 1);
            }
        }
        return t;
    }

    public void printBTree()
    {
        thePrintBTree(root, 0);
    }

    static void thePrintBTree(BinaryTreeNode t, int i)
    {
        if(t.rightChild != null)
            thePrintBTree(t.rightChild, i + 1);
        for(int j = 1; j <= i; j++)
            System.out.print("   ");

        System.out.println(t.element.toString());
        if(t.leftChild != null)
            thePrintBTree(t.leftChild, i + 1);
    }

    public static void main(String args[])
    {
        LinkedBinaryTree Null = new LinkedBinaryTree();
        LinkedBinaryTree x = new LinkedBinaryTree();
        LinkedBinaryTree y = new LinkedBinaryTree();
        LinkedBinaryTree z = new LinkedBinaryTree();
        y.makeTree(new Integer(1), Null, Null);
        z.makeTree(new Integer(2), Null, Null);
        x.makeTree(new Integer(3), y, z);
        y.makeTree(new Integer(4), x, Null);
        System.out.println("Postorder sequence is ");
        y.postOrder();
        System.out.println();
        LinkedBinaryTree Nullother = new LinkedBinaryTree();
        LinkedBinaryTree xother = new LinkedBinaryTree();
        LinkedBinaryTree yother = new LinkedBinaryTree();
        LinkedBinaryTree zother = new LinkedBinaryTree();
        LinkedBinaryTree mother = new LinkedBinaryTree();
        LinkedBinaryTree nother = new LinkedBinaryTree();
        nother.makeTree(new Integer(9), Null, Null);
        yother.makeTree(new Integer(4), Null, Null);
        zother.makeTree(new Integer(5), nother, Null);
        mother.makeTree(new Integer(8), Null, Null);
        xother.makeTree(new Integer(6), yother, zother);
        yother.makeTree(new Integer(7), xother, mother);
        System.out.println("Preorder sequence is ");
        y.preOrder();
        System.out.println();
        System.out.println("Other Preorder sequence is ");
        yother.preOrder();
        System.out.println();
        int t = y.Similar(yother.root);
        if(t == 1)
            System.out.println("two trees are similar");
        else
            System.out.println("two trees aren't similar");
        System.out.println("Preorder_iter sequence is ");
        y.preOrder_iter();
        System.out.println();
        System.out.println("Postorder_iter sequence is ");
        y.postOrder_iter();
        System.out.println();
        System.out.println("levelOrder sequence is ");
        y.levelOrderTraverse();
        System.out.println();
        System.out.println("Preorder sequence is ");
        y.preOrder();
        System.out.println();
        y.deleteSubtree(new Integer(3));
        System.out.println("delete 3,the new Preorder sequence is ");
        y.preOrder();
        System.out.println();
        String s = "#ALABLACRBDLCELCFRDGRFHL##L";
        LinkedBinaryTree tree = new LinkedBinaryTree();
        System.out.println(s);
        tree.creatBinaryTree(s);
        System.out.println("Preorder tree is ");
        tree.preOrder();
        System.out.println();
        Object pre[] = {
            "a", "b", "c", "d", "e", "f", "g"
        };
        Object ino[] = {
            "c", "b", "d", "a", "e", "g", "f"
        };
        LinkedBinaryTree treeother = new LinkedBinaryTree();
        treeother.crtBT(pre, ino);
        System.out.println("Preorder tree is ");
        treeother.preOrder();
        System.out.println();
        System.out.println("Inorder tree is ");
        treeother.inOrder();
        System.out.println();
        System.out.println("Postorder tree is ");
        treeother.postOrder();
        System.out.println();
        yother.printBTree();
    }

    protected BinaryTreeNode root;
    static int count;
}