文档介绍://名称:
//功能:编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值
//作者:薛小超
//日期:2012.
//*******************************************************************
#include <iostream>
using namespace std;
typedef char TElemType;
typedef struct BiTNode//定义声明结构体BiTNode
{
TElemType data;
BiTNode *lchild,*rchild;
}*BiTree;
void visit (TElemType a)//访问
{
ﻩcout<<a;
}
void CreateBiTree(BiTree &T,char a[],int &i)
{
ﻩi++;
ﻩif(a[i]=='#')
ﻩ{
ﻩ T=NULL;
ﻩ return;
ﻩ}
T=new BiTNode;
ﻩT->data=a[i];
CreateBiTree(T->lchild,a,i);
ﻩCreateBiTree(T->rchild,a,i);
}
void CreateBiTree(BiTree &T,char a[])//创建二叉树
{
ﻩint i=-1;
ﻩCreateBiTree(T,a,i);
}
void preorderlists(BiTree T,void visit(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<<')';
}
}
void PreorderSearch_(BiTree T,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);
}