#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <iostream>
#include <stack>
using namespace std;
#define NULL 0
typedef struct BiTNode      //定义数据结构
{
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode,*BiTree;
BiTree create(BiTree T)   //建立二叉树
{
    char ch;
    ch = getchar();
    if (ch==' ')
        T = NULL;
    else
        {
            if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
                printf("Error!");
            T->data = ch;
            T->lchild = create(T->lchild);
            T->rchild = create(T->rchild);
        }
    return T;
}
void preorder(BiTree T)
{
    //先序遍历二叉树
    if (T)
        {
            printf("%c",T->data);
            preorder(T->lchild);
            preorder(T->rchild);
        }
}
void midview(BiTree T)   //非递归中序遍历
{
    stack<BiTree> Stack;
    if (!T)
        {
            printf("empty tree\n");
            return;
        }
    while (T||!Stack.empty())
        {
            while (T)
                {
                    Stack.push(T);
                    T = T->lchild;
                }
            T = Stack.top();
            Stack.pop();
            printf("%c",T->data);
            T = T->rchild;
        }
}
void lastview(BiTree T)    //后续遍历
{
    if (T)
        {
            lastview(T->lchild);
            lastview(T->rchild);
            printf("%c",T->data);
        }
}
int sumleaf(BiTree T)
{
    //求叶子节点的个数
    int sum = 0,m,n;
    if (T)
        {
            if ((!T->lchild)&&(!T->rchild))
                sum++;
            m = sumleaf(T->lchild);
            sum = sum + m;        //左子树的叶子节点数目m
            n = sumleaf(T->rchild);
            sum = sum + n;        //右子树的叶子节点数目n
        }
    return sum;
}
int sumdutwo(BiTree T)
{
    //求度为2节点的个数
    int sum2 = 0,a,b;
    if (T)
        {
            if ((T->lchild)&&(T->rchild))
                sum2++;
            a = sumdutwo(T->lchild);
            sum2 = sum2 + a;
            b = sumdutwo(T->rchild);
            sum2 = sum2 + b;
        }
    return sum2;
}
int depth(BiTree T)   //求二叉树的深度
{
    int dep = 0,depl,depr;
    if (!T) dep = 0;
    else
        {
            depl = depth(T->lchild);
            depr = depth(T->rchild);
            dep = 1 + (depl>depr?depl:depr);
        }
    return dep;
}
int main()
{
    BiTree T;
    int sum,sum2,dep;
    T = create(T);
    printf("二叉树建立成功!\n");
    printf("先序遍历\n");
    preorder(T);
    printf("\n");
    printf("中序遍历\n");
    midview(T);
    printf("\n");
    printf("后序遍历\n");
    lastview(T);
    printf("\n");
    printf("叶子节点数目\n");
    sum = sumleaf(T);
    printf("%d\n",sum);
    printf("度为2的节点数目\n");
    sum2 = sumdutwo(T);
    printf("%d\n",sum2);
    printf("树的深度\n");
    dep = depth(T);
    printf("%d\n",dep);
    return 0;
}