描述

假设一棵平衡二叉树的每个结点都标明了平衡因子b，设计一个算法，求平衡二叉树的高度。

输入

多组数据，每组数据一行，为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“#”时，输入结束。

输出

每组数据输出一行，为平衡二叉树的高度。

输入样例 1

110###0##
1110###0##10###
#

输出样例 1

3
4

//平衡二叉树高度的计算 
#include<iostream>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T){  
	//按先序次序输入二叉树中结点的值 创建二叉链表表示的二叉树 
    char ch;
	cin>>ch;
	if(ch=='#') T = NULL;         //递归结束 空树 
	else{                         //递归创建二叉树 
		T = new BiTNode;          //生成根节点
		T->data = ch;             //根结点数据域置ch 
		CreatBiTree(T->lchild);   //递归创建左子树 
		CreatBiTree(T->rchild);   //递归创建右子树 
	} 
} 
void CreatBiTree(BiTree &T,char ch){  
	//按先序次序输入二叉树中结点的值 创建二叉链表表示的二叉树 
	if(ch=='#') T = NULL;         //递归结束 空树 
	else{                         //递归创建二叉树 
		T = new BiTNode;          //生成根节点
		T->data = ch;             //根结点数据域置ch 
		CreatBiTree(T->lchild);   //递归创建左子树 
		CreatBiTree(T->rchild);   //递归创建右子树 
	} 
} 
int Depth(BiTree T)
{
	if(!T)
		return 0;
	else if(!T->lchild&&!T->rchild)
		return 1;
	return Depth(T->lchild)>=Depth(T->rchild)?Depth(T->lchild)+1:Depth(T->rchild)+1;
}
int main()
{
    char ch;
	while(cin>>ch&&ch!='#')
	{
	  	BiTree T;
		CreatBiTree(T,ch);
		cout<<Depth(T)<<endl;
	}
	return 0;
}