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

《二叉树中求位于先序序列中第k个位置的结点的值(递归算法).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//名称：6.41//功能：编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值//作者：薛小超//日期：2012.10.30//*******************************************************************#includeusingnamespacestd;typedefcharTElemType;typedefstructBiTNode//定义声明结构体BiTNode{TElemTypedata;BiTNode*lchild,*rchild;}*BiTree;voidvisit(

2、TElemTypea)//访问{cout<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,voidvis

3、it(TElemType))//广义表输出二叉树{if(!T){cout<<'#';return;}visit(T->data);if(T->lchild!=NULL

4、

5、T->rchild!=NULL){cout<<'(';preorderlists(T->lchild,visit);cout<<',';preorderlists(T->rchild,visit);cout<<')';}}voidPreorderSearch_(BiTreeT,int&k,TElemType&s){if(k==0

6、

7、!T)return;if(k==1)s=T->data;k--;Pr

8、eorderSearch_(T->lchild,k,s);PreorderSearch_(T->rchild,k,s);}boolPreorderSearch(BiTreeT,intk,TElemType&s)//在二叉树中求位于先序序列中第k个位置的结点的值{if(k<1)returnfalse;PreorderSearch_(T,k,s);returnk==0;}//主函数intmain(){BiTreeT1;intk=4;TElemTypea[]={"AB#D##G#F##"};TElemTypes;CreateBiTree(T1,a);//创建二叉树cout

9、<<"二叉树为:"<