求二叉树的深度和宽

Description

Input

包含多组测试数据。每组测试数据一行，给出二叉树的先序遍历序列（至少1个结点）。

Output

输出二叉树的繁茂程度。

Sample Input

Sample Output

#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<string>#include<algorithm>#include<stack>#include<queue>#include<map>#include<iostream>using namespace std;typedef struct BiTNode{    char d;    struct BiTNode *l;    struct BiTNode *r;}*BiTree,BiTreeNode;char ch;bool flag;void CreatBiTree( BiTree &T)//创建二叉树{    char tmp;    if( flag)        scanf("%c",&tmp);    else    {        tmp = ch;        flag = 1;    }    if( tmp == '^')        T = NULL;    else    {        T = new BiTreeNode;        T->d = tmp;        CreatBiTree(T->l);        CreatBiTree(T->r);    }}int getdepth( BiTree T)//获取二叉树的深度{    if( T == NULL)    {        //PRintf("t=null/n");        return 0;    }    else    {        //printf("tt/n");        int left = getdepth(T->l);        int right = getdepth(T->r);        return 1+max(left,right);    }}int getwidth( BiTree T)//求二叉树的宽度{    if( T == NULL)        return 0;    queue<BiTree> q;    q.push(T);    int maxwidth = 1;    while( true)    {        int len = q.size();        if( len == 0)            break;        while( len > 0)        {            BiTree t = q.front();            q.pop();            len--;            if( t->l != NULL)                q.push( t->l);            if( t->r != NULL)                q.push( t->r);        }        if( q.size() > maxwidth)            maxwidth = q.size();    }    return maxwidth;}int main(){    while( ~scanf("%c",&ch))    {        if( ch == '/n')            continue;        BiTree T = NULL;        flag = 0;        CreatBiTree( T);        int a = getdepth( T);        int b = getwidth( T);        //printf("a = %d, b = %d/n",a,b);        printf("%d/n",a*b);    }    return 0;}