二叉树先序，中序，后序遍历非递归实现

#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<queue>  
#include<stack>  
using namespace std;  
char in[30],pre[30],last[30];  
  
typedef struct mynode  
{  
    char data;  
    struct mynode* leftchild;  
    struct mynode* rightchild;  
} Node,*pNode;  
  
void build(char *pre,char *in,int len,pNode &root)  
{  
    if(len<1)  
        return;  
    int i=0;  
    while(pre[0]!=in[i])i++;  
    root = (pNode)malloc(sizeof(Node));  
    root->data = pre[0];  
    root->rightchild = root->leftchild = NULL;  
    build(pre+1,in,i,root->leftchild);  
    build(pre+i+1,in+i+1,len-i-1,root->rightchild);  
}  
  
//层序遍历  
void seqorder(pNode root)  
{  
    pNode temp;  
    queue<pNode> qe1;  
    queue<pNode> qe2;  
    qe1.push(root);
    while(!qe1.empty())  
    {  
        temp = qe1.front();  
        qe1.pop();  
        printf("%c",temp->data);  
        if(temp->leftchild)  
            qe2.push(temp->leftchild);  
        if(temp->rightchild)  
            qe2.push(temp->rightchild);
        if(qe1.empty() && !qe2.empty()){
            swap(qe1,qe2);
            printf("\n");  
        }
    }  
}  
  
//中序遍历  
void inorder(pNode root)  
{  
    if(NULL==root) return;  
    inorder(root->leftchild);  
    printf("%c",root->data);  
    inorder(root->rightchild);  
  
}  
  
//前序遍历  
void preorder(pNode root)  
{  
    if(NULL==root) return;  
    printf("%c",root->data);  
    preorder(root->leftchild);  
    preorder(root->rightchild);  
}  
  
//后续遍历  
void lastorder(pNode root)  
{  
    if(NULL==root)return;  
    lastorder(root->leftchild);  
    lastorder(root->rightchild);  
    printf("%c",root->data);  
}  
  
//前序非递归  
void _preorder(pNode root)  
{  
    stack<pNode> stk;  
    while(!stk.empty()||root!=NULL)  
    {  
        while(root)  
        {  
            stk.push(root);  
            printf("%c",root->data);  
            root = root->leftchild;  
        }  
        root = stk.top();  
        root = root->rightchild;  
        stk.pop();  
    }  
}  
//中序遍历非递归  
void _inorder(pNode root)  
{  
    stack<pNode> stk;  
  
    while(root||!stk.empty())  
    {  
        while(root)  
        {  
            stk.push(root);  
            root = root->leftchild;  
        }  
        root = stk.top();  
        stk.pop();  
        printf("%c",root->data);  
        root = root->rightchild;  
    }  
}  
  
//后续遍历非递归  
void _lastorder(pNode root)  
{  
    stack<pNode> stk1;  
    stack<pNode> stk2;
    stk1.push(root);  
    while(!stk1.empty())  
    {  
        root = stk1.top();  
        stk1.pop();
        stk2.push(root);
        if(root->leftchild){
            stk1.push(root->leftchild);
        }  
        if(root->rightchild){
            stk1.push(root->rightchild);
        }
    }  
    while(!stk2.empty()){
        printf("%d",stk2.top()->data);
        stk2.pop();
    }
}  
int main(void)  
{  
    scanf("%s %s",pre,in);  
    pNode root;  
    build(pre,in,strlen(pre),root);  
    //lastorder(root);  
    _lastorder(root);  
    return 0;  
}