树的建立及其深度.cpp

树结构是数据结构中最重要的结构。利用树可以实现遍历等要求。该算法用于建立树

//求树的深度
#include <stdio.h> 
#include <stdlib.h>
#define   length  100 
typedef struct TNode 
{ 
   char data; 
   int du;
   struct TNode *fchild,*nsibling; 
} TNode,*TTree;//结点结构
typedef struct
{ 
  TTree  elem[length];
  int front,rear ; 
}QU;
//树的建立 
void Tree( TTree &BT,char *a,int *b,int n)
{  
	if(n==0) BT=NULL;
	else
	{
		TTree p=NULL;
		QU  qu;
		int i=0;  
		qu.front=0;   
		qu.rear=0;
		p=( TNode*)malloc(sizeof( TNode));
		p->data=a[i];  
		p->du=b[i];
		p->nsibling=NULL;
		BT=p;
		i++; 
		qu.elem[qu.rear]=p; 
		qu.rear++;
		if(n==1)BT->fchild=NULL;
		else
		{
		  while(qu.front!=qu.rear)
		  { 
			  p=qu.elem[qu.front];qu.front++;int j=p->du;
	          if(j==0)p->fchild=NULL;
		      else
			  { 
				  TTree q=NULL, q1=NULL;
			      while(j>0)
				  {
					  q=( TNode*)malloc(sizeof( TNode));
					  q->data=a[i];    q->du=b[i];
					  if(j==p->du)p->fchild=q;
					  else q1->nsibling=q; 
					  qu.elem[qu.rear]=q;
					  qu.rear++;
					  q1=q;
					  i++; 
					  j--;    
				  }//while(j>0)
				  q1->nsibling=NULL;
			  }//else
		  }//while
	  }//else
	}//else
}//Tree
int TMax(int x,int y)//求取深度使用的计算
{   int z=0;
	if(x>y) z=x;
	else    z=y;
	return z;
}
int TreeDepth(TTree T)
{//求树的深度
	int h1=0,h2=0,heigh=0;
	if(!T)return 0;
	else
	{
		h1=TreeDepth(T->fchild);
		h2=TreeDepth(T->nsibling);
		heigh=TMax(h1+1,h2);
		return heigh;
	}
}
 void main() 
 { 
  TTree T;
  char a[length];
  int b[length];
  int treedepth,n;
  printf("\n输入树的结点总数n:");
  scanf("%3d",&n); 
  printf("\n输入该树的层次序列:");
  for(int i=0;i<=n;i++)
  {scanf("%c",&a[i]);}  
  printf("\n输入该树的度序列:");
  for(int j=0;j<n;j++){scanf("%d",&b[j]);} 
  Tree(T,a,b,n);      
  printf("\n该树的深度为："); 
  treedepth=TreeDepth(T);
  printf("%d",treedepth);
 }