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

#include<iostream> using namespace std; typedef class trees { public: int data; trees *left; trees *right; }*Btree,btree; typedef class Node { public : Btree node; }*Qnode,qnode; typedef class Stack //创建一个链栈，用来遍历 { public: Btree tree; Stack *next; }*LinkStack,Link; void push_Stack(LinkStack &L,Btree t);//进栈操作 void init_Stack(LinkStack &L);//初始化栈 Btree pop_Stack(LinkStack &L);//出栈操作 void insert_tree(Qnode &L,int e);//建立二叉搜索树 以及插入 bool empty_Stack(LinkStack L);//判断栈是否为空 void mid_printlist(Qnode L);//中序遍历 void get_mid_printk(Btree tree,int &e,int &n,int k);//初始化为1 k初始化为想要的值 //这里的n一定要加引用 int main() { LinkStack Stacks; init_Stack(Stacks); int a[9]={4,6,1,8,3,2,5,7,9}; Qnode L=new qnode; L->node=NULL; for(int i=0;i<=8;i++) { insert_tree(L,a[i]); } mid_printlist(L); int e=-1,k; cout<<"你想要得到中序遍历第几个值"<<endl; cin>>k; int n=1; get_mid_printk(L->node,e,n,k); cout<<"中序遍历第"<<k<<"个值为"<<e<<endl; return 0; } void init_Stack(LinkStack &L) //初始化栈 { L=new Link; L->next=NULL; } void push_Stack(LinkStack &L,Btree t)//进栈操作 { LinkStack p=new Link; p->tree=t; p->next=L->next; L->next=p; } bool empty_Stack(LinkStack L)//判断栈是否为空 { if(L->next==NULL) { return true; } else { return false; } } Btree pop_Stack(LinkStack &L)//出栈操作 { if(!empty_Stack(L)) { LinkStack p=L->next; L->next=p->next; return p->tree; } else { return NULL; } } void insert_tree(Qnode &L,int e)//建立二叉搜索树 以及插入 { Btree p=new btree; p->left=NULL; p->right=NULL; p->data=e; if(L->node==NULL) { L->node=p; } else { Btree temp=L->node; while(temp!=NULL) { if(e<temp->data) { if(temp->left==NULL) { temp->left=p; return ; } else { temp=temp->left; } } else { if(temp->right==NULL) { temp->right=p; return ; } else { temp=temp->right; } } } } } void mid_printlist(Qnode L)//中序遍历 { Btree p=L->node; LinkStack Stack=new Link; init_Stack(Stack); while(!empty_Stack(Stack)||p) { while(p!=NULL) { push_Stack(Stack,p); p=p->left; } if(!empty_Stack(Stack)) { Btree s=pop_Stack(Stack); cout<<s->data<<" "; p=s->right; } } } void get_mid_printk(Btree tree,int &e,int &n,int k)//n初始化为1 k初始化为想要的值 { if(tree==NULL) { return ; } else { get_mid_printk(tree->left,e,n,k); if(n<=k) { cout<<n<<": "<<tree->data<<" "; if(n==k) { e=tree->data; } } n++; get_mid_printk(tree->right,e,n,k); } }