Description


给定一颗二叉树的先序序列，求该二叉树的高。


Input

输入包括两部分第一部分：一个正整数n，代表有n颗二叉树第二部分：包括n行，每行代表一颗二叉树的先序遍历序列，空指针用字符^占位
Output
n行，每行一个整数，代表对应二叉树的高度


Sample Input

2
ABC^^^^
AB^^^

Sample Output

3
2

求二叉树的高是二叉树的基本操作，不再赘述；
需要注意的是：
开始先输入N，代表N组数据，N后会输入一个“\n”，需要getchar()一下；
同样的，每输入一组数据后，都会有个“\n”,需要getchar()一下；

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
	char ch;
	struct node *Lchild;
	struct node *Rchild;
}Btree,*Ptree;
void Q_CreatTree(Ptree *T);
void Q_Traverse(Ptree T);
int TreeDeep(Ptree T); 
int main(void)
{
	int flag;
	scanf("%d",&flag);
	getchar();//注意换行符 
	while(flag--)
	{
	    Ptree T;
	    Q_CreatTree(&T);//前序遍历创建二叉树
	    getchar();//吞掉换行符 
		int deep=TreeDeep(T);
	    printf("%d\n",deep);
	}
}
void Q_CreatTree(Ptree *T)//前序遍历建立二叉树 
{
	char str;
	str=getchar();
	if(str=='^')
	{
		*T=NULL;
	}
	else
	{
		(*T)=(Ptree)malloc(sizeof(Btree));
		(*T)->ch=str;
		Q_CreatTree( &( (*T)->Lchild ) );
		Q_CreatTree( &( (*T)->Rchild ) );
	}
}
int TreeDeep(Ptree T)//求树的深度
{
	int n=0;
	if(T)
	{
		int L=TreeDeep(T->Lchild);
		int R=TreeDeep(T->Rchild);
		n=L+1>R+1?L+1:R+1;
	}
	return n;
 }