假设以二叉链表作为二叉树的存储结构，试编写一个求树的高度的算法

#include
#include

#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;

typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;

status treecreated=FALSE;
int leafcount=0;

status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);

void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout<<"===========二叉树演示程序==============="< do
{
cout<<"1：创建一个二叉树，按先序遍历结果输入，空用0表示 "< cout<<"2：先序遍历二叉树，递归方式遍历二叉树 "< cout<<"3：求叶子数"< cout<<"4：计算二叉树的高度"< cout<<"5: 树进行左右翻转"< cout<<"0：退出"< cout<<"-------请输入你的选择:"< cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"< break;
};
cout<<"请输入代表树的数字："< flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已经建立了一棵树了！"< treecreated=TRUE;
}
break;

case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"< break;
}
cout<<"先序遍历顺序:"< preordertraverse(bt);
cout< break;

case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"< break;
}
leafcounts(bt);
cout<<"树的叶子数:"< cout< break;

case 4:
int h;
h=height(bt);
cout<<"树的高度:"< break;

case 5:
swap(&bt);
cout<<"树已经翻转！！！"< break;

case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 谢谢 再见了！！！"<}
//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0) //输入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申请空间
(*t)->data=ch; //把数据传给他
createbitree(&(*t)->lchild); //左孩子重新进入创建函数
createbitree(&(*t)->rchild); //右孩子重新进入创建函数
}
return OK;
}

//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
cout<data<<" "; //先把头结点输出
preordertraverse(t->lchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}

int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild)+1; //最下面的左孩子加一
hr=height(t->rchild)+1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比较谁大就取谁
}

void swap(bitree *t) //进行左右翻转
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p为中间变量
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}

void leafcounts(bitree t) //求叶子数
{
if(t) //如果不为空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都为空 表明是叶子
leafcount++;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}

int length(BiTree T)
{
int h1,h2;
if(T==NULL) return 0;
if(T->lchild==NULL && T->rchild==NULL) return 1;
h1=length(T->lchild);
h2=length(T->rchild);
return h1>=h2?h1:h2;
}

BiTree Find(BiTree T,ElemType x) //该函数返回给定值的结点的指针
{
BiTree t;
if(T==NULL) return NULL;
if(T->data==x) return T;
if(t=Find(T->lchild)) return t;
if(t=Find(T->rchild)) return t;
return NULL;
}

#include
using namespace std;
template
struct BiNode
{T data;BiNode*lchild,*rchild;};
template
class BiTree
{
public:
BiTree(){root=Creat(root);}
void PreOrder(){PreOrder(root);}
int Deepth(){ return Deepth(root);}
int Empty();
private:
BiNode*root;
BiNode*Creat(BiNode*bt);
int Deepth(BiNode*bt);
};
template
BiNode*BiTree::Creat(BiNode*bt)
{ char ch;
cin>>ch;
if(ch=='#')bt=NULL;
else{
bt=new BiNode;bt->data=ch;
bt->lchild=Creat(bt->lchild);
bt->rchild=Creat(bt->rchild);
}
return bt;
}
template
int BiTree::Empty()
{
if(root==NULL)return 1;
else return 0;
}
template
int BiTree::Deepth(BiNode*bt)//求深度的算法
{ int nl,nr;
if(bt==NULL) return 0;
else
{
nl=Deepth(bt->lchild);
nl++;
nr=Deepth(bt->rchild);
nr++;
if(nl>nr)return nl;
else return nr;
}
}
int main()
{ int t;
while(1)
{
BiTree Bt;
cout< t=Bt.Empty();
if(t==1)break;
}
return 0;
}

int BTNodeDepth (BTNode *t)
{
int lchildh, rchildh;
if (t == NULL)
return 0;
else
{
lchildh = BTNodeDepth (t->lch);
rchildh = BTNodeDepth (t->rch);
return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
}
}