题目描述:利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法。
分析: 设置二叉树的平衡标记为balance,若 balance 为 1,则是平衡二叉树,若为0,则不是。
void Judge_AVL(BiTree T,int &balance,int &h){
int bl = 0,br = 0,hl = 0,hr = 0;
if(T == NULL){
balance = 1;
h = 0;
}
else
if(T->lchild == NULL && T->rchild == NULL){
balance = 1;
h = 1;
}
else{
Judge_AVL(T->lchild,bl,hl);
Judge_AVL(T->rchild,br,hr);
if(abs(hl - hr) < 2)
balance = bl && br;
else
balance = 0;
}
}