假设一棵平衡二叉树的每个结点都标明了平衡因子b 试设计一个算法 求平衡二叉树的高度。
结点,因子,算法
已帮助 人
-
正确答案：int Height(BSTree t) ／／求平衡二叉树t的高度 {level=0；P=t； while(P) {level++；／／树的高度增1 if(p一>bf<0)P=p->rchild；／／bf=-1沿右分枝向下 else P=p->lchild；／／bf>=0沿左分枝向下 }／／while return(level)；／／平衡二叉树的高度 }／／算法结束
此题考查的知识点是平衡二叉树的算法。因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分支向下查找，若b不为0，则沿左(当b=1时)或右(当b=一1时)向下查找。