www.pudn.com > fp_growth_source.rar > ITree.java

package  association.fptree; 
 
import java.io.Serializable; 
import java.util.*; 
/** 
 * ITree树 
 * 05.12.10－第二版 
 * ITree树中同一层次的兄弟结点之间按照项目编号升序排序 
 * 用LinkedList存储同层的兄弟结点 
 *  
 *              _______________________ 
 *   head  --->|__|____|___|___|___|___| 
 *                |        |       | 
 *                V        |       | 
 *          孩子LinkedList  |       | 
 *                         V       | 
 *                                 | 
 *                                 |     _______________________ 
 *                 孩子LinkedList   ---->|__|____|___|___|___|___|            
 *                                         |        |       | 
 *                                         V        V       V 
 * */ 
 
public class ITree implements Serializable{ 
	private int total;                         //记录事务总数 
	private double sCount;                        //在当前记录数下的支持度计数 
	public LinkedList head; 
	int n=0; 
	public ITree(){ 
		this.total=0; 
		this.sCount=0; 
		head=new LinkedList(); 
	} 
	public ITree(int total,int sCount){ 
		this.total=total; 
		this.sCount=sCount; 
		head=new LinkedList(); 
	} 
	/** 
	 * 增加事务记录总数，重新计算1/1000支持度计数 
	 * @param inc 新增的事务记录数 
	 * */ 
	void addTotal(int inc){ 
		total+=inc; 
	} 
	/** 
	 * 取得当前最小支持度计数 
	 * */ 
	double readSCount(){ 
		return sCount; 
	} 
	/** 
	 * 设置ITree的最小支持度计数 
	 * @param n  最小支持度计数 
	 * */ 
	void setSCount(double n){ 
		sCount=n; 
	} 
	/** 
	 * 将堆栈中的项集插入到ITree1 
	 * */ 
	void Insert2(Stack s){ 
		Stack ss; 
		double count; 
		Node top; 
		 
		top=(Node)s.top.obj; 
		count=top.count; 
		ss=s.clone(); 
		Sort.sort(ss);                         //按照项目编号排序		 
		InsertToITree(ss,count); 
		ss=null; 
	} 
	private void InsertToITree(Stack s,double count){ 
		int n; 
		Node node=null,cn=null; 
		LinkedList l; 
		String itemName; 
		int comp; 
		 
        if (s==null||s.IsEmpty()) return;   
		if(head==null) head=new LinkedList(); 
		l=head; 
        while(!s.IsEmpty()){ 
            node=(Node)s.pop(); 
            node.count=0; 
			itemName=node.name; 
			if(l.size()==0){  
				l.add(node); 
				l=new LinkedList(); 
				node.cNode=l; 
				continue; 
			}	 
			for(int i=0;i(); 
						cn.cNode=l; 
					}	 
					break; 
				}else if(comp<0){               //未找到则插入 
				    l.add(i,node);	 
				    l=new LinkedList(); 
				    node.cNode=l; 
				    break; 
				}else if(i==l.size()-1){       //到链尾了还未找到 
					l.add(node); 
					l=new LinkedList(); 
					node.cNode=l; 
					break; 
				} 
			} 
			 
		} 
		node.count+=count;                     //更新支持度计数 
	} 
	private int compare(String it1,String it2){ 
    	int i1,i2; 
    	it1=it1.trim(); 
    	it2=it2.trim(); 
    	i1=Integer.parseInt(it1.substring(1)); 
    	i2=Integer.parseInt(it2.substring(1)); 
    	if (i1>i2)return 1; 
    	else if(i1==i2)return 0; 
    	return -1; 
    }  
	void empty(){ 
		head=null; 
	} 
	/**树是否为空*/ 
	boolean IsEmpty(){ 
		if (head==null||head.size()==0) 
			return true; 
		else return false; 
	} 
	/** 
	 * 测试用打印 
	 * */ 
	void print(LinkedList h,Stack s){ 
		Node node=null; 
		if(h==null) { 
			//System.out.print(n+++":"); 
	    	//Print.print(s,"node"); 
			return; 
		} 
	    for(int i=0;i cNode;  
    	Node(String name){ 
    		count=0; 
    		this.name=name; 
    	} 
    	public Node(String name,int count){ 
    		this.count=count; 
    		this.name=name; 
    	} 
    	public String toString(){ 
    		return name; 
    	} 
	} 
}