二叉树中求位于先序序列中第k个位置的结点的值(递归算法)

//名称：6.41//功能：编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值//作者：薛小超//日期：2012.10.30//*******************************************************************#includeiostreamusingnamespacestd;typedefcharTElemType;typedefstructBiTNode//定义声明结构体BiTNode{TElemTypedata;BiTNode*lchild,*rchild;}*BiTree;voidvisit(TElemTypea)//访问{couta;}voidCreateBiTree(BiTree&T,chara[],int&i){i++;if(a[i]=='#'){T=NULL;return;}T=newBiTNode;T-data=a[i];CreateBiTree(T-lchild,a,i);CreateBiTree(T-rchild,a,i);}voidCreateBiTree(BiTree&T,chara[])//创建二叉树{inti=-1;CreateBiTree(T,a,i);}voidpreorderlists(BiTreeT,voidvisit(TElemType))//广义表输出二叉树{if(!T){cout'#';return;}visit(T-data);if(T-lchild!=NULL||T-rchild!=NULL){cout'(';preorderlists(T-lchild,visit);cout',';preorderlists(T-rchild,visit);cout')';}}voidPreorderSearch_(BiTreeT,int&k,TElemType&s){if(k==0||!T)return;if(k==1)s=T-data;k--;PreorderSearch_(T-lchild,k,s);PreorderSearch_(T-rchild,k,s);}boolPreorderSearch(BiTreeT,intk,TElemType&s)//在二叉树中求位于先序序列中第k个位置的结点的值{if(k1)returnfalse;PreorderSearch_(T,k,s);returnk==0;}//主函数intmain(){BiTreeT1;intk=4;TElemTypea[]={AB#D##G#F##};TElemTypes;CreateBiTree(T1,a);//创建二叉树cout二叉树为:endl;preorderlists(T1,visit);//广义表输出二叉树coutendlendl;if(PreorderSearch(T1,k,s))cout先序序列中第k个位置的结点的值为:sendl;elsecout未找到第k个位置的结点的值endl;return0;}