202661.cpp

来自「数据结构（清华版）」· C++ 代码 · 共 89 行

#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 TreeDegree(Tree T)//创建函数求得树的度
{
	Tree p;
	int i,j,k;
	i=0;k=0;
	if(!T) return 0;
	p=T->firstchild;
	while (p)
	{
		i++;
		j=TreeDegree(p);
		if(k<j) k=j;
		p=p->nextsibling;
	}
	return k>i? k:i;
}
//===================================================================================
void main()
{
	Tree T;
	char s[]="A(B(E,F),C(G),D)";
	CreateTree(T,s);
	cout<<"该树的度为  "<<TreeDegree(T)<<endl;
}