【每日编程】Day 4求前序遍历序列中第k个结点的结点值

问题描述

假设二叉树采用二叉链表存储结构，设计一个算法，求前序遍历序列中第K个结点的结点值。

问题解决

如果对程序没有时间和空间上的要求，处理前序遍历之类的问题我们一般采用递归的算法。

递归过程中计数：

静态局部变量    全局变量   引用参数

#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T)
{
	char ch;
	ch=getchar();
	if(ch=='#')
		*T=NULL;
	else
	{
		(*T)=(BiTNode*)malloc(sizeof(BiTNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
	return OK;
}
Status PreOrderTraverse(BiTree T,Status (*visit)(TElemType e))
{
	if(T)
	{
		(*visit)(T->data);
		PreOrderTraverse(T->lchild,visit);
		PreOrderTraverse(T->rchild,visit);
	}
	else
		return OK;
}
Status visit(TElemType e)
{
  printf("%c\t",e);
  return OK;
}
Status fun1(BiTree T,int k,BiTree *p)
{
	static int n=0;
	if(T)
	{
		n++;
		if(n==k)
		{
			*p=T;
		}
		fun1(T->lchild,k,p);
		fun1(T->rchild,k,p);
	}
	if(T)
		printf("%c",T->data);
	else
		printf("NULL");
	printf("%d\n",n);
	return k;
}
int main()
{
	BiTree T,p;
	int k;
	printf("请输入一个二叉链表：");
	CreateBiTree(&T);
	printf("先序遍历后的链表为：\n");
	PreOrderTraverse(T,visit);
	printf("\n请输入k的值：\n");
	scanf("%d",&k);
	fun1(T,k,&p);
	printf("第%d个结点的结点值为%c",k,p->data);
	return 0;
}