//非遞歸前序遍歷
typedef struct btnode{    char data;    struct btnode *lchild;    struct btnode *rchild;}btnode;typedef struct seqstack{    btnode *stack_p[SIZE]; //store pointers of stack    int tag[SIZE];      //為了非遞歸后續(xù)遍歷使用    int top;            //top of stack}seqstack;void push(seqstack *s,btnode *t){    if(s->top == SIZE){        PRintf("the stack is full/n");    }    else{        (s->top)++;        s->stack_p[s->top] = t;    }}btnode* pop(seqstack *s){    if(s->top==-1){        return NULL;    }    else{        (s->top)--;        return s->stack_p[(s->top)+1];    }}
void preorder1(btnode *t){    seqstack s;    s.top = -1;    if(!t){        cout << "the tree is empty" <<endl;    }    else    {        while((s.top != -1) || (t) ){                while(t){     //棧不為空這入棧并打印，直到葉子節(jié)點                printf("%c/n",t->data);                push(&s,t);                t = t->lchild;            }                     t = pop(&s);  //回溯到上一個根節(jié)點            t = t->rchild;        }    }}
二叉樹重構(gòu)
主要是通過前序遍歷和中序遍歷的特點，前序首先讀取根節(jié)點，然后再中序中找到根節(jié)點的位置，將根的左右子樹分開求解。遞歸。因為兩種遍歷順序，每種在根旁邊有左右子樹。故用4個vector存儲4個subtree。遍歷結(jié)束標(biāo)志是到葉子節(jié)點，此時其分支數(shù)目為0。
btnode *reConstructBintree(vector<int> pre,vector<int> vin){//the length of preint length = pre.size();cout << length <<endl;if(length == 0)    return NULL;//    return new btnode(pre[0]);//define 4 vector to store left subtree and right subtreevector<int> l_pre,r_pre,l_vin,r_vin;btnode *head = new btnode(pre[0]);int gen=0;for(int i = 0; i < length; i++){    if(pre[0] == vin[i]){        gen = i;        break;    }}for(int i = 0; i < gen; i++){    l_pre.push_back(pre[i+1]);    l_vin.push_back(vin[i]);}for(int i=gen+1; i<length; i++){    r_pre.push_back(pre[i]);    r_vin.push_back(vin[i]);}head->lchild = reConstructBintree(l_pre,l_vin);head->rchild = reConstructBintree(r_pre,r_vin);return head;}