//文件名: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“）;
			}
		}?
	}
}