树的泛滥操作(2014华为校园招聘 机试 第三题 )

树的众多操作(2014华为校园招聘 机试 第三题 )

这次的题目是在http://blog.csdn.net/wang603603/article/details/11394915看到的，但是我觉得他完成的不是很好，容错性或则健壮性感觉欠佳，便自己写了一个，因为是华为的机试题，所以每次写起来都特别有激情。希望能进呀...

问题描述：

输入一个二叉树 格式为“单个字符+节点所在层次” 
比如根节点所在层次是1，它的两个子树都是2. 节点排列从左到右，然后再输入其中的某个（些）节点，
求得其深度。
第三题还有条件：层次不超过9层
输入：a1b2c2d3e3f3    ab
输出：3 2

ps：因为是在一个文档里写了很多代码，头文件和命名空间就不引了，还有关于哪个层次不超过9的条件我就自动忽略啦...树的操作真的很重要...一定要掌握，递归和非递归，链式存储和线性存储...

typedef struct Tree
{
	char data;
	struct Tree *lchild;
	struct Tree *rchild;
}Tree;
//创建树
Tree *BuildTree(char a[])
{
	assert(a != NULL);
	assert(strlen(a) >= 2);
	Tree *head;
	list<Tree *> lstTree;
	list<Tree *>::iterator p;
	int i = 0;
	while(i < strlen(a))
	{
		if(i == 0)
		{
			head = (Tree*)malloc(sizeof(Tree));
			head->data = a[i];
			head->lchild = NULL;
			head->rchild = NULL;
			lstTree.push_back(head);
			p = lstTree.begin();
			i+=2;
			continue;
		}
		char record = a[i+1];
		if(a[i+1] != a[i-1]+1)//格式有错误
			return NULL;
		list<Tree *>::iterator start;//表示此层的第一个元素
		int time = 1;//记录当前层次添加节点的次数
		while(record == a[i+1])//record记录层次，如果层次有变化则跳出循环
		{//这一段代码逻辑比较复杂
			Tree *temp;
			temp = (Tree*)malloc(sizeof(Tree));
			temp->data = a[i];
			temp->lchild = NULL;
			temp->rchild = NULL;
			lstTree.push_back(temp);
			if((*p)->lchild == NULL)
			{
				(*p)->lchild = temp;
			}
			else if((*p)->rchild == NULL)
			{
				(*p)->rchild = temp;
			}
			else
			{
				++p;
				(*p)->lchild = temp;
			}
			i+=2;
			if(time == 1)
			{//为了保证每一次P指针都指向下一层的第一个节点
				start = lstTree.end();
				start--;
				time++;
			}
			if(p == start)//超过这一层最多节点数，输入字符串违法
				return NULL;
		}
		p = start;
	}
	return head;
}
//删除该树
void DeleteTree(Tree* t)
{
	assert(t != NULL);
	if(t->lchild != NULL)
		DeleteTree(t->lchild);
	if(t->rchild != NULL)
		DeleteTree(t->rchild);
	free(t);
}
//得到某个节点的高度
int GetHigh(Tree *t)
{
	assert(t != NULL);
	if(t->lchild == NULL && t->rchild == NULL)
		return 1;
	int high1 = 1,high2 = 1;
	if(t->lchild != NULL)
		high1 += GetHigh(t->lchild);
	if(t->rchild != NULL)
		high2 += GetHigh(t->rchild);
	return high1>high2?high1:high2;
}
//题目要求功能函数
void SelectNodeHigh(Tree* t,char data,vector<Tree *> &vet)
{//这样保证可能存在同名节点都可以全部找出来
	assert(t != NULL);
	if(t->data == data)
		vet.push_back(t);
	if(t->lchild == NULL && t->rchild == NULL)
		return ;
	if(t->lchild != NULL)
		SelectNodeHigh(t->lchild,data,vet);
	if(t->rchild != NULL)
		SelectNodeHigh(t->rchild,data,vet);
}

int main(int argc, char* argv[])
{
	Tree *head = BuildTree("a1a2c2d3e3a4"); //创建树
	cout<<GetHigh(head)<<endl;
	vector<Tree *> vet;
	SelectNodeHigh(head,'a',vet);
	for(vector<Tree *>::iterator p = vet.begin();p != vet.end();++p)
		cout<<GetHigh(*p)<<endl;
	DeleteTree(head);//销毁树
	return 0;
}