判断一个二叉树是否是平衡的？

平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1。

问题：判断一个二叉排序树是否是平衡二叉树这里是二叉排序树的定义解决方案：根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。首先编写一个计算二叉树深度的函数，利用递归实现。

下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数：

#include
#include
#include
#include
using namespace std;
typedef int datatype;
int countLeaves,nodes;
typedef struct node
{
    datatype data;
    struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;

    void createbintree(bintree *t)
    {
    //输入二叉树的先序遍历序列，创建二叉链表
        int ch;
        //ch=getchar();
        scanf("%d",&ch);
        if(ch==-1)
            *t=NULL;//如果读入空格字符，创建空树，T是指向指针的指针,*t就相当于一个bintree指针，专门指向bintnode；
        else
        {
            (*t)=(bintnode*)malloc(sizeof(bintnode));
            (*t)->data=ch;
            createbintree(&(*t)->lchild);//根据先序遍历，继续创建左子树，让客户端继续输入
            createbintree(&(*t)->rchild);//创建完左子树，继续创建右子树
        } //递归调用，自动返回
    }



    //求树的深度
    int deepLength(bintree t)
    {
        if(t==NULL)
            return 0;
        //递归返回左右子树较大的就是
        else
        {
            int ldeep=deepLength(t->lchild);
            int rdeep=deepLength(t->rchild);
            if(ldeep
                return rdeep+1;
            else
                return ldeep+1;
        }
    }

    //递归，逐个结点判断,返回值,不平衡:0,平衡:1
    int isBalance(bintree t)
    {
        if(t==NULL)
            return 1;//这个点是null没有左右子树,认为是平衡
        int ldepth=deepLength(t->lchild);//左子树的高度
        int rdepth=deepLength(t->rchild);//右子树的高度
        int dis=ldepth-rdepth;
        if(dis>1|| dis<-1)
            return 0;//不平衡,直接跳出递归,返回0
        else
            return (isBalance(t->lchild) && isBalance(t->rchild)) ;//平衡,继续看它的左右子树
    }

int main()
{

/*
这里的输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,
就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个
元素,那么一定要有n+1个#才会结束迭代过程.
*/
    bintree t=NULL;
    createbintree(&t);//这样才能改变T，指向指针的指针

    int height=deepLength(t);
    printf("\n树的高度: %d",height);
    if(isBalance(t))
        printf("\n平衡");
    else
        printf("\n不平衡");

    printf("\n");
    getchar();
    return 0;
}



/*
平衡：
1 2 4 8 -1 -1 9 -1 -1 5 10 -1 -1 11 -1 -1 3 6 -1 -1 7 -1 -1

树的高度: 4
平衡
Press any key to continue


不平衡:
1 2 -1 4 8 -1 -1 9 -1 -1 5 10 -1 -1 11 -1 -1
树的高度: 4
不平衡
Press any key to continue
*/