// BTree1.cpp : 定义控制台应用程序的入口点  
    //1.使用广义表构造二叉树  
    //2.程序默认数据为：a(b(c,d),e(,f))  
    //3.三种遍历使用非递归，求树的高度、查找节点使用递归  
      
      
    #include "stdafx.h"  
    #include<iostream>  
    #include<stack>  
    using namespace std;  
      
      
    #define ElemType char  
    #define Status int  
    #define OK 0  
    #define ERROR 1  
    #define MAX_LEN 100  
    typedef struct BTnode  
    {  
        ElemType date;  
        BTnode *lchild,*rchild;  
    }BTnode,*BTree;  
    typedef enum{L,R} tagtype;  
    typedef struct   
    {  
        BTree ptr;  
        tagtype tag;  
    }stacknode;  
      
      
    Status creat(BTree &T,char *str);//根据str创建二叉树T  
    Status visit(BTree e);//访问节点，打印date  
    Status preorder(BTree T);//先序遍历，非递归  
    Status inorder(BTree T);//中序遍历，非递归  
    Status postorder(BTree T);//后序遍历，非递归  
    Status getTreeHeight(BTree T,int &H);//求树的高度，递归  
    Status findNode(BTree T,ElemType e,BTnode &bt);//求树中结点data值为e的节点，并返回此节点的引用  
      
      
    int _tmain(int argc, _TCHAR* argv[])  
    {  
        int i,height,flag;  
        BTree T;  
        BTnode bt;  
        char *buffer,e;  
        printf("想输入自己的数据请输入--1or采用默认数据请输入--2：");  
        cin>>flag;  
        if(flag==1)  
        {  
            buffer=(char*)malloc(MAX_LEN*sizeof(char));  
            scanf("%s",buffer);  
        }  
        else if(flag==2)  
            buffer="a(b(c,d),e(,f))";  
        T=NULL;  
        creat(T,buffer);//创建树  
        //先序遍历  
        printf("先序遍历:");  
        preorder(T);  
        //中序遍历  
        printf("\n中序遍历:");  
        inorder(T);  
        //后序遍历  
        printf("\n后序遍历:");  
        postorder(T);  
        //求树的高度  
        height=0;  
        getTreeHeight(T,height);  
        printf("\n此树的高度为：%d\n",height);  
        //查找date值为e的节点并返回节点的引用  
        printf("请输入要查找的字符值：");  
            cin>>e;  
        findNode(T,e,bt);  
        if(bt.date==NULL)  
            printf("未找到");  
        else  
            printf("找到他了：%c",bt.date);  
        printf("\n");  
        system("pause");  
        return 0;  
    }  
      
      
    Status creat(BTree &T,char *str)//初始T=NULL  
    {  
        char *ch;  
        int flag=0;  
        BTree p;  
        stack<BTnode *> Stack; //实例化栈  
        p=NULL;  
        ch=str;  
        while((*ch)!='\0')  
        {  
            switch(*ch)  
            {  
            case'(':  
                Stack.push(p);  
                flag=1;  
                break;  
            case',':  
                flag=2;  
                break;  
            case')':  
                Stack.pop();  
                break;  
            default://对字符的处理  
                p=(BTree)malloc(sizeof(BTnode));  
                p->date=*ch;  
                p->lchild=p->rchild=NULL;  
                if(T==NULL)  
                    T=p;  
                else  
                {  
                    if(flag==1)  
                        Stack.top()->lchild=p;  
                    if(flag==2)  
                        Stack.top()->rchild=p;  
                }  
            }  
            ch++;  
        }  
        return OK;  
    }  
    Status visit(BTree e)  
    {  
        printf("%c",e->date);  
        return OK;  
    }  
    Status preorder(BTree T)  
    {  
        BTree p;  
        stack<BTnode *> Stack;   
        p=T;  
        Stack.push(NULL);  
        while(p!=NULL)  
        {  
            visit(p);//访问节点  
            if(p->rchild!=NULL)//如果有右孩子，此右孩子节点进栈，  
                Stack.push(p->rchild);  
            if(p->lchild!=NULL)//向左移动  
                p=p->lchild;  
            else//左孩子已访问过，p=根—>rchild  
            {  
                p=Stack.top();  
                Stack.pop();  
            }  
        }  
        return OK;  
    }  
    Status inorder(BTree T)  
    {  
        BTree p;  
        p=NULL;  
        stack<BTree> Stack;//实例化栈  
        Stack.push(T);//根节点进栈  
        while(!Stack.empty())  
        {  
            while(Stack.top()!=NULL)//一路向左，至最左  
                Stack.push(Stack.top()->lchild);  
            Stack.pop();//空指针弹出  
            if(!Stack.empty())  
            {  
                p=Stack.top();  
                Stack.pop();  
                visit(p);  
                Stack.push(p->rchild);//向右移动  
            }  
        }  
        return OK;  
    }  
    Status postorder(BTree T)  
    {  
        stack<stacknode> Stack;  
        stacknode S;  
        BTree p;  
        p=T;  
        do  
        {  
            while(p!=NULL)//一路向左，进栈，至最左  
            {  
                S.ptr=p;  
                S.tag=L;  
                Stack.push(S);  
                p=p->lchild;  
            }  
            while(!Stack.empty()&&Stack.top().tag==R)    
            {  
                S=Stack.top();  
                Stack.pop();  
                p=S.ptr;  
                visit(p);   //tag为R，表示右子树访问完毕，故访问根结点         
            }  
            if(!Stack.empty())//向右移一个  
            {  
                Stack.top().tag=R;  
                p=Stack.top().ptr->rchild;  
            }  
      
      
        }while(!Stack.empty());  
        return OK;  
    }  
    Status getTreeHeight(BTree T,int &H)  
    {  
        //递归，分别计算左、右子树的高度，后比较较大者，+1  
        int lchildH,rchildH;  
        lchildH=rchildH=0;//左右子树高度，初始化  
        if(T==NULL)  
            H=0;  
        else  
        {  
            getTreeHeight(T->lchild,lchildH);//计算左子树的高度  
            getTreeHeight(T->rchild,rchildH);//计算右子树的高度  
            if(lchildH>rchildH)  
                H=lchildH+1;  
            else   
                H=rchildH+1;  
        }  
        return OK;  
    }  
    Status findNode(BTree T,ElemType e,BTnode &bt)  
    {  
        if(T==NULL)//当前BTree为空  
        {  
            bt.date=NULL;  
            return ERROR;  
        }  
        else if(T->date==e)//找到，当前节点符合  
            bt=*T;  
        else  
        {  
            findNode(T->lchild,e,bt);//在左子树中寻找  
            if(bt.date==NULL)  
                findNode(T->rchild,e,bt);//在右子树中寻找  
        }  
        return OK;  
    }