数据结构二叉树家谱

//文件名:excise3.cpp
#include 
#include 
#include 
#define MaxWidth 40			//凹入表示法时的最大场宽
#define MaxSize 30			//栈的最大元素个数
#define NAMEWIDTH 10		//姓名的最多字符个数
typedef struct fnode
{
	char father[NAMEWIDTH];	//父
	char wife[NAMEWIDTH];	//母
	char son[NAMEWIDTH];	//子
} FamType;
typedef struct tnode
{
	char name[NAMEWIDTH];
	struct tnode *lchild*rchild;
} BTree;					//家谱树类型
BTree *CreatBTree（char *rootFamType fam[]int n）	//从fam（含n个记录）递归创建一棵二叉树
{
	int i=0j;
	BTree *bt*p;
	bt=（BTree *）malloc（sizeof（BTree））;	//创建父亲节点
	strcpy（bt->nameroot）;
	bt->lchild=bt->rchild=NULL;
	while （i		i++;
	if （i	{
		p=（BTree *）malloc（sizeof（BTree））;		//创建母亲节点
		p->lchild=p->rchild=NULL;
		strcpy（p->namefam[i].wife）;
		bt->lchild=p;
		for （j=0;j			if （strcmp（fam[j].fatherroot）==0）	//找到一个儿子
			{
				p->rchild=CreatBTree（fam[j].sonfamn）;
				p=p->rchild;
			}
	}
	return（bt）;
}
void DispTree1（BTree *b）	//以括号表示法输出二叉树
{
	if （b!=NULL）
	{
		printf（“%s“b->name）;
		if （b->lchild!=NULL || b->rchild!=NULL）
		{
			printf（“（“）;
			DispTree1（b->lchild）;
			if （b->rchild!=NULL） 
				printf（““）;
			DispTree1（b->rchild）;
			printf（“）“）;
		}
	}
}
void DispTree2（BTree *bt）	//以凹入表示法输出
{
	BTree *St[MaxSize]*p;
	int Level[MaxSize][2]topniwidth=4;
	if （bt!=NULL）
	{
		printf（“  >>家谱凹入表示法:\n“）;
        top=1;
		St[top]=bt;				//根节点进栈
		Level[top][0]=width;
		while （top>0）
        {
			p=St[top];			//退栈并凹入显示该节点值
			n=Level[top][0];
			for （i=1;i<=n;i++）  //其中n为显示场宽字符以右对齐显示
				printf（“ “）;
			printf（“%6s“p->name）;
			if （Level[top][1]==1）
				printf（“（l）“）;
			else
				printf（“（r）“）;
			for （i=n+1;i<=MaxWidth-6;i+=2）
				printf（“--“）;
			printf（“\n“）;
			top--;
			if （p->rchild!=NULL）
			{								//将右子树根节点进栈
				top++;
				St[top]=p->rchild;
				Level[top][0]=n+width;		//显示场宽增width
				Level[top][1]=2;			//为右孩子节点
			}
			if （p->lchild!=NULL）
			{								//将左子树根节点进栈
				top++;
				St[top]=p->lchild;
				Level[top][0]=n+width;		//显示场宽增width
				Level[top][1]=1;			//为左孩子节点
			}
        }
	}
}
BTree *FindNode（BTree *btchar xm[]） //采用先序递归算法找name为xm的节点
{
	BTree *p=bt;
	if （p==NULL） 
		return（NULL）;
	else
	{
		if （strcmp（p->namexm）==0）
			return（p）;
		else
		{
			bt=FindNode（p->lchildxm）;
			if （bt!=NULL） 
				return（bt）;
			else 
				return（FindNode（p->rchildxm））;
		}
	}
}
void FindSon（BTree *bt）	//输出某人的所有儿子
{
	char xm[NAMEWIDTH];
	BTree *p;
	printf（“  >>父亲姓名:“）;
	scanf（“%s“xm）;
	p=FindNode（btxm）;
	if （p==NULL）
		printf（“  >>不存在%s的父亲!\n“xm）;
	else
	{
		p=p->lchild;
		if （p==NULL）
			printf（“  >>%s没有妻子\n“xm）;
		else
		{
			p=p->rchild;
			if （p==NULL）
				printf（“  >>%s没有儿子!\n“xm）;
			else
			{
				printf（“  >>%s的儿子:“xm）;
				while （p!=NULL）
				{
					printf（“%10s“p->name）;
					p=p->rchild;
				}
				printf（“\n“）;
			}
		} 
	}
}