#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define		MAX_INT	 32767		//定義最大整數(shù)
#define		MIN_INT -32768		//定義最小整數(shù)
#define		MAX			 1		//極大層節(jié)點(diǎn)標(biāo)志
#define		MIN			 0		//極小層節(jié)點(diǎn)標(biāo)志

//以下結(jié)構(gòu)定義了樹結(jié)構(gòu)的一個(gè)節(jié)點(diǎn)。
//樹結(jié)構(gòu)的表示如下：
//每個(gè)節(jié)點(diǎn)指向其父節(jié)點(diǎn)
//每個(gè)節(jié)點(diǎn)指向其子節(jié)點(diǎn)鏈表
//一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)，形成一個(gè)兄弟鏈表，其父節(jié)點(diǎn)指向該兄弟鏈表的第一個(gè)
//節(jié)點(diǎn)，但是兄弟鏈表中的每個(gè)節(jié)點(diǎn)，都指向其父節(jié)點(diǎn)
struct NODE
{
	char name[10];			//節(jié)點(diǎn)名
	int value;				//節(jié)點(diǎn)的值
	int level;				//節(jié)點(diǎn)處在極大層，還是極小層
	struct NODE *pFrom;		//該節(jié)點(diǎn)的值來自于哪個(gè)子節(jié)點(diǎn)
	struct NODE *pFather;	//指向父節(jié)點(diǎn)
	struct NODE *pChildren; //指向子節(jié)點(diǎn)鏈表
	struct NODE *pNext;		//指向兄弟鏈表的下一個(gè)節(jié)點(diǎn)
};

//動(dòng)態(tài)產(chǎn)生一個(gè)節(jié)點(diǎn)
struct NODE *NewNode(char *name, int level)
{
	struct NODE *pNode = NULL;
	pNode = (NODE*)malloc(sizeof(struct NODE));
	if (pNode == NULL) return NULL;
	strcpy(pNode->name, name);
	if (level == MAX) 
	{
		pNode->value = MIN_INT;
	}
	else 
	{
		pNode->value = MAX_INT;
	}
	pNode->level = level;
	pNode->pFrom = NULL;
	pNode->pFather = NULL;
	pNode->pChildren = NULL;
	pNode->pNext = NULL;
	return pNode;
}
//從已經(jīng)建立的樹中，查找給定名字的節(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針 
struct NODE *Search(char *name, struct NODE *pTree)
{
	struct NODE *pNode = NULL;
	if (pTree == NULL) return NULL;
	if (! strcmp(name, pTree->name)) return pTree;	//如果根節(jié)點(diǎn)就是待查找的節(jié)點(diǎn)，則返回該節(jié)點(diǎn)
	if (pNode = Search(name, pTree->pNext))	//否則從該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)中遞歸查找
	{
		return pNode;	//如果找到，則返回該節(jié)點(diǎn)
	}
	if (pNode = Search(name, pTree->pChildren))	//否則在子節(jié)點(diǎn)中遞歸查找
	{
		return pNode;	//如果找到則返回該節(jié)點(diǎn)
	}
	return NULL;	//以上均找不到的話則返回NULL
}

//從一個(gè)文本文件中讀入一個(gè)樹
struct NODE *ReadTree(FILE *pFile)
{
	char name[256];
	int value;
	struct NODE *pNode = NULL, *pRoot = NULL, *pFNode = NULL, *pLast = NULL;

	//在樹文件中，尋找ROOT標(biāo)志
	while (!feof(pFile))
	{
		fscanf(pFile, "%s", name);
		if (feof(pFile)) return NULL;
		if (! strcmp(name, "ROOT")) break;
	}

	fscanf(pFile, "%s", name);	//得到根節(jié)點(diǎn)名字
	pRoot = NewNode(name, MAX);	//建立根節(jié)點(diǎn)
	if (pRoot == NULL) return NULL;	//如果空間不夠則返回NULL

	//讀文本文件，建立樹結(jié)構(gòu)
	while (!feof(pFile))
	{
		fscanf(pFile, "%s", name);	//name得到父節(jié)點(diǎn)名字
		if (feof(pFile)) return NULL;
		if (! strcmp(name, "VALUE")) break;
		pFNode = Search(name, pRoot);	//得到父節(jié)點(diǎn)在樹中的指針
		if (pFNode == NULL) return NULL;	//如果樹中不存在該節(jié)點(diǎn)則返回NULL

		pLast = NULL;

		//讀子節(jié)點(diǎn)，建立父子關(guān)系和兄弟關(guān)系
		while (!feof(pFile))
		{
			fscanf(pFile, "%s", name);	//得到子節(jié)點(diǎn)名
			if (feof(pFile)) return NULL;
			if (! strcmp(name, "END")) break;
			pNode = NewNode(name, !pFNode->level);	//建立子節(jié)點(diǎn)
			if (pNode == NULL) return NULL;	//空間不夠用時(shí)返回NULL

			if (pLast == NULL)	//如果是第一個(gè)子節(jié)點(diǎn)，其父節(jié)點(diǎn)指向該節(jié)點(diǎn)
			{
				pFNode->pChildren = pNode;
			}
			else
			{
				pLast->pNext = pNode;	//否則將該節(jié)點(diǎn)鏈接到兄弟鏈表中
			}
			pLast = pNode;
			pNode->pFather = pFNode;	//設(shè)置該節(jié)點(diǎn)的父節(jié)點(diǎn)
		}
	}

	//為葉節(jié)點(diǎn)賦初始估計(jì)值
	while (!feof(pFile))
	{
		fscanf(pFile, "%s", name);	//得到葉節(jié)點(diǎn)名
		if (feof(pFile)) return NULL;
		if (! strcmp(name, "END")) break;	//END為結(jié)束標(biāo)志
		fscanf(pFile, "%d", &value);	//得到葉節(jié)點(diǎn)的初始估計(jì)值
		if (feof(pFile)) return NULL;
		pNode = Search(name, pRoot);	//從樹中得到該節(jié)點(diǎn)的指針
		if (pNode == NULL) return NULL;	//如果樹中沒有該節(jié)點(diǎn)，則返回NULL
		pNode->value = value;	//為該節(jié)點(diǎn)賦初始估計(jì)值
	}

	return pRoot;	//返回樹根節(jié)點(diǎn)
}

//顯示信息
void PrintTreeRoot(struct NODE *pRoot)
{
	if (pRoot == NULL) 
		return;	
	printf("根節(jié)點(diǎn): %s\n", pRoot->name);	//顯示根節(jié)點(diǎn)的名字
	printf("倒推值: %d\n", pRoot->value);
	printf("應(yīng)走的步驟: %s\n", pRoot->pFrom->name);
}

//釋放動(dòng)態(tài)產(chǎn)生的樹 
void FreeTree(struct NODE *pRoot)
{
	struct NODE *pChildren = NULL, *pNext = NULL;
	if (pRoot == NULL) return;
	pChildren = pRoot->pChildren;
	pNext = pRoot->pNext;
	free(pRoot);	//釋放根節(jié)點(diǎn)
	FreeTree(pChildren);	//遞歸釋放根節(jié)點(diǎn)的子節(jié)點(diǎn)
	FreeTree(pNext);	//遞歸釋放根節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
}

//判斷在給定的節(jié)點(diǎn)處是否可以發(fā)生剪枝
int CutP(struct NODE *pNode)
{
	int value;
	int level;

	if (pNode == NULL) return 0;
	value = pNode->value;
	level = pNode->level;
	//printf("First : %s\n" , pNode->name);
	
	while (pNode)
	{
		if(pNode->pFather == NULL)
		{
			//printf("pNode->pFather == NULL\n");
			return 0;
		}
		pNode = pNode->pFather;			
		if(level == MAX)
		{	
			//printf("level == MAX\n");
			while(pNode->pFather != NULL && (pNode->value == MAX_INT || pNode->value == MIN_INT))
			{
				//printf("MAX:pNode->name : %s\n", pNode->name);
				pNode = pNode->pFather;
			}
			if(pNode->level == MIN && value >= pNode->value)
			{
				//printf("CUT:%d\n",value);
				//printf("CUT:%d\n",pNode->value);
				//printf("CUT\n");
				return 1;
			}
			//else
			//{
				//printf("NOT:%s\n",pNode->name);
				//printf("NOT:%d\n",value);
				//printf("NOT:%d\n",pNode->value);
				//printf("NOT CUT\n");
				return 0;
			//}
			/*while(pNode!= NULL && pNode->level == MIN && value >= pNode->value && pNode->value!= MIN_INT)
			{
				return 1;
				pNode = pNode->pFather;
			}*/
		}
		if(level == MIN)
		{
			//printf("level == MIN\n");
			while(pNode->pFather != NULL && (pNode->value == MAX_INT || pNode->value == MIN_INT))
			{
				//printf("MIN:pNode->name : %s\n", pNode->name);
				pNode = pNode->pFather;
			}
			if(pNode->level == MAX && value <= pNode->value)
			{
				//printf("%s\n",pNode->level);
				//printf("CUT:%d\n",value);
				//printf("CUT:%d\n",pNode->value);
				//printf("CUT\n");
				return 1;
			}
			else 
			{
				//printf("NOT:%s\n",pNode->name);
				//printf("NOT:%d\n",value);
				//printf("NOT:%d\n",pNode->value);
				//printf("NOT CUT\n");
				return 0;
			}
			/*while(pNode!= NULL && pNode->level == MAX && value <= pNode->value && pNode->value != MAX_INT)
			{
				return 1;
				pNode = pNode->pFather;
			}*/
		}
		//pNode = pNode->pFather;
		/*if (pNode == NULL) return 0;

		if (pNode->value == MAX_INT ||
			pNode->value == MIN_INT)
		{
			return 0;	//如果祖先節(jié)點(diǎn)還沒有值，則不發(fā)生剪枝
		}

		if (level == MAX)	//對于極大節(jié)點(diǎn)
		{		
			if (value >= pNode->value)  //如果當(dāng)前值大于其祖先極小節(jié)點(diǎn)的值
			{
				return 1;	//則發(fā)生剪枝
			}
		}
		else	//對于極小節(jié)點(diǎn)
		{
			if (value <= pNode->value)	//如果當(dāng)值小于其祖先極大節(jié)點(diǎn)的值
			{
				return 1;	//則發(fā)生剪枝
			}
		}
		pNode = pNode->pFather;*/
	}	
	return 0;
}

//打印剪枝
void Cut(struct NODE *pNode, struct NODE *pChildren)
{
	printf("剪枝 %s: ", pNode->name);
	while (pChildren)
	{
		printf("%s ", pChildren->name);
		pChildren = pChildren->pNext;
	}
	printf("\n");
}

//Alpha_Beta剪枝主函數(shù)
int Alpha_Beta(struct NODE *pRoot)
{
	struct NODE *pNode = NULL;
	int value;

	//如果根節(jié)點(diǎn)沒有子節(jié)點(diǎn)，則其值就是該節(jié)點(diǎn)的指
	if (pRoot->pChildren == NULL)
	{
		return pRoot->value;
	}

	pNode = pRoot->pChildren;	
	while (pNode)
	{
		value = Alpha_Beta(pNode);	//對于根節(jié)點(diǎn)的子節(jié)點(diǎn)，遞歸計(jì)算其值
		if (pRoot->level == MAX)	//對于極大節(jié)點(diǎn)
		{
			if (value > pRoot->value)	//如果子節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的值 
			{
				pRoot->value = value;	//則用其子節(jié)點(diǎn)的值代替
				pRoot->pFrom = pNode;	//標(biāo)記該值的出處
				if (pNode->pNext && CutP(pRoot))	//如果其子節(jié)點(diǎn)還有沒有擴(kuò)展的兄弟節(jié)點(diǎn)
													//并且當(dāng)前節(jié)點(diǎn)滿足剪枝條件
				{
					Cut(pRoot, pNode->pNext);	//則進(jìn)行剪枝
					//printf("CUT MAX : %s\n", pNode->pFather->name);//debug
					return value;	//返回得到的值
				}
			}
		}
		else	//對于極小節(jié)點(diǎn)
		{
			if (value < pRoot->value)	//如果子節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值
			{
				pRoot->value = value;	//則用其子節(jié)點(diǎn)的值代替
				pRoot->pFrom = pNode;	//標(biāo)記該值的出處
				if (pNode->pNext && CutP(pRoot))	//如果其子節(jié)點(diǎn)還有沒有擴(kuò)展的兄弟節(jié)點(diǎn)
													//并且當(dāng)前節(jié)點(diǎn)滿足剪枝條件
				{
					Cut(pRoot, pNode->pNext);	//則進(jìn)行剪枝
					//printf("CUT MIN : %s\n", pNode->pFather->name);//debug
					return value;	//返回得到的值
				}
			}
		}
		pNode = pNode->pNext;	//試探下一個(gè)兄弟節(jié)點(diǎn)
	}
	return pRoot->value;
}

void main(void)
{
	FILE *pFile;
	struct NODE *pRoot;

	char filename[10];
	scanf("%s",filename);
	pFile = fopen(filename, "r");
	if (pFile == NULL)
	{
		printf("文件打開錯(cuò)誤!\n");
	}
	else
	{
		pRoot = ReadTree(pFile);	//從文件中讀入樹結(jié)構(gòu)
		fclose(pFile);
		if (pRoot == NULL)
		{
			printf("讀數(shù)據(jù)文件錯(cuò)誤!\n");
		}
		else
		{
			Alpha_Beta(pRoot);	//對該樹進(jìn)行Alpha_Beta剪枝
			PrintTreeRoot(pRoot);
			FreeTree(pRoot);	//釋放動(dòng)態(tài)產(chǎn)生的樹
		}
	}
}