tree.txt

树的实现,以C语言来实现树.在UNIX下编译通过的,可供借鉴使用

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

#ifndef NULL
#define NULL  0
#endif

#define MAXRULEROW 5000
#define NUM	10

typedef struct _JL_Node
{
	int nIsLeaf;
	int nNum;
	char data[20];		//belong to port_id
	char area_id[20];	//belong to area_id
	struct JL_Node* branch[NUM];
}JL_Node, *PJL_Node;

typedef struct _JLTrieHead
{
	char szSwitchCode[10];
	JL_Node* pRoot;
	int nNodeCnt;
}JLTrieHead, *PJLTrieHead;



int  InitJLNode(JL_Node* pNode)
{
	int i;

	
	pNode->nIsLeaf = 0;
	pNode->nNum = 0;
	memset(pNode->data, 0, sizeof(pNode->data));
	//printf("pNode->data's length is %d\n", sizeof(pNode->data));
	
	for (i=0; i<NUM; i++) 
		pNode->branch[i] = NULL;
	
	return 0;
}


int JLSearch(const char* szWord, char *entry, char *szAreaid)  
{
	int nCharIndex;
	int nTreeIdx = 0;
	
	//JL_Node *location = g_stJlTrieHead[nTreeIdx].pRoot;
	JL_Node *location = ptrTeleHead->pRoot;

	
	while( location!=NULL && *szWord!=0 ) 
	{
		if (*szWord>='0' && *szWord<='9') 
			nCharIndex = *szWord-'0';
		else 
			return 0;// 不合法的单词
			
		if (location->data != NULL)
		{
			memset(entry, 0, 20);
			memset(szAreaid, 0, 20);
			strcpy(entry, location->data);
			strcpy(szAreaid, location->area_id);
		}
		
		location = (JL_Node *)location->branch[nCharIndex];
		
		szWord++;
	}
	
	if (location != NULL && location->nIsLeaf) //全字匹配
	{
		memset(entry, 0, 20);
		memset(szAreaid, 0, 20);
		strcpy(entry, location->data);
		strcpy(szAreaid, location->area_id);
		//printf("Find current node ,belong to '%s' port\n", location->data);

		return 1;
	}
	else if(strlen(entry) > 0)
	{
		//printf("Find pre node ,belong to '%s' port\n", entry);

		return 1;
	}
	else
		return 0;// 不合法的单词
		
}

int JLInsert(const char* szWord, char* entry, char *areaid) 
{
	int result = 1, nPostion = 0;
	int nTreeIdx = 0;
	int nCharIndex;
	JL_Node *location = g_stJlTrieHead[nTreeIdx].pRoot;
	JL_Node e;
	
	if ( location == NULL ) 
	{
		g_stJlTrieHead[nTreeIdx].pRoot = DeQueue(ptrTeleHead);
		ptrTeleHead->pRoot = g_stJlTrieHead[nTreeIdx].pRoot;
		//g_stJlTrieHead[nTreeIdx].pRoot = (JL_Node*)malloc(sizeof(JL_Node));
		InitJLNode(g_stJlTrieHead[nTreeIdx].pRoot);
		location = g_stJlTrieHead[nTreeIdx].pRoot;
		g_stJlTrieHead[nTreeIdx].nNodeCnt++;
		ptrTeleHead->nNodeCnt++;
	}
	while( location!=NULL && *szWord!=0 ) 
	{
		if (*szWord>='0' && *szWord<='9') 
			nCharIndex = *szWord-'0';
		else 
			return 0;	// 不合法的单词
		if( location->branch[nCharIndex] == NULL ) 
		{
			location->branch[nCharIndex] = (JL_Node*)DeQueue(ptrTeleHead);
			// location->branch[nCharIndex] = (JL_Node*)malloc(sizeof(JL_Node));
			InitJLNode((JL_Node*)location->branch[nCharIndex]);
			location->nNum++;
			g_stJlTrieHead[nTreeIdx].nNodeCnt++;
			ptrTeleHead->nNodeCnt++;
		}
		location = (JL_Node*)location->branch[nCharIndex];
		nPostion++;
		szWord++;
	}
	if (location->nIsLeaf ) 
		result = 0;//欲插入的单词已经存在
	else 
	{
		location->nIsLeaf  = 1;
		
		strcpy(location->data, entry);
		strcpy(location->area_id, areaid);

	}
	
	return result;
	
}


int JLRemove(char* szWord)	//在Trie树中删除指定的号码头串pWord
{
	int result = 1, nPostion = 0, nPrePosition = 0;
	int nCharIndex, nTreeIdx = 0;
	JL_Node *location = g_stJlTrieHead[nTreeIdx].pRoot;
	JL_Node* FatherNode = NULL;
	char szWordBack[20];
	memset(szWordBack, 0, sizeof(szWordBack));
	strcpy(szWordBack, szWord);
	
	while( location!=NULL && *szWord!=0 ) 
	{
		if (*szWord>='0' && *szWord<='9') 
			nCharIndex = *szWord-'0';
		else
		{
			printf("No the key:%s \n", szWord);
			return 0;// 不合法的单词
		}
		nPrePosition = nCharIndex;
		FatherNode = location;
		location = (JL_Node*)location->branch[nCharIndex];
		nPostion++;
		szWord++;
	}
	if(location!=NULL && location->nNum == 0)// && strcmp(location->data, szEntry) == 0) //找到了待删除叶子节点元素
	{
		if(location->nIsLeaf)
		{
			printf("Find the specified leaf-node, addr %02x for remove\n",location);
		}
		else
			printf("Find the specified branch-node:addr %02x for remove\n", location);

		//location->data = NULL;
		    
		free(location);
		
		if(FatherNode)
		{
			FatherNode->branch[nPrePosition] = NULL;
			if(--(FatherNode->nNum) ==0 && !FatherNode->nIsLeaf)
			{
				szWordBack[nPostion-1] = '\0';
				JLRemove(szWordBack);
			}
		}
		return 1;
	}
	else if(location!=NULL && location->nNum > 0 && location->nIsLeaf)// && strcmp(location->data, szEntry) == 0) //找到了待删除非叶子节点元素
	{
		printf("remove the branch-leaf-node[%02x] \n", location);
		return 2;
	}
	else
	{
		printf("No found this element:%s \n", szWordBack);
		return -1; //没找到待删除元素
	}
}


/*delete the trie-tree*/
void JLDelTree(JL_Node* location)
{
	int i;
	if ( location == NULL) 
	return;
	
	if (location->nNum == 0)	// This is a leaf-node 
	{
		//printf("destroy leaf-node addr is %02x\n", location);
		free(location);
	}
	else						// It is branch-node
	{
		for (i = 0; i < NUM; i++)
		{
		 	if (location->branch[i] != NULL)
		 	{
		 		JLDelTree((JL_Node*)location->branch[i]);
		 		
		 		location->nNum--;
		 		
		 		if (location->nNum == 0)	// This is a leaf-node 
				{
					free(location);
					
					break;
				}
		 	}
		}
	}
}

/*
int main(void)
{
	int nLen = 0, i;
	char szValue[20];

	InitQueue();
	
	nLen = QueueLength(ptrTeleHead);
	
	printf("Queue's length is %d\n", nLen);
	
	memset(szValue, 0, sizeof(szValue));
	
	g_stJlTrieHead[0].pRoot = NULL;
	ptrTeleHead->pRoot = NULL;
	JLInsert("28", "28");

	JLInsert("2886", "2886");
	JLInsert("28862",  "28862");
	if (JLSearch("288627", szValue))
		printf("'288627' was found.  return '%s'\n", szValue);
	else
		printf(" '288627' was no found.  \n");


	if (JLSearch("2", szValue))
		printf("'2' was found.  return '%s'\n", szValue);
	else
		printf(" '2' was no found.  \n");

	printf("Create %d node \n", ptrTeleHead->nNodeCnt);
	
	//JLRemove("288", 0);
	//JLInsert("884", 0, "884");
	//JLInsert("883", 0, "883");
	
	//JLDelTree(g_stJlTrieHead[0].pRoot);

	return 0;

}
*/