利用树型结构进行排序

前段时间遇到一个排序的问题，是对一个数组进行排序，数组中存放的是有级别的对象（已经由Oracle的Connect 进行分级），但是每级内的对象顺序是乱的，下面这个类完成了排序功能
package dsn;

import java.util.*;
import log.*;
import model.*;

public class RequireSorter2
{
    Log4jWrapper log = WebLog.getInstance();
    private static RequireSorter2 instance = new RequireSorter2();
    private RequireSorter2()
    {
    }

    public static RequireSorter2 getInstance()
    {
        return instance;
    }

    public ProductRequire[] sort( ProductRequire[] sourceRequire )
    {
        log.debug("Begin sort");
        long start = System.currentTimeMillis();
        if(null==sourceRequire || sourceRequire.length ==0 )
        {
            return sourceRequire;
        }

        /*构造有序树*/
        SorterTreeNode root = new SorterTreeNode( null );
        for ( int i = 0; i < sourceRequire.length; i++ )
        {
            if(null==sourceRequire[ i ])
            {
                continue;
            }
            SorterTreeNode treeNode = new SorterTreeNode( sourceRequire[ i ] );
            root.add(treeNode);
        }

        /*将树转为数组*/
        sourceRequire = treeToArray(root);
        long end = System.currentTimeMillis();
        log.debug("Sort count:"+sourceRequire.length);
        log.debug("Sort time:"+(end-start));
        return  sourceRequire;
    }

    /**
     * 使用深度优先遍历树,返回数组
     * @param treeNode TreeNode
     * @return ProductRequire[]
     */
    private ProductRequire[] treeToArray(SorterTreeNode treeNode)
    {
        /*存储从树中取出的节点*/
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        stack.push(treeNode);
        SorterTreeNode parent = null;
        SorterTreeNode child = null;
        while(!stack.isEmpty())
        {
            parent = (SorterTreeNode)stack.pop();
            /*根节点是null*/
            if(null!=parent.getProductRequire())
            {
                list.add( parent.getProductRequire() );
            }
            ArrayList children = parent.getChildren();
            for(int i=children.size()-1;i>=0;i--)
            {
                stack.push(children.get(i));
            }
        }
        ProductRequire[] productRequire = (ProductRequire[])list.toArray(new ProductRequire[list.size()]);
        return productRequire;
    }
}

class SorterTreeNode
{
    /*人造节点*/
    public static final String OTHER_LEVEL_REQUIREMENT_NO = "          ";

    /*父节点*/
    private SorterTreeNode parent = null;

    /*本节点存储的对象*/
    private ProductRequire productRequire = null;

    /*子节点*/
    private ArrayList children = new ArrayList();

    private int lastChildIndex = -1;
    /**
     * 私有
     */
    private SorterTreeNode(ProductRequire[] sourceRequire)
    {
    }
    /**
     * 构造函数
     */
    public SorterTreeNode(ProductRequire productRequire)
    {
        this.productRequire  = productRequire;
    }

    public SorterTreeNode getParent()
    {
        return parent;
    }

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

    public ArrayList getChildren()
    {
        return children;
    }

    public ProductRequire getProductRequire()
    {
        return productRequire;
    }

    /**
     * 添加节点
     */
    public void add(SorterTreeNode treeNode)
    {
        if(lastChildIndex<0
           || ((SorterTreeNode)children.get(lastChildIndex)).getProductRequire().getLevelId()==treeNode.getProductRequire().getLevelId())
        {
            insertChild(treeNode);
        }
        else
        {
            ((SorterTreeNode)children.get(lastChildIndex)).add(treeNode);
        }
    }

    /**
     * 按序插入子节点
     * @param productRequire ProductRequire
     */
    private void insertChild(SorterTreeNode child)
    {
        child.setParent(this);
        ProductRequire productRequire = child.getProductRequire();
        ProductRequire tmp = null;
        for(int i=0;i<children.size();i++)
        {
            tmp = ((SorterTreeNode)children.get(i)).getProductRequire();
            if(compare(tmp.getRequirementNo(),productRequire.getRequirementNo())>0)
            {
                lastChildIndex = i;
                children.add(i,child);
                return;
            }
        }
        children.add(child);
        lastChildIndex = children.size()-1;
    }

    public int compare( Object o1, Object o2 )
    {
        int result = ( ( String )o1 ).compareTo( o2 );
        if ( result > 0 && OTHER_LEVEL_REQUIREMENT_NO.equals( o2 ) )
        {
            result = 0;
        }
        return result;
    }

    public boolean equals( Object o1 )
    {
        return true;
    }

}

本文地址：http://com.8s8s.com/it/it13823.htm