#include "stdafx.h"
#include "stdlib.h"
#include "string.h"

#define MAX 100
typedef char Elemtype;

typedef struct BTNODE
{
    Elemtype data;
    BTNODE *left;
    BTNODE *right;
} BTNode;

void CreateBTNode(BTNode *&root, char *str)
{
    BTNode *p = NULL;
    BTNode *st[MAX] = {NULL};
    int top = -1;
    int i = 0;
    int k = 0;
    char ch = str[i];

    while ('\0' != ch)
    {
        switch (ch)
        {
        case '(':
            {
                top++;
                st[top] = p;
                k = 1;
                break;
            }
        case ')':
            {
                top--;
                break;
            }
        case ',':
            {
                k = 2;
                break;
            }
        default:
            {
                p = (BTNode*)malloc(sizeof(BTNode));
                if (NULL == p)
                {
                    return;
                }
                p->data = ch;
                p->left = p->right = NULL;

                if (!root)
                {
                    root = p;
                } 
                else
                {
                    switch (k)
                    {
                    case 1:
                        st[top]->left = p;
                        break;
                    case 2:
                        st[top]->right = p;
                        break;
                    }
                }
                break;
            }
        }
        ch = str[++i];
    }
}

void DispBTNode(BTNode *&root)
{
    if (root)
    {
        printf("%c", root->data);
        if (root->left || root->right)
        {
            printf("(");
            DispBTNode(root->left);
            if (root->right)
            {
                printf(",");
                DispBTNode(root->right);
            }
            printf(")");
        }
    }
}

int GetBTNodeDepth(BTNode *&root)
{
    int iLeftDepth  = 0;
    int iRightDepth = 0;

    if (!root)
    {
        return 0;
    }

    iLeftDepth  = GetBTNodeDepth(root->left);
    iRightDepth = GetBTNodeDepth(root->right);
    return (iLeftDepth > iRightDepth ? (iLeftDepth+1):(iRightDepth+1));
}

void PreOrder(BTNode *&root)
{
    if (root)
    {
        printf("%c\t", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void PreOrder1(BTNode *&root)
{
    int top = -1;
    BTNode *p = NULL;
    BTNode *st[MAX] = {NULL};

    if (root)
    {
        top++;
        st[top] = root;

        while (top > -1)
        {
            p = st[top];
            top--;
            printf("%c\t", p->data);
            if (p->right)
            {
                top++;
                st[top] = p->right;
            }
            if (p->left)
            {
                top++;
                st[top] = p->left;
            }
        }
    }
}

void InOrder(BTNode *&root)
{
    if (root)
    {        
        PreOrder(root->left);
        printf("%c\t", root->data);
        PreOrder(root->right);
    }
}

void PostOrder(BTNode *&root)
{
    if (root)
    {        
        PreOrder(root->left);        
        PreOrder(root->right);
        printf("%c\t", root->data);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    BTNode *root = NULL;
    char *str = "A(B(D(,G)),C(E,F))";
    CreateBTNode(root, str);
    DispBTNode(root);
    printf("\r\n");
    printf("The BTree's Depth = %d\r\n", GetBTNodeDepth(root));

    printf("PreOrder:\r\n");
    PreOrder(root);
    printf("\r\n");

    printf("InOrder:\r\n");
    InOrder(root);
    printf("\r\n");

    printf("PostOrder:\r\n");
    PostOrder(root);
    printf("\r\n");
    return 0;
}