//求先序遍历中的第k个节点的值

int n=;

elemType preNode(BTNode *root,int k){

    if(root==NULL)

        return ' ';

    if(n==k)

        return root->data;

    n++;

    elemType ch = preNode(root->lchild,k);

    if(ch!=' ')

        return ch;

    ch = preNode(root->rchild,k);

    return ch;

}

//求先序遍历中的第k个节点的值(非递归)

elemType preNode2(BTNode *root,int k){

    if(root!=NULL){

        int n=;

        stack<BTNode*> s;

        BTNode *p=root;

        s.push(p);

        while(!s.empty()){

            p=s.top();

            s.pop();

            n++;

            if(n==k){

                //printf("%c ",p->data);

                return p->data;

            }

            if(p->rchild!=NULL)

                s.push(p->rchild);

            if(p->lchild!=NULL)

                s.push(p->lchild);

        }

    }else

        return ' ';

}

//求中序遍历中的第k个节点的值

elemType inNode(BTNode *root,int k){

    if(root==NULL)

        return ' ';

    stack<BTNode*> s;

    BTNode *p=root;

    int n=;

    while(!s.empty()||p){

        while(p){

            s.push(p);

            p=p->lchild;

        }

        if(!s.empty()){

            p=s.top();

            s.pop();

            n++;

            if(n==k)

                return p->data;

            p=p->rchild;

        }

    }

} 

//求后序遍历中的第k个节点的值

elemType postNode(BTNode *root,int k){

    BTNode* stack[];

    int top=-;

    int f=;

    int n=;

    BTNode *b=NULL;

    if(root!=NULL){

        BTNode *p=root;

        do{

            while(p){

                stack[++top]=p;

                p=p->lchild;

            }

            f=;

            b=NULL;

            while(top>-&&f){

                p=stack[top];

                if(p->rchild==b){

                    n++;

                    if(n==k)

                        return p->data;

                    b=p;

                    top--;

                }else{

                    p=p->rchild;

                    f=;

                }

            }

        }while(top>-);

    }

}