LZW

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;

class LZWTree
{
    private class Node
    {
        public Node()
        {
            this.letter = '\\';
        }

        public Node(char b)
        {
            this.letter = b;
        }

        public char getLetter()
        {
            return this.letter;
        }

        public Node getLeftZeroChild()
        {
            return this.leftZeroChild;
        }

        public Node getRightOneChild()
        {
            return this.rightOneChild;
        }

        public void addLeftZeroChild(Node newLeftZeroChild)
        {
            this.leftZeroChild = newLeftZeroChild;
        }

        public void addRightOneChild(Node newRightOneChild)
        {
            this.rightOneChild = newRightOneChild;
        }

        private char letter;
        private Node leftZeroChild, rightOneChild;
    }

    public LZWTree()
    {
        currentNode = root;
    }

    public void insert(char b)
    {
        if ('0' == b)
        {
            if (null == currentNode.getLeftZeroChild())
            {
                currentNode.addLeftZeroChild(new Node('0'));
                currentNode = root;
            }
            else
                currentNode = currentNode.getLeftZeroChild();
        }
        else
        {
            if (null == currentNode.getRightOneChild())
            {
                currentNode.addRightOneChild(new Node('1'));
                currentNode = root;
            }
            else
                currentNode = currentNode.getRightOneChild();
        }
    }

    public void print(java.io.Writer output) throws IOException
    {
        depth = 0;
        print(root, output);
    }

    public int getDepth()
    {
        depth = maxDepth = 0;
        _getDepth(root);
        return maxDepth - 1;
    }

    public double getAverage()
    {
        depth = averageSum = averageCount = 0;
        _getAverage(root);
        average = ((double) averageSum) / averageCount;
        return average;
    }

    public double getVariance()
    {
        average = getAverage();
        varianceSum = 0.0;
        depth = averageCount = 0;

        _getVariance(root);

        if (averageCount - 1 > 0)
            variance = Math.sqrt(varianceSum / (averageCount - 1));
        else
            variance = Math.sqrt(varianceSum);
        return variance;
    }

    private void print(Node node, java.io.Writer output) throws IOException
    {
        if (null != node)
        {
            ++depth;
            print(node.getRightOneChild(), output);

            for(int i=0; i < depth; ++i)
                output.write(new String("---"));
            output.write(node.getLetter() + "(" + (depth - 1) + ")" + '\n');

            print(node.getLeftZeroChild(), output);
            --depth;
        }
    }

    protected void _getDepth(Node node)
    {
         if (null != node)
         {
                 ++depth;

                 if(depth > maxDepth)
                     maxDepth = depth;

                 _getDepth(node.getRightOneChild());
                 _getDepth(node.getLeftZeroChild());
                 --depth;
         }
    }

    protected void _getAverage(Node node)
    {
        if (null != node)
        {
                ++depth;
                _getAverage(node.getRightOneChild());
                _getAverage(node.getLeftZeroChild());
                --depth;
                if( null == node.getRightOneChild() && null == node.getLeftZeroChild() )
                {
                        ++averageCount;
                        averageSum += depth;
                }
        }
    }

    protected void _getVariance(Node node)
    {
        if(null != node)
        {
                ++depth;
                _getVariance(node.getRightOneChild());
                _getVariance(node.getLeftZeroChild());
                --depth;
                if( null == node.getRightOneChild() && null == node.getLeftZeroChild() )
                {
                        ++averageCount;
                        varianceSum += ((depth - average) * (depth - average));
                }
        }
    }

    private Node currentNode;
    private int depth, averageSum, averageCount;
    private double varianceSum;
    protected Node root = new Node();
    protected int maxDepth;
    protected double average, variance;
}

public class Program
{
    public static void main(String[] args) throws FileNotFoundException, IOException
    {
        String usage = "Usage: lzwtree in_file -o out_file";

        if (args.length < 3)
        {
            System.out.println(usage);
            System.exit(-1);
        }
        if (!"-o".equals(args[1]))
        {
            System.out.println(usage);
            System.exit(-1);
        }

        java.io.InputStream input;
        java.io.Writer output = new java.io.FileWriter(args[2]);

        try
        {
            input = new FileInputStream(args[0]);
        }
        catch (FileNotFoundException e)
        {
            System.out.println("cannot find input file...");
            System.exit(-1);
        }

        input = new FileInputStream(args[0]);
        char ch;
        LZWTree lzw = new LZWTree();


        while(0 < input.available())
        {
            ch = (char)input.read();
            if (0x0a == ch) break;
        }

        boolean inComment = false;
        while(0 < input.available())
        {
            ch = (char)input.read();

                    if(0x3e == ch)
                    {
                            inComment = true;
                            continue;
                    }
                    if(0x0a == ch)
            {
                            inComment = false;
                            continue;
                    }
                    if(inComment) continue;
                    if(0x4e == ch) continue;

                    for(int i=0; i<8; i++)
            {
                            if((ch & 0x80)!=0)
                                    lzw.insert('1');
                            else
                                    lzw.insert('0');
                            ch <<=1 ;
                    }
        }

             lzw.print(output);
             output.write("depth = " + lzw.getDepth() + '\n');
             output.write("mean = " + lzw.getAverage() + '\n');
             output.write("var = " + lzw.getVariance() + '\n');

             input.close();
             output.close();
    }
}