樹的操作（構造，遍歷，求高度，查找）非遞歸

    // 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;  
}  </pre>