treedeep.cpp

这个程序包括了用队列建立树

#include<iostream.h>

#define NULL 0
#define  QUEUE_INIT_SIZE  100

typedef struct CSNode{
    char    data;
    struct CSNode  *firstchild, *nextsibling;
}CSNode, *CSTree;
typedef struct{
      CSTree  *elem;
    int front;
    int rear;
}SqQueue;

void InitQueue(SqQueue &Q)
{
    Q.elem=new CSTree[QUEUE_INIT_SIZE+1];
   if(Q.elem) 
    Q.front=Q.rear=NULL;
}//InitQueue
void EnQueue(SqQueue &Q, CSTree e)
{
    Q.elem[Q.rear]=e;
    Q.rear=Q.rear+1;
}//EnQueue
void DeQueue(SqQueue &Q, CSTree &e){
    if(Q.front!=Q.rear) 
	{
    e=Q.elem[Q.front];
    Q.front=Q.front+1;
	}
}//DeQueue
void GetHead(SqQueue &Q, CSTree &e)
{
    if(Q.elem)
    e=Q.elem[Q.front];
}//GetHead

int max(int a, int b)
{return(a>b?a:b);
}

void CreateTree(CSTree &T){
    SqQueue Q;
	InitQueue(Q);
    char ch,fa;
    CSTree p=T;
    CSNode *s,*r;
    T=NULL;
    for(cin>>fa>>ch; ch!='#'; cin>>fa>>ch){
        p=new CSNode;
		p->data=ch; 
		p->firstchild=p->nextsibling=NULL;
        EnQueue(Q,p);//创建一个节点，加入队列
        if(fa=='#') T=p;//所建为根节点
        else{//非根节点的情况
            GetHead(Q,s);//取队头
            while(s->data!=fa){//查询父节点
                DeQueue(Q,s); 
				GetHead(Q,s);
            }//while
            if(!(s->firstchild)) {s->firstchild=p; r=p;}//链接第一个孩子节点
            else{r->nextsibling=p; r=p;}//链接其他孩子节点
        }//else
    }//for
}//CreateTree

int TreeDepth(CSTree T)//求孩子兄弟链表表示的树T的深度
{ int h1,h2;
  if(!T) return 0;
  else{
     h1= TreeDepth(T->firstchild);
     h2=  TreeDepth(T->nextsibling);
  
      return (max(h1+1,h2));
  }
}//TreeDepth   

void main()
{
CSTree T;
cout<<"请输入树（按从左到右，从上到下的顺序输入）:"<<endl; 
CreateTree(T);                         
cout<<endl;
cout<<"孩子兄弟链表表示的树T的深度为:"<<TreeDepth(T)<<endl;
}