检验平衡二叉树

2014-02-23平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。判断其是否是平衡二叉树的代码：

#include <iostream>

#include<cmath>

using namespace std;

typedef int datatype;

typedef struct node {     datatype data;    

struct node *lchild,*rchild; }binnode,*bintree;

void CreateBTree(bintree &t)//按照先序方式 建立二叉树

{     int ch;     cin>>ch;   

  if(ch==-1)     t=NULL;    

else     {         t=new binnode;//

        t->data=ch;       

     CreateBTree(t->lchild);      

   CreateBTree(t->rchild);

    } }

int deepBTree(bintree t)//二叉树的深度

{     if(t==NULL)     return 0;    

else {     int lleng=deepBTree(t->lchild);   

  int rleng=deepBTree(t->rchild);   

  if(lleng<rleng)     return rleng+1;     else     return lleng+1;

}

}

int balanceBTree(bintree t)//树是否平衡

{     if(t==NULL)     return 1;    

      else{     int lbal=deepBTree(t->lchild);   

      int rbal=deepBTree(t->rchild);

     if(fabs(lbal-rbal)>1)    

       return 0;    

     else return (balanceBTree(t->lchild)&&balanceBTree(t->rchild));

}

}

int main()

{

    bintree t;    

   CreateBTree(t);   

  cout<<"the height of the tree \t  "<<deepBTree(t)<<endl;    

if(balanceBTree(t))     cout<<"balance!";    

else cout<<"unbalance!";    

//cout << "Hello world!" << endl;    

return 0;

}

检验平衡二叉树

原文：http://www.cnblogs.com/yinhitter123/p/3562533.html