机试算法讲解： 第18题 大家一起猜，这两个序列是同一个二叉搜索树的序列码？

/*
问题:二叉搜索树。判断2个序列是否为同一个二叉搜索树序列
输入:
开始一个数n,(1<=n<=20)表示有n个需要判断，n = 0输入结束。接下去一行是一个序列，序列茬高度小于10,包含(0-9)的数字，没有重复数字，
根据这个序列可以构造出一颗二叉搜索树
接下去去n行有n个序列，每个序列格式跟第一个序列一样，请判断2个序列是否能组成同一颗二叉搜索树

输出:如果序列相同，则输出YES,否则输出NO

输入:
2
567432
543267
576342
0
输出:
YES
NO

思路:
对输入的数字序列构建二叉排序树，对其进行前序和中序遍历，比较遍历结果是否相同，若相同则说明两棵二叉排序树相同，否则不同

关键:
1判断两棵树是否完全相同，采用判断前序和中序序列相同即可
2void *memset(void* buffer,int ch,size_t count)
3在解决计数器的问题时，由于C语言没有引用，只能采用指针，int size1 = 0,int *size = & size1的方式
4输入的字符转换为数字，采用遍历字符数组，字符-'0'形式,将数字转换为字符数组时，采用+'0'形式，并且注意要使结束符为'\0'
*/

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

typedef struct Node
{
	Node* lchild;
	Node* rchild;
	//char iData;//这边还是只能用int类型
	int iData;
}Node;

Node Tree[100];
int loc = 0;
int mid = 0;
int iCount = 0;//不行，必须用指针的方式
int *size;//便于每次进行更改，其实用引用也可以

//关键这里必须的构造必须用的iCount有问题只能确保用一次
void frontOrder(Node* T,char* sFront)
{
	//printf("%d",T->iData);
	//static int iCount = 0;
	//这边构造字符串时，加上'0'
	//sFront[iCount++] = T->iData ;
	sFront[(*size)++] = T->iData + '0';
	//易错,添加结尾符号
	sFront[(*size)] = '\0';
	if(T->lchild!=NULL)
	{
		frontOrder(T->lchild,sFront);
	}
	if(T->rchild!=NULL)
	{
		frontOrder(T->rchild,sFront);
	}
}

void inOrder(Node* T,char* sMid)
{
	//static int iMid = 0;
	if(T->lchild!=NULL)
	{
		inOrder(T->lchild,sMid);
	}
	//printf("%d",T->iData);
	//sMid[iMid++] = T->iData;//易错，添加数字时，用'0'
	sMid[(*size)++] = T->iData + '0';
	//添加结尾父
	sMid[(*size)] = '\0';
	if(T->rchild!=NULL)
	{
		inOrder(T->rchild,sMid);
	}
}

Node* createNode()
{
	//static int iCount = 0;
	Tree[loc].rchild = Tree[loc].lchild = NULL;
	return &Tree[loc++];
}

Node* insertNode(Node* T,int x)
{
	if(NULL==T)
	{
		T = createNode();
		T->iData = x;
		//易错，这里必须加上返回，否则往下走
		return T;
	}
	//插入左子树
	else if(x < T->iData)
	{
		//易错:这里应该插入的就是T->lchild，本来左孩子为空，经此操作后不再为空
		T->lchild = insertNode(T->lchild,x);
	}
	else if(T->iData < x)
	{
		T->rchild = insertNode(T->rchild,x);
	}
	return T;
}

int main(int argc,char* argv[])
{
	char sData[10];
	int iNum;
	//Node Tree[100];
	Node* root = NULL;
	while(EOF!=scanf("%d",&iNum) && iNum!=0)
	{
		scanf("%s",sData);
		//根据输入的起始序列，建立前序和中序结果。这个结果建立在累加的基础上
		char sFront[10],sMid[10];
		//关键输入的是字符串，用's' - '0'的方式
		int i = 0;
		//构造二叉排序树
		while('\0'!=sData[i])
		{
			//易错，这里将字符转换为数字采用-'0'方式
			root = insertNode(root,sData[i++] - '0');
		}
		//进行前序遍历
		//*size = 0;//不能用这个指向0,而是只能用一个0的数，然后取地址
		int size1 = 0;
		size = &size1;
		frontOrder(root,sFront);
		//最后一个字符要加结束符
		printf("原始前序:%s\n",sFront);
		int size2 = 0;
		size = &size2;
		inOrder(root,sMid);
		printf("原始中序:%s\n",sMid);
		char sFront2[10],sMid2[10];
		for(int k = 0 ; k < iNum ; k++)
		{
			//清空上一次的数组
			memset(sData,0,sizeof(sData));
			memset(sFront2,0,sizeof(sFront2));
			memset(sMid2,0,sizeof(sMid2));
			scanf("%s",sData);
			int j = 0;
			Node* root2 = NULL;
			while('\0'!=sData[j])
			{
				root2 = insertNode(root2,sData[j++] - '0');
			}
			int size3 = 0;
			size = &size3;
			frontOrder(root2,sFront2);
			int size4 = 0;
			size = &size4;
			inOrder(root2,sMid2);
			printf("当前前序是:%s\n",sFront2);
			printf("当前中序是:%s\n",sMid2);
			if(strcmp(sFront,sFront2)==0 && strcmp(sMid,sMid2)==0)
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
	}
	getchar();
	return 0;
}