树的深度.cpp

建一棵树后然后求树的深度

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct CSNode{
     int data;
     struct CSNode *firstchild, *nextsibling;
} CSNode;
//建立树的节点的结构体
typedef struct QNode{
	CSNode * dataNode;
	struct QNode * next;
}QNode;
typedef struct {
	QNode * front;
	QNode * rear;
}QLink;
//建立队列的节点
//声明一个全局变量  一个队列
QLink Q;
CSNode * GetTreeNode(int child)
{
	CSNode * p=(CSNode * )malloc(sizeof(CSNode));
	p->data=child;
	p->firstchild=NULL;
	p->nextsibling=NULL;
	return p;
}
//生成树的节点的函数
void InitQueue(QLink &Q)//建立一个空队列
{
	Q.front=(QNode *)malloc(sizeof(QNode));
                                      //产生一个头结点
 //  if(!Q.front) exit(OVERFLOW);     //存储分配失败
      Q.rear= Q.front;       //头、尾指针均指向头结点
      Q.front -> next=NULL;

}
//初始化一个队列
void EnQueue(QLink &Q,CSNode * p)
{
	QNode *pp;
	pp=(QNode *)malloc(sizeof(QNode));
	if(!p)
		exit(0);
	
	pp->dataNode=p;
	pp->next=0;

	Q.rear->next=pp;
	Q.rear=pp;
}
//入队函数
CSNode *GetHead(QLink &Q)
{

		return Q.front->next->dataNode;

}
//返回队头的节点
void DeQueue(QLink &Q)
{
	QNode *p;
	if(Q.front==Q.rear)
		return ;
	p=Q.front->next;
	Q.front->next=p->next;
	

	free(p);

}
//删除队头的节点
CSNode * CreatTree() {
	CSNode * T ;
    T = NULL;
	int fa,ch;

	InitQueue(Q);
	CSNode *p,*r,*s;
    for( scanf("%d,%d",&fa,&ch); ch!=0;scanf("%d,%d",&fa,&ch))
	{
	p = GetTreeNode(ch);    // 创建结点
	
	EnQueue(Q,p); 	// 指针入队列

	if (fa == 0)
		T = p;     // 所建为点根结
    else {
 	s=GetHead(Q); // 取队列头元素(指针值)
	while (s->data != fa ) 
	{ // 查询双亲结点

		DeQueue(Q);
		s=GetHead(Q);
	}
	
	if (!(s->firstchild)) 
	{ 
	
		s->firstchild = p; r = p; }
                         // 链接第一个孩子结点
	else { r->nextsibling = p;  r = p;  }
                           // 链接其它孩子结点 

		}     // 非根结点的情况  //else
   } // for
	return T;
} // CreateTree	
int max(int a,int b)
{
	if(a>=b)
		return a;
	else
		return b;
}

int TreeDepth(CSNode *T) {
	int h1,h2;
  if(!T)  return 0;
  else {
     h1 = TreeDepth(T->firstchild);
     h2 = TreeDepth(T->nextsibling);
	 return(max(h1+1, h2));

  }
} // TreeDepth树的深度函数

int main()
{
	CSNode * T ;
	T=CreatTree();
	printf("深度:%d\n",TreeDepth(T));
	

}