博弈树树的c实现

下棋属于一种博弈游戏，博弈过程可以用树（博弈树）来表示。假设游戏由两个人（ A 和 B ）玩，开始由某个人从根结点开始走，两个人轮流走棋，每次只能走一步， 下一步棋只能选择当前结点的孩子结点，谁先走到叶子结点为胜。例如，对于下图所示的博弈树，若 A 先走，可以选 f ， B 若选 h ，则 A 选 j 胜。 编写一程序，让计算机和人下棋。当计算机走下一步时，可以根据以下情况决定下一步： （1） 若存在可以确保取胜的一个孩子结点，则选择该结点作为下一步； （2） 若存在多个可以确保取胜的孩子结点，则选择其中高度最小的结点作为下一步（若有多个选择，则选最左边的结点）； （3） 若不存在可以确保取胜的一个孩子结点，则选择高度最大的孩子结点作为下一步（若有多个选择，则选最左边的结点）； 例： （下面的黑体为输入） (a,(b,(x)),(c,(d),(e,(g),(h)),(f))) a b x c d e g h f Who play first(0: computer; 1: player )? 1 player: c computer: d Sorry, you lost. Continue(y/n)? y Who play first(0: computer; 1: player )? 1 player: x illegal move. player: b computer: x Sorry, you lost. Continue(y/n)? y Who play first(0: computer; 1: player )? 0 computer: c player: f Congratulate, you win. Continue(y/n)? n

#include
#include
#include

char tree[200]IllegalMove[20];

typedef struct ChildList* Child;

typedef struct NODE
{
	char Name;
	char Pure; //高度是否纯奇数 或 纯偶数。
	int Height; //该树的高度
	struct NODE * Father; //父节点
	Child List; //孩子节点
}*Tree;
struct ChildList
{
	Tree SubTree;
	Child Next;
};
Tree PeoVsBot;
void AddASubTree（Tree father Tree child）
{
	Child TempCell;
	TempCell = （Child）malloc（sizeof（struct ChildList））;
	TempCell->SubTree = child;
	TempCell->Next = father->List;
	father->List = TempCell;
}
Tree CreateTree（char name Tree Father）
{
	Tree ATree;
	ATree = （Tree）malloc（sizeof（struct NODE））;
	ATree->Father = Father;
	ATree->Height = 0;
	ATree->List = NULL;
	ATree->Name = name;
	ATree->Pure = 1;
	if （Father != NULL）
	{
		AddASubTree（Father ATree）;
	}
	return ATree;
}
void PrintStr（char s[]）
{
	int len i;
	len = strlen（s）;
	for （i = 0; i < len; i++）
	{
		if （s[i] == ‘ ‘） putchar（NULL）;
		else printf（“%c“ s[i]）;
	}
	printf（“\n“）;
}
int PrintTree（int father int height Tree GrandFather）//当前节点（下标）是father，GrandFather是当前节点的父节点地址
{
	int i;
	for （i = 0; i < height; i++）
	{
		putchar（NULL）;
		putchar（NULL）;
		putchar（NULL）;
		putchar（NULL）;
	}
	printf（“%c\n“ tree[father]）;
	Tree CurrentNode;
	CurrentNode = CreateTree（tree[father] GrandFather）;
	if （height == 0）
	{
		PeoVsBot = CurrentNode;
	}
	for （i = father + 1; 1; i++）
	{
		if （tree[i] == ‘）‘）
		{
			//修改grandfather的heightpure //树的根没有father
			if （CurrentNode->Father != NULL）
			{
				if （CurrentNode->Father->Height == 0）
				{
					CurrentNode->Father->Height = CurrentNode->Height + 1;
				}
				else
				{
					if （CurrentNode->Father->Pure == 1 && （（CurrentNode->Height+1） % 2 != CurrentNode->Father->Height % 2））
					{
						CurrentNode->Father->Pure = 0;
					}
					if （CurrentNode->Height + 1 > CurrentNode->Father->Height）
					{
						CurrentNode->Father->Height = CurrentNode->Height + 1;
					}
				}
			}
			return i;//返回这课树的结束的下标
		}
		else if （tree[i] == ‘（‘）//还要判断输入是不不是标准的。即函数判断（）之间是否有节点
		{
			i = PrintTree（i + 1 height + 1 CurrentNode）;//子树  得到返回值 i
		}
	}
}

Tree Bot（Tree father）//计算机操作
{
	Child Temp = father->List;
	Tree SureStep = NULL NotSureStep = NULL;
	while （Temp != NULL）
	{
		if （Temp->SubTree->Pur