202662.cpp

数据结构（清华版）

//6.62求一棵以孩子-兄弟链表表示的树的深度
#include<iostream>
using namespace std;
//======================================================================================
typedef char TElemtype;//创建树结构体
typedef struct TNode
{
	TElemtype data;
	TNode *firstchild ,*nextsibling;
}*Tree;
void CreateTree(Tree &T,char s[],int &i)//创建孩子兄弟链表表示的树函数 
{
	Tree p;i++;
	if (s[i]=='#'){T=NULL;return;}
	T=new TNode;T->data=s[i];
	T->firstchild=T->nextsibling=NULL;
	if (s[i+1]=='(')
	{
		i++;CreateTree(T->firstchild,s,i);
		p=T->firstchild;
		while (s[i+1]==',')
		{
			i++;CreateTree(p->nextsibling,s,i);
			p=p->nextsibling;
		}
		i++;
	}
}
void CreateTree(Tree &T,char s[])
{
	int i=-1;
	CreateTree(T,s,i);
}
//==================================================================================
int TreeDepth(Tree T)//创建函数求得树的深度
{
	Tree p;
	int i,j;
	i=0;
	if(!T) return 0;
	p=T->firstchild;
	while (p)
	{
		j=TreeDepth(p);
		if(i<j) i=j;
		p=p->nextsibling;
	}
	return i+1;
}
//===================================================================================
void main()
{
	Tree T;
	char s[]="A(B(E,F(q,w)),C(G),D)";
	CreateTree(T,s);
	cout<<"该树的深度为  "<<TreeDepth(T)<<endl;
}