题目描述

利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建，否则创建该结点。最后再输出创建完成的二叉树中的指定结点的双亲结点。注意输入数据序列中的“#”字符和非“#”字符的序列及个数关系，这会最终决定创建的二叉树的形态。

输入

输入用例分2行输入，第一行接受键盘输入的由大写英文字符和“#”字符构成的一个字符串（用于创建对应的二叉树），第二行为指定的结点数据。

输出

用一行输出该用例对应的二叉树中指定结点的双亲结点。若相应双亲结点不存在则以“#”代替。

样例输入

A##
A
ABC####
B

样例输出

A

参考程序

#include<stdio.h>
#include<malloc.h>
struct BTNode
{
	char data;
	struct BTNode *lchild;
	struct BTNode *rchild;
};
void PreOrder(struct BTNode *&p)//先序遍历创建二叉树 
{
	char a;
	scanf("%c",&a);
	if(a=='#') p=NULL;
	else
	{
		p=(struct BTNode*)malloc(sizeof(struct BTNode));
		p->data=a;
		PreOrder(p->lchild);
		PreOrder(p->rchild);
	}
}
void SearchBT(struct BTNode *p,char data)//查找指定双亲结点 
{
	if(p!=NULL)
	{
		if(p->lchild!=NULL&&p->lchild->data==data||p->rchild!=NULL&&p->rchild->data==data)
		printf("%c",p->data);
		else
		{
			SearchBT(p->lchild,data);
			SearchBT(p->rchild,data);
		}
	}
}
int main()
{
	struct BTNode *p;
	PreOrder(p);
	getchar();//抵消回车字符 
	char data;
	scanf("%c",&data);
	if(p->data==data) printf("#");
	else SearchBT(p,data);
}

注意

该程序仅供学习参考！