treenode.cpp

来自「关联规则中转换树算法在VC下的实现」· C++ 代码 · 共 116 行

// TreeNode.cpp: implementation of the CTreeNode class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AssocRule.h"
#include "TreeNode.h"
#include "buffer.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction of TreeNode
//////////////////////////////////////////////////////////////////////

CTreeNode::CTreeNode()
{
	HasSinglePath = TRUE;
	Root=Create(-1,0);
}

CTreeNode::~CTreeNode()
{

}

Node* CTreeNode::Create(ItemType itmno, int c1, Node* pSib, Node* pSon)
{
	Node *p1;
	
	p1=(Node*)fp_buf->newbuf(1, sizeof(Node));
	if (p1==NULL)
		return NULL;
	
	p1->itemNo = itmno;
	p1->count = c1;
	p1->pSibNext = pSib;
	p1->psLink = pSon;
	return p1;
	
}

BOOL CTreeNode::insert_tree(int itemnum, ItemType *pitem, int count1)
{
	Node *p1, *p2;
	int i;
	Node *pt=Root;
	
	// 向pt为根的树中插入pitem指向的项序列
	for (i=0; i<itemnum; i++)
	{
		ItemType itno=*pitem;
		p1=pt->psLink;
		p2=NULL;
		if (p1 == NULL)   // 此前pt没有子结点
		{
			p2=Create(itno, count1);
			
			if (p2 == NULL)
				return FALSE;
			
			pt->psLink = p2;
		}
		else   // 此前pt有子结点
		{
			if ( (itno) < p1->itemNo )   //新结点是目前itemNo最小的结点
			{
				p2=Create(itno, count1, p1);
				
				if (p2 == NULL)
					return FALSE;
				
				pt->psLink = p2;
				HasSinglePath = FALSE;
			}
			else if ( itno == p1->itemNo )  //新结点与原来第一个结点的itemNo相同
			{
				p1->count += count1;
				p2 = p1;
			}
			else  	// 查找合适的插入位置
			{
				while ((p1->pSibNext != NULL) && (p1->pSibNext->itemNo < itno))
					p1 = p1->pSibNext;
				
				// 新结点是其双亲的子结点中itemNo最大的结点
				// 或新结点应插在结点p1之后
				if ((p1->pSibNext == NULL)||(p1->pSibNext->itemNo > itno))
				{
					p2=Create(itno, count1, p1->pSibNext);
					
					if (p2 == NULL)
						return FALSE;
					
					p1->pSibNext = p2;
					HasSinglePath = FALSE;
				}
				else  // (p1->pSibNext->itemNo == itno)找到与项序列第一个元素相同的结点
				{
					p2 = p1->pSibNext;
					p2->count += count1;
				}
			}
		}
		
		pitem++;
		pt=p2;
	}
	
	return TRUE;
}