欸嘿，作为全网唯一你找得到的本道题的题解，本题累计只有百余人作对，本人不才，也作对了（手动狗头）。此题确实有一定难度，需要对二叉树、遍历算法、指针的相关知识十分熟练才能作对此题，我已将里面我踩过的坑一一注释，希望能对后来的同学有所帮助，恕我愚钝，实在是找不到其他较好的算法了，也希望有其他好方法的朋友可以不吝赐教。

问题描述

给定一个包含N个数的序列，依照此序列建立二叉排序树。然后再给出给定的M个数据分别在树中的位置信息，这个位置信息是一个五元组（双亲、左孩子、右孩子、中序深度优先遍历的直接前驱、直接后继）。（M，N<=1000）

输入说明

输入分为四组数据，列为四行（同行数据间以空格隔开）。

 第一组为一个数据，说明序列中元素的个数N；

 第二组为N个数据，即为该序列；

 第三组为一个数据，表示个数M（M<=N）；

 第四组为M个数据，它们都是第二组数据中的某一个，最后需要求解的是这些数据在树中的位置。

输出说明

输出中应该包含M行，每行有五个数据：给定数据在树中的双亲、左孩子、右孩子、中序深度优先遍历的直接前驱、直接后继。其中存在的数据以值表示，不存在的数据以NIL表示。

输入样例

例1：

5

19 23 10 20 45

2

20 19

输出样例

例1：

23 NIL NIL 19 23

NIL 10 23 10 20

#include
#includetypedef struct node {int data;	//数据项struct node* lchild, * rchild, * parent;	//左右子树，及双亲结点指针
}Bstnode;Bstnode* InsertBst(Bstnode* t, Bstnode* s);
Bstnode* CreateBst(int num);
void InOrder(Bstnode*p);
void Search(Bstnode*p, int data);/*此处设定全局变量的原因是需要将二叉排序树的顺序记录下来，并以此来输出前驱及后继结点PS：全局变量自动初始化为0*/int sort[1000];
int g;int main(){int N, M;int i, j;scanf("%d", &N);		//输入结点数Bstnode *tree = CreateBst(N);		//构造新树InOrder(tree);		//将顺序放入数组
//	for(i=0;idata == p->data)	return t;	//树中已有该节点，无需插入if (s->data < p->data)	p = p->lchild;	//在左子树上查找插入位置，如果根结点数值大于插入结点，就放入左子树，否则放右子树elsep = p->rchild;}if (t == NULL){		//原树为空，返回s作为根结点s->parent = NULL; return s;}if (s->data < f->data){		//如果根结点数值大于插入结点，就放入左子树，否则放右子树f->lchild = s;s->parent = f;}elsef->rchild = s;s->parent = f;return t;
}Bstnode* CreateBst(int num) {Bstnode* t, * s;int data;t = NULL;		//设置二叉排序树为空int i = 0;for (i; i < num; i++) {scanf("%d", &data);s = (Bstnode*)malloc(sizeof(Bstnode));	//分配新节点s->lchild = s->rchild = s->parent = NULL;	//左右子树，双亲结点初始化s->data = data;t = InsertBst(t, s);		//插入新节点}return t;
}void InOrder(Bstnode*p){if(p!=NULL){InOrder(p->lchild);		//访问左子树	 sort[g]=p->data;		//将结点数据存入数组 g++;					//每次存一个就g++InOrder(p->rchild);		//访问右子树 }
}void Search(Bstnode*p, int data){if(p!=NULL){Search(p->lchild, data);		//访问左子树，进行数据查找	 	if(p->data==data){		//如果找到了就进行输出 if(p->parent!=NULL){//输出双亲printf("%d ",p->parent->data);}else{printf("NIL ");		//如果为NULL就输出NIL}if((p->lchild!=NULL)){//输出左孩子printf("%d ",p->lchild->data);}else{printf("NIL ");}if((p->rchild!=NULL)){//输出右孩子printf("%d ",p->rchild->data);}else{	printf("NIL ");}			}Search(p->rchild, data);		//访问右子树，进行数据查找}
}

欢迎大家关注：https://github.com/XDUgaile

写完的一些东西会不定时丢上去。