www.pudn.com > huffman.rar > ECBTree.c

#include "ECBTree.h" 
#include "MyAssert.h" 
#include "ECStack.h" 
#include  
#include  
 
PBinTree consBTree(EBTreeType* initList) 
{ 
	PBinTree pbtree; 
	pbtree=(PBinTree)malloc(sizeof(BinTree)); 
	 
	if(pbtree!=NULL) 
		*pbtree=consRestBTree(initList); 
	 
	gConsPos=0; 
	 
	return pbtree; 
} 
 
PBinTreeNode consRestBTree(EBTreeType* initList) 
{ 
	PBinTreeNode pbnode; 
	 
	if(initList[gConsPos]=='@') 
	{ 
		gConsPos++; 
		pbnode=NULL; 
	} 
	else 
	{ 
		pbnode=(PBinTreeNode)malloc(sizeof(struct BinTreeNode)); 
		 
		assertF(pbnode!=NULL,"In consRestBTree,MEM APPLY FAILURE\n"); 
		 
		pbnode->info=initList[gConsPos]; 
		 
		gConsPos++; 
		 
		pbnode->llink=consRestBTree(initList); 
		pbnode->rlink=consRestBTree(initList); 
	} 
	 
	return pbnode; 
} 
 
void preOrder(PBinTreeNode inNode) 
{ 
	if(inNode==NULL) 
		return; 
	else 
	{ 
		//preVisit(inNode->info); 
		printf("%c->",inNode->info); 
		preOrder(inNode->llink); 
		preOrder(inNode->rlink); 
	} 
} 
 
void preVisit(EBTreeType info) 
{ 
	printf("%c->",info); 
} 
 
 
//before it 
/* 
	findLen=0; 
	gFind=0; 
*/ 
void findPath(PBinTreeNode inNode,PBinTreeNode searchNode) 
{ 
	if(inNode==NULL) 
		return; 
	else 
	{ 
		 
		if(gFind) 
			 return; 
		 
		prePanDuan(inNode,searchNode); 
		 
		if(!gFind) 
		{ 
			findPath(inNode->llink,searchNode); 
			findPath(inNode->rlink,searchNode); 
		} 
	} 
} 
 
void prePanDuan(PBinTreeNode inNode,PBinTreeNode searchNode) 
{ 
	if(inNode==searchNode) 
			gFind=1; 
			 
	gFindList[findLen]=inNode->info; 
	findLen++; 
} 
 
 
void  locateNode(PBinTreeNode inNode,EBTreeType inInfo,PBinTree targetNode) 
{ 
	if(inNode==NULL) 
		return ; 
	else 
	{ 
		if(inNode->info==inInfo) 
		{ 
			*targetNode=inNode; 
			gFind=1; 
			return; 
		} 
		else 
		{ 
			locateNode(inNode->llink,inInfo,targetNode); 
			locateNode(inNode->rlink,inInfo,targetNode); 
		} 
	} 
 
 } 
 
 int locateVisit(EBTreeType info) 
 { 
	return 0; 
 } 
  
 void preOrderUnStack(PBinTreeNode inNode) 
{ 
	 
	PBinTreeNode p; 
	PSeqStack myStack; 
	int flag; 
 
	assertF(inNode!=NULL,"pass in node is null\n"); 
	 
 
	myStack=createNullSeqStack(); 
	p=inNode; 
	 
	preVisit(p->info);//visit 
	seqPush(myStack,p); 
	while(!isNullSeqStack(myStack)) 
	{ 
		while(p->llink!=NULL) 
		{ 
			p=p->llink;//move to left child node 
			preVisit(p->info);//visit 
			seqPush(myStack,p);//push current node to the stack. 
		} 
		 
		flag=0; 
		 
		while(!flag&&!isNullSeqStack(myStack)) 
		{ 
			p=seqPop(myStack); 
			if(p->rlink!=NULL) 
			{ 
				p=p->rlink; 
				preVisit(p->info);//visit 
				seqPush(myStack,p); 
				flag=1; 
			} 
		} 
	} 
	printf("preOrder visit end\n"); 
} 
 
 
/*Start of Haffman Tree Ulti Function*/ 
/* 
	struct HtNode 
	{ 
		EBTreeType type; 
		int parentIndex; 
		int llinkIndex; 
		int rlinkIndex; 
	}; 
*/ 
PHtTree consHtTree(EBTreeType* initList) 
{ 
	PHtTree pht; 
//	int i; 
	 
	pht=(PHtTree)malloc(sizeof(struct HtTree)); 
	 
	assertF(pht!=NULL,"in consHtTree,mem apply failure\n"); 
	 
//	for(i=0;i<2*m-1;i++) 
	 
	return NULL; 
} 
 
PHtTree haffmanAlgorithm(int m,EBTreeType* w) 
{ 
	PHtTree pht; 
	int i,j; 
	int firstMinIndex,secondMinIndex; 
	int firstMinW,secondMinW; 
	 
	pht=(PHtTree)malloc(sizeof(struct HtTree)); 
	 
	assertF(pht!=NULL,"in haffman algorithm,mem apply failure\n"); 
	 
	/*Initialize the tree array*/ 
	for(i=0;i<2*m-1;i++) 
	{ 
		pht->ht[i].llinkIndex=-1; 
		pht->ht[i].rlinkIndex=-1; 
		pht->ht[i].parentIndex=-1; 
		if(iht[i].ww=w[i]; 
			pht->ht[i].info=(char)i; 
		} 
		else  
			pht->ht[i].ww=-1; 
	} 
	 
	for(i=0;iht[j].wwht[j].parentIndex==-1) 
			{ 
				//trans minFirst info to minSecond info 
				secondMinIndex=firstMinIndex; 
				secondMinW=firstMinW; 
				 
				//set new first min node. 
				firstMinIndex=j; 
				firstMinW=pht->ht[j].ww; 
			} 
			else if(pht->ht[j].wwht[j].parentIndex==-1)/*update second node info*/ 
			{ 
				secondMinW=pht->ht[j].ww; 
				secondMinIndex=j; 
			} 
		} 
		 
		//Construct a new node. m+i is current new node's index 
			pht->ht[firstMinIndex].parentIndex=m+i; 
			pht->ht[secondMinIndex].parentIndex=m+i; 
			 
			pht->ht[m+i].ww=firstMinW+secondMinW; 
			pht->ht[m+i].llinkIndex=firstMinIndex; 
			pht->ht[m+i].rlinkIndex=secondMinIndex; 
			pht->rootIndex=m+i; 
	} 
	 
	return pht; 
} 
 
/*Invoke 
	preHtOrder(myHtTree,myHtTree->rootIndex) 
*/ 
void preHtOrder(PHtTree inTree,int rootIndex) 
{ 
	if(rootIndex==-1) 
		return; 
	else 
	{ 
		preHtVisit(inTree->ht[rootIndex].info); 
		preHtOrder(inTree,inTree->ht[rootIndex].llinkIndex); 
		preHtOrder(inTree,inTree->ht[rootIndex].rlinkIndex); 
	} 
} 
/*Invoke: 
	preHaffListMake(myHtTree,myHtTree->rootIndex,0x00,0,myList) 
*/ 
void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inList) 
{ 
	/* 
	typedef struct 
	{ 
		char asciiCode; 
		unsigned haffCode; 
		int haffCodeLen; 
	}HaffCode; 
	*/ 
	if(inTree->ht[rootIndex].llinkIndex==-1&&inTree->ht[rootIndex].rlinkIndex==-1) 
	{ 
		inList[inTree->ht[rootIndex].info].haffCode=youBiao; 
		inList[inTree->ht[rootIndex].info].haffCodeLen=sDepth; 
	} 
	else 
	{ 
		preHaffListMake(inTree,inTree->ht[rootIndex].llinkIndex,youBiao<<1,sDepth+1,inList); 
		preHaffListMake(inTree,inTree->ht[rootIndex].rlinkIndex,(youBiao<<1)|0x01,sDepth+1,inList); 
	} 
} 
 
 
void preHtVisit(InfoType info) 
{ 
	printf("%c->",info); 
}