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

参考答案：因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左(当b=1时)或右(当b=-1时)向下查找。
　　[算法描述]
　　int Height(BSTree t)
　　// 求平衡二叉树t的高度
　　{level=0;p=t;
　　while(p)
　　{level++; // 树的高度增1
　　if(p->bf<0)p=p->rchild;//bf=-1 沿右分枝向下
　　//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义
　　else p=p->lchild; //bf>=0 沿左分枝向下
　　}//while
　　return (level);//平衡二叉树的高度
　　} //算法结束