ntreeop.c

一个C语言的N叉树的操作代码

/*********************************************************************
* 版权所有 (C)2005, 中兴通讯股份有限公司。
*
* 文件名称： nTreeOP.C
* 文件标识： 
* 其它说明： n叉树的操作
* 当前版本： V1.0
* 作    者： 廖月旺
* 完成日期： 
*
* 修改记录1：
*    修改日期：2005年4月19日
*    版 本 号：V1.0
*    修 改 人：廖月旺
*    修改内容：创建
*    修改日期：2005年4月25日
*    版 本 号：V2.0
*    修 改 人：廖月旺
*    修改内容：修改增加结点和删除结点时候报错
**********************************************************************/

#include <stdio.h>
#include <stdlib.h>

/*#undef  VOS_WINNT*/
#define  VOS_WINNT

#ifdef VOS_WINNT
#define TreeTstmain main
#endif

#define SuccessRet 1;
#define FailedRet  0;


#define MaxTreeSize 100           /*向量空间的大小，由用户定义*/
typedef char DataType;            /*应由用户定义*/
typedef int  INT;
typedef INT  RetStatus;

/*子链表结点	*/
typedef struct CNode{           
	INT child;                /*孩子结点在向量中对应的序号*/
	struct CNode *pNext;
}CNode;

typedef struct CPNode{ 
	DataType data;            /*存放树中结点数据*/
	INT parent;               /*双亲指针，指示结点的双亲在向量中的位置*/
	CNode *pFirstchild;       /*孩子链表的头指针*/
}CPNode;

typedef struct CPTree{
	CPNode nodes[MaxTreeSize];
	INT nodenum;		      /*nodenum为结点总数*/
	INT root;                 /*root指出根在向量中的位置*/
}CPTree;

typedef CPTree * pTree;            /*定义双亲孩子链表指针类型*/

extern pTree AllocTreeRoot(void);
extern CPNode * FindRootNode(pTree pTreeNode);
extern void PreOrder(struct CPNode * pRootNode,pTree pTreeNode);
extern RetStatus AddChildNode(struct CPNode * pParent , struct CPNode * pChild ,pTree pTreeNode);
extern void DelNode(struct CPNode * node ,pTree pTreeNode);
extern void DelChildNode(struct CPNode * node ,pTree pTreeNode);
extern void TreeTstmain(void);

/**********************************************************************
* 函数名称： AllocTreeRoot
* 功能描述： 分配树空间并初始化根结点
* 访问的表： 无
* 修改的表： 无
* 输入参数： 无
* 输出参数： 无
* 返 回 值： pTree
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/19        V1.0      廖月旺        创建
* 
***********************************************************************/
pTree AllocTreeRoot(void)
{
	INT i = 0;
	pTree pTreeNode;
	
    pTreeNode=(pTree)malloc(sizeof(struct CPTree));
	if(pTreeNode==NULL) 
	{
		pTreeNode=(pTree)realloc(pTreeNode,sizeof(struct CPTree));
	}	
	
	/*初始化根结点*/
	pTreeNode->nodenum = 1;
	pTreeNode->root = 0;
	pTreeNode->nodes[pTreeNode->root].data = 'A';
	pTreeNode->nodes[pTreeNode->root].parent = -1;        /*根无双亲，其parent域为-1*/
	pTreeNode->nodes[pTreeNode->root].pFirstchild = NULL; /*根目前无孩子，其孩子链表为空*/
	/*初始化其余向量空间*/
	for (i=1;i<MaxTreeSize;i++)
	{
		pTreeNode->nodes[i].data = 'a';
		pTreeNode->nodes[i].parent = -2;         /*其余还没成为结点，其parent域为-2*/
		pTreeNode->nodes[i].pFirstchild = NULL;  /*其余还没成为结点，其孩子链表为空*/
	}
	
	return (pTreeNode);
}

/**********************************************************************
* 函数名称： FindRootNode
* 功能描述： 找根结点
* 访问的表： 无
* 修改的表： 无
* 输入参数： pTree pTreeNode   树
* 输出参数： 无
* 返 回 值： CPNode *  根结点指针
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/19        V1.0      廖月旺        创建
* 
***********************************************************************/
CPNode * FindRootNode(pTree pTreeNode)
{
	CPNode * pRootNode = NULL;
	/*找到根结点*/
	INT i = 0;

	for(i = 0; i < MaxTreeSize; i++)
	{
		if(pTreeNode->nodes[i].parent == -1)
		{
			break;
		}
	}
	if(i == MaxTreeSize)
	{
		if (pTreeNode->nodes[i].parent != -1) {
			printf("None of root node!\n");    
			return NULL;
		}
	}
	pTreeNode->root = i;
	pRootNode = &pTreeNode->nodes[pTreeNode->root];
	
	return (pRootNode);
}

/**********************************************************************
* 函数名称： PreOrder
* 功能描述： 前序遍历树
* 访问的表： 无
* 修改的表： 无
* 输入参数： CPNode * pRootNode  树的根结点 ；pTree pTreeNode 树
* 输出参数： 无
* 返 回 值： 无
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/19         V1.0      廖月旺        创建
* 
***********************************************************************/
void PreOrder(struct CPNode * pRootNode,pTree pTreeNode)
{
	CNode * pCur = NULL;
	if (pRootNode == NULL || pTreeNode == NULL) {
		return;
	}
	if (pRootNode->parent == -1) {
		printf("This is ROOT node! \n");
	}
	printf("The Current Node data is %c \n",pRootNode->data);
	printf("The Current Node parent is %d \n\n",pRootNode->parent);
	
	if(pRootNode->pFirstchild != NULL)
	{
		pCur = pRootNode->pFirstchild;
		while (pCur){
			PreOrder(&pTreeNode->nodes[pCur->child],pTreeNode);
			pCur = pCur->pNext;
		}
	}
}

/**********************************************************************
* 函数名称： AddChildNode
* 功能描述： 增加结点
* 访问的表： 无
* 修改的表： 无
* 输入参数： CPNode * pParent 父结点；CPNode * pChild 要插入的孩子结点；pTree pTreeNode 树
* 输出参数： 无
* 返 回 值： SuccessRet 成功；FailedRet 失败
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/19        V1.0      廖月旺        创建
* 
***********************************************************************/
RetStatus AddChildNode(struct CPNode * pParent , struct CPNode * pChild ,pTree pTreeNode)
{
	/*在存放结点的数组中搜索空余位置并把新结点放入*/
	INT i;
	CNode * pCNode = NULL;
	CNode * pCur = NULL;
	CNode * pPre = NULL;
	
	for(i = 0;i < MaxTreeSize;i++)
	{
		if(pTreeNode->nodes[i].parent == -2)
		{
			pTreeNode->nodes[i].data = pChild->data;
			pTreeNode->nodes[i].parent = pChild->parent;
			pTreeNode->nodes[i].pFirstchild = pChild->pFirstchild;
			pTreeNode->nodenum ++;
			break;
		}
	}
	if(i == MaxTreeSize)
	{
		if (pTreeNode->nodes[i].parent != -2) {
			printf("None of enough space in array!\n");    
			return FailedRet;
		}
	}
	
	pCNode=(CNode *)malloc(sizeof(struct CNode));
	if(pTreeNode==NULL) 
	{
		pCNode=(CNode *)realloc(pCNode,sizeof(struct CNode));
	}
	pCNode->child = i;
	pCNode->pNext = NULL;
	
	if (pParent->pFirstchild == NULL) {
		pParent->pFirstchild = pCNode;
	}
	else
	{		
		/*在孩子链表尾部插入*/
		pCur = pParent->pFirstchild->pNext;
		pPre = pParent->pFirstchild;
		
		while (pCur) {
			pPre = pCur;
			pCur = pCur->pNext;
		}
		
		pPre->pNext = pCNode;
	}	
	
	return SuccessRet;
}

/**********************************************************************
* 函数名称： DelNode
* 功能描述： 删除一个结点
* 访问的表： 无
* 修改的表： 无
* 输入参数： CPNode * node 要删除的结点 ；pTree pTreeNode 树
* 输出参数： 无
* 返 回 值： 无
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/19        V1.0      廖月旺        创建
* 
***********************************************************************/
void DelNode(struct CPNode * node ,pTree pTreeNode)
{
	CNode * pCur = NULL;
	CNode * pNxt = NULL;	
	
	if (node->pFirstchild != NULL) {
		pCur =  node->pFirstchild;
		while (pCur) {
			DelNode(&pTreeNode->nodes[pCur->child],pTreeNode);
			pNxt = pCur->pNext;
			free(pCur);
			pCur = pNxt;
		}
		node->parent = -2;
		node->data = 'a';
		node->pFirstchild = NULL;
		pTreeNode->nodenum --;		
	}
	else{
		node->parent = -2;
		node->data = 'a';
		pTreeNode->nodenum --;
	}	
}

/**********************************************************************
* 函数名称： DelChildNode
* 功能描述： 删除一个结点并且在其父亲的孩子链表中把其孩子结点删除
* 访问的表： 无
* 修改的表： 无
* 输入参数： CPNode * node 要删除的结点 ；pTree pTreeNode 树
* 输出参数： 无
* 返 回 值： 无
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/25        V1.0      廖月旺        创建
* 
***********************************************************************/
void DelChildNode(struct CPNode * node ,pTree pTreeNode)
{
	INT child,parent;
	
	CNode * pPre = NULL;
	CNode * pCur = NULL;

	child = parent = -1;
	
	/*在没释放其在数组中的向量空间前记录下其向量位置和其父结点位置*/
	if (node->parent != -1) {			
		if (pTreeNode->nodes[node->parent].pFirstchild) {
			child = pTreeNode->nodes[node->parent].pFirstchild->child;
		}
	}
	parent =  node->parent;
	if (parent != -1) {
		
		DelNode(node ,pTreeNode);
		
		/*在其父结点的孩子链表中删除其孩子结点*/		
		
		if (pTreeNode->nodes[parent].pFirstchild) {
			if (pTreeNode->nodes[child].parent == -2){
				pPre = pTreeNode->nodes[parent].pFirstchild;
				pCur = pTreeNode->nodes[parent].pFirstchild->pNext;
				free(pPre);
				pTreeNode->nodes[parent].pFirstchild = pCur;				
			}
			else
			{			
				pCur = pTreeNode->nodes[parent].pFirstchild->pNext;
				pPre = pTreeNode->nodes[parent].pFirstchild;
				while (pCur) {
					if (pTreeNode->nodes[pCur->child].parent == -2)  {
						break;
					}
					pPre = pCur;
					pCur = pCur->pNext;
				}
				pPre->pNext = pCur->pNext;
				free(pCur);	
			}
		}
	}
	else
	{
	/*	DelNode(node ,pTreeNode);
		free(pTreeNode);
		pTreeNode = NULL;*/		
		printf("\nAttention: YOU CAN'T DELETE THE ROOT NODE!!!\n");
	}
				
}

/**********************************************************************
* 函数名称： Tstmain
* 功能描述： 测试函数入口
* 访问的表： 无
* 修改的表： 无
* 输入参数： 无
* 输出参数： 无
* 返 回 值： 无
* 其它说明： 无
* 修改日期        版本号     修改人       修改内容
* -----------------------------------------------
* 2005/4/19        V1.0      廖月旺        创建
* 
***********************************************************************/
void TreeTstmain(void)
{
	pTree pT;
	CPNode childNode;

	CPNode * pRootNode;
	
	pT = AllocTreeRoot();
	printf("The root num in the NODE array is %d \n",pT->root);
	
	childNode.data = 'B';
	childNode.parent = pT->root;
	childNode.pFirstchild = NULL;
	AddChildNode(&pT->nodes[pT->root] , &childNode ,pT);
	
	childNode.data = 'C';
	childNode.parent = pT->root;
	childNode.pFirstchild = NULL;
    AddChildNode(&pT->nodes[pT->root] , &childNode ,pT);
	
	childNode.data = 'E';
	childNode.parent = 1;
	childNode.pFirstchild = NULL;
    AddChildNode(&pT->nodes[1] , &childNode ,pT);
	
	childNode.data = 'F';
	childNode.parent = 1;
	childNode.pFirstchild = NULL;
    AddChildNode(&pT->nodes[1] , &childNode ,pT);
	
	DelChildNode(&pT->nodes[0] ,pT);
	
	printf("The whole tree have %d nodes. \n\n",pT->nodenum);
	
	PreOrder(&pT->nodes[pT->root],pT);

    pRootNode = FindRootNode(pT);
	printf("The Root Node data is %c \n",pRootNode->data);
	printf("The Root Node parent is %d \n\n",pRootNode->parent);

	printf("\n******** This test is created by Jack Lio. Email:[e-mail]********\n\n");
	
	
}