tree.h

求树的深度和叶子数

#include "stdlib.h"
#include "stdio.h"


#define QUEUE_INIT_SIZE 100 	      //MAXSIZE	存储空间初始分配量
#define QUEUEINCREMENT  10	
#define OK 1
#define ERROR 0	
#define OVERFLOW -1


typedef char ELEM;	//定义树节点元素类型

typedef struct CSNode
{   
	ELEM data;
    CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

typedef CSTree ELEMTYPE;

////////////////////////////////////////////////////////////////下面定义队列的相关操作
typedef struct
{ 
    ELEMTYPE *front;        //头指针，若队列不空，指向队列头元素
    ELEMTYPE *rear;		    //尾指针，若队列不空，指向队列尾元素的下一个位置
	int queuesize;	        //记录队列的大小
}Queue;

void InitQueue (Queue &Q) 
{
	Q.front=(ELEMTYPE*)malloc(QUEUE_INIT_SIZE *sizeof (ELEMTYPE));
    if (!Q.front) exit (OVERFLOW);    // 存储分配失败
    Q.rear=Q.front;
	Q.queuesize=QUEUE_INIT_SIZE;
}

void EnQueue(Queue &Q, ELEMTYPE e) 
{     
	if(Q.rear-Q.front>=Q.queuesize)
	{
		Q.front=(ELEMTYPE*)realloc(Q.front,(Q.queuesize +QUEUEINCREMENT)*sizeof(ELEMTYPE));
		if(!Q.front)exit(OVERFLOW);
		Q.rear=Q.front +Q.queuesize;
		Q.queuesize +=QUEUEINCREMENT;
	}
	*Q.rear ++=e;
}

ELEMTYPE DeQueue(Queue &Q)  // 若队列不空，则用e返回其值，并返回OK;
{      
	ELEMTYPE e;
    if (Q.front == Q.rear)printf("队列已空！\n");
    e = *Q.front++;
    return (e);
}

int QueueEmpty(Queue Q)
{
	if(Q.front == Q.rear)
		return 1;
	else 
		return 0;
}

ELEMTYPE GetHead(Queue Q)
{
	ELEMTYPE e;
    if (Q.front == Q.rear)printf("队列已空了！\n");
    e = *Q.front;
    return (e);
}
/////////////////////////////////////////////////////////////////////队列操作定义完毕


ELEMTYPE GetTreeNode(ELEM ch)
{
	ELEMTYPE t=(ELEMTYPE )malloc(sizeof(ELEMTYPE));
	t->data=ch;
	t->firstchild=NULL; 
	t->nextsibling=NULL;
	return(t);
}

void CreatTree( CSTree &T ) 
{ 
	printf("请以从上到下,从左到右的顺序输入孩子兄弟的关系，中间以逗号间隔：\n");
	T = NULL;
	ELEM fa,ch;
	Queue Q;
	InitQueue(Q);
	ELEMTYPE p,s,r;
	scanf("%c,%c",&fa, &ch);c 
	getchar();
    for( ; ch!='/';  ) 
    {
		p = GetTreeNode(ch);		// 创建结点
		EnQueue(Q, p);				// 指针入队列
		if (fa =='/') T=p;			// 所建为根结点
        else
		{
			s=GetHead(Q);			// 取队列头元素(指针值)
			while (s->data != fa )	// 查询双亲结点
			{ 
				s=DeQueue(Q);  
				s=GetHead(Q);
			}   
			if(!(s->firstchild)) 
			{ 
				s->firstchild = p;
				r = p; 
			}// 链接第一个孩子结点
			else 
			{ 
				r->nextsibling = p;  
				r = p;  
			}// 链接其它孩子结点 
		}//else 非根结点的情况
		scanf("%c,%c",&fa, &ch);
		getchar();
     }//for
}//CreateTree	

int TreeDepth(CSTree T) //求树的深度
{
	int h1,h2;
	if(!T) return 0;
	else 
	{
		h1 = TreeDepth( T->firstchild );
		h2 = TreeDepth( T->nextsibling);
		return( h1+1 > h2? h1+1 : h2);
	}
} // TreeDepth

void visit(ELEM e)
{
	printf("%c",e);
}


void CountNodeNumber(CSTree T,int &NodeNumbers)	 //求树的叶子数
{
	if(T)
	{
		if(!(T->firstchild))
		{
			visit(T->data);								// 访问结点
			NodeNumbers++;
		}
		CountNodeNumber(T->firstchild,NodeNumbers);		// 遍历左子树					 
		CountNodeNumber(T->nextsibling,NodeNumbers);	// 遍历右子树
	}
}//CountNodeNumber