求二叉树的高度(递归和非递归)
假设二叉树采用二叉链表存储结构，设计一个算法求二叉树的高度。
递归：
int getTreeHight(BiTree T){
if(T==NULL){
return 0;
}else {
int lh = getTreeHight(T->lchild);
int rh = getTreeHight(T->rchild);
return (lh>rh?lh:rh)+1;
}
}
时间复杂度O(n)；空间复杂度O（n）
非递归
思想：先获得当前层的节点个数，遍历完队列中的节点就是处理完该层。这时候队列中所有节点就是下一层的。每处理一层，层数+1
int getTreeHight(BTree T){
//树空
if(T==NULL){
return 0;
}
//初始化队列
BTiree Q[MaxSize];
int rear=-1,front=-1;
Q[++rear]=T;//根入队
BTiree p;
int last=0;//指向当前层最后一个结点
int count=0;//记录层数
while(front<rear){
p=Q[++front];
if(p->lchild){
Q[++rear]=p->lchild;
}
if(p->rchild){
Q[++rear]=p->rchild;
}
//当前层结点访问完毕，rear刚好指向下一层的最后一个结点
if(front==last){
count++;
last=rear;//指向下一层最后一个结点
}
}
return count;
}时间复杂度O(n)；空间复杂度O（n）