求先序遍历序列中第(1＜=k＜=二叉树中结点个数)个结点的值

本题本质上就是一个遍历算法的实现，只不过用一个全局变量的来记录访问的序号，求其他遍历序列的第k个结点也采用相似的方法。二叉树的遍历算法可以引申出大量的算法题，因此考生务必熟练掌握二叉树的遍历算法。 

 C语言代码：

 
//本题本质上就是一个遍历算法的实现，只不过用一个全局变量的
//来记录访问的序号，求其他遍历序列的第k个结点也采用相似的
//方法。二叉树的遍历算法可以引申出大量的算法题，因此考生务必
//熟练掌握二叉树的遍历算法。
 
#include 
using namespace std;
 
typedef char ElemType;
typedef struct BiNode {
	ElemType data;
	BiNode* lchild;
	BiNode* rchild;
}BiNode, * BiTree;
 
//构建二叉树
BiNode* Create(BiNode* bt) {
	static int i = 0;
	char ch;
	//string str = "AB#D##C##";
	//string str = "124##56##7##3##";
	string str = "ABD#G##E##CF###";
	//string str = "ABD#GH##I##E##CF###";
	//string str = "#";
	ch = str[i++];
	if (ch == '#')bt = NULL;//建立一棵空树 
	else {
		bt = (BiTree)malloc(sizeof(BiNode)); bt->data = ch;//生成一个结点，数据域为ch
		bt->lchild = Create(bt->lchild);//递归建立左子树
		bt->rchild = Create(bt->rchild);//递归建立右子树
	}
	return bt;
}
 
int i = 1;//遍历序号的全局变量
ElemType PreNode(BiTree b,int k) {
	char ch;
	//本算法查找二叉树先序遍历中第k个结点的值
	if (b == NULL) {//空结点，则返回特殊字符
		return '#';
	}
	if (i == k) {
		return b->data;
	}
	i++;//下一个结点
	ch = PreNode(b->lchild, k);//左子树中递归寻找
	if (ch != '#')//在左子树中，则返回该值
		return ch;
	ch = PreNode(b->rchild, k);//在右子树中递归寻找
	return ch;
}
 
void PreOrder(BiTree T) {
	if (T) {
		printf("%c ", T->data);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
int main() {
	BiTree T = (BiTree)malloc(sizeof(BiNode));
	T = Create(T);
	int num = 5;
	ElemType ch;
	ch = PreNode(T, num);
	if (ch != '#') {
		//递归先序遍历
		printf("递归先序遍历序列：");
		PreOrder(T);
		printf("\n先序遍历序列中第%d个结点值为：%c ", num, ch);
	}
	else {
		printf("该二叉树是一棵空树");
	}
}

实验结果图：