判断二叉树是否平衡

                         平衡二叉树
               时间限制: 1 Sec  内存限制: 128 MB

题目描述
所谓平衡二叉树就是￥￥￥@！#@￥##@！&&（水星文，若看不懂请跳转到下一题）… 你的任务判断输入的二叉树是否为平衡二叉树，是则输出Yes，否则输出No。
输入
每行是一棵二叉树的带虚结点（#）表示的前序遍历序串，长度不超过2000。每个结点为一个小写字母或一个数字。
输出
对于每行输入的二叉树，如果是平衡二叉树则输出Yes，否则输出No
样例输入

 #
 abc####

样例输出

 Yes
 No

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#define OK 1
#define ERROR 0
int sum=0;
typedef char ElemType;
typedef struct BiTNode          /*定义树的节点*/
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree p;
BiTree CreateBiTree(BiTree T,char a[])  /*构建二叉树*/
{
    char d;
    d=a[sum];                           /* 将新带入的数组下一个元素赋给d用来判断是否存在子*/
    if(d=='#')                           /*输入出现#跳回上层*/
    {
        T=NULL;
          sum++;
        return T;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));  /*新节点*/
        T->data=d;
        sum++;
        T->lchild=CreateBiTree(T->lchild,a);/*向左子构建*/
        T->rchild=CreateBiTree(T->rchild,a);
        return T;       /*返回到最上层返回主函数以树的根*/
    }
}
int TreeDeep(BiTree T)
{
    int high=0;         /*初始化为1*/
    if(T)
    {
        int lchilddeep=TreeDeep(T->lchild);                             /*向左到底*/
        int rchilddeep=TreeDeep(T->rchild);                             /*向右到底*/
        high=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;          /*左右比较留下最大的加1*/
    }
    return high;
}
int Balance(BiTree T)   /*判断是否平衡*/
{
    if(T==NULL)         /*如果根为空平衡*/
        return OK;
    int lefthigh=TreeDeep(T->lchild); /*算左右深度*/
    int righthigh=TreeDeep(T->rchild);
    if(abs(lefthigh-righthigh)>1)  /*不平衡*/
                return ERROR;
    else
                return Balance(T->lchild)&&Balance(T->rchild); /*向左右子延伸递归*/
}
int main()
{
    int s,i,high;
    char a[2005];
    while(gets(a))
    {
        sum=0;
        if(a[0]=='#')
            printf("Yes\n");
        else
        {
            p=CreateBiTree(p,a);
            s=Balance(p);
            if(s==0)
                printf("No\n");
            if(s==1)
                printf("Yes\n");
        }
    }
}

建立二叉树

T=(BiTree)malloc(sizeof(BiTNode)); /新节点/
T->data=d;
sum++;
T->lchild=CreateBiTree(T->lchild,a);/向左子构建/
T->rchild=CreateBiTree(T->rchild,a);
return T; /返回到最上层返回主函数以树的根/

迭代将输入的数组插入当第一个数定为根，下一个数定为根的左子
如果遇到#则返回上一级尝试右指一直到所有完成。

计算深度

int TreeDeep(BiTree T)
{
int high=0; /初始化为1/
if(T)
{
int lchilddeep=TreeDeep(T->lchild); /向左到底/
int rchilddeep=TreeDeep(T->rchild); /向右到底/
high=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1; /左右比较留下最大的加1/
}
return high;
}

左右到底每次迭代加一比较最后左右子大小取较大
拆开high=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;

if(lchilddeep>rchilddeep)
return lchilddeep+1;
else
return rchilddeep+1;
}

比较平衡

int Balance(BiTree T) /判断是否平衡/
{
if(T==NULL) /如果根为空平衡/
return OK;
int lefthigh=TreeDeep(T->lchild); /算左右深度/
int righthigh=TreeDeep(T->rchild);
if(abs(lefthigh-righthigh)>1) /不平衡/
return ERROR;
else
return Balance(T->lchild)&&Balance(T->rchild); /向左右子延伸递归/
}

从根开始往下递归比较