tree.cpp

数据结构编程题

#include "iostream.h"
#include "stdio.h"
#include "malloc.h"






typedef struct TNode
{
	char data;
	struct TNode *child;
	struct TNode *brother;
}TNode,*Tree;


void CreateTree(Tree &T)
{
	int i=0;
	char st[100];
	scanf("%s",st);	
	Tree queue[100];
	int rear=0,front=0;
	Tree p=NULL;


	if(st[i]=='*')T=NULL;
	else
	{
		T=(TNode*)malloc(sizeof(TNode));
		queue[rear]=T;
		T->child=NULL;
		T->brother=NULL;
		queue[rear]->data=st[i];
		rear=(rear+1)%100;
		i++;
		while(st[i]!='#')
		{
			
			if((st[i]!='*')&&(st[i]!='&'))
			{
				p=(TNode*)malloc(sizeof(TNode));
				p->data=st[i];
				p->child=NULL;
				p->brother=NULL;
				queue[rear-1]->brother=p; /////////////////////////////////// 
				queue[rear]=p;
				rear=(rear+1)%100;
				i++;
			}
			else if(st[i]!='&')
			{
				queue[rear-1]->brother=NULL;
				i++;
				p=(TNode*)malloc(sizeof(TNode));
				p->data=st[i];
				p->brother=NULL;
				p->child=NULL;
				queue[rear]=p;
				queue[front]->child=p;
				rear=(rear+1)%100;
				front=(front+1)%100;
				i++;
			}
			else
			{
				front=(front+1)%100;
				i++;
			}
		}
	}
}

int  Depth(Tree T)          
{
	int h1,h2;
	if(!T)
		return 0;
	else
	{
		h1=Depth(T->child);
		h2=Depth(T->brother);
	}
	
	return ((h1+1)>h2? (h1+1):h2);
}

void main()
{
	cout<<"每层树建立完毕用*号换层!"<<endl;
	cout<<"没有子树的节点用&号结束!"<<endl;
	cout<<"用#表示树的结束!"<<endl;
	cout<<"请输入所要建立的树"<<endl;
	Tree T;
	CreateTree(T);
	cout<<Depth(T);
	cout<<"层";
	cout<<endl;
}