一、求二叉树的前序遍历中的第k个节点
//求先序遍历中的第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个节点
//求中序遍历中的第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个节点
//求后序遍历中的第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>-);
}
}